SPRUJB6B November 2024 – May 2025 AM2612
Most MAU commands perform arithmetic modulo some modulus p.
When a user needs to read the result of a sequence of modular operations, it must canonicalize the result. The easiest way to do this is to issue the CANON command, which canonicalizes the scratchpad (by adding p if the scratchpad is negative). Afterward the user can store the canonicalized value to RAM.
When the scratchpad is the result of a modular operation, the MAU will also canonicalize it automatically before certain operations:
Storing the scratchpad somewhere other than a RAM slot.
Performing an integer operation such as INT_ADD on the scratchpad.
Changing the modulus.
The MAU does not do this for values stored in RAM slots. If a user performs some arithmetic modulo p and stores the result to a RAM slot, in general the result will behave correctly if it is later accessed through the same slot-based address for further arithmetic computations mod p. However, if read directly, or if used for arithmetic modulo some q ≠ p, it may not produce the correct result.
If the user writes a value x to a RAM slot, and then performs the following operations, it may produce an unexpected result due to non-canonical reduction:
Reading x back through a non-slot address: this will disregard the sign bit.
Overwriting x through a non-slot address, then using the same address again: this will use the old sign bit.
Reading the value directly from RAM, outside the MAU: this returns the non-canonical value.
Re-defining the slots and then using the value: this clears the sign information.
Changing the modulus, then reading the value: this results in reduction mod the new modulus instead of the old and may result in an arithmetic overflow.
Operating on the value with integer operations. This reads the non-canonical data, possibly including the sign, and may cause arithmetic overflow.
Copying the value with the COPY command to a non-slot address. This discards the sign.
Copying the value with the COPY command with a size different from the modulus. This may copy the sign and will produce an implementation-specific result.
Using the value as a multiplicand, with a length not equal to the modulus length. This applies the sign with the wrong significance, and in any case produces an implementation-specific result.
As in previous versions of the PKE, when the input to a modular operation is not in the appropriate range (here between -p and p-1), then the output might also not be in this range. This is because full modular reduction is expensive, so (for example) the result of an addition of two non-negative numbers is reduced simply by subtracting p. If the inputs are greater than p, then the output will be too. The result will still be correct modulo p unless an arithmetic overflow occurs (i.e. if after subtracting p the result still has too many bits). Arithmetic overflow will trigger an error. This is only a problem for users of low-level commands: high-level ones such as elliptic-curve scalar multiplication will check that their inputs are less than p (or q, as appropriate) before operating.
Users are discouraged from relying on the exact behavior of non-canonical reduction. They should instead use the CANON command to reduce the final value of a computation, as well as values to be used with different moduli or slot arrangements.