Patent attributes
In a general aspect, approximate modular reductions are applied in cryptographic protocols. In some aspects, an array of integers defined for a lattice-based cryptography system is obtained. A transformation is applied to the array of integers, which includes applying a modular reduction to a product of a first integer and a second integer. The first integer is based on the array of integers, and the second integer is based on the transformation. Applying the modular reduction includes operations mathematically equivalent to multiplying the product by a first constant to yield a first intermediate value, applying a bit shift operation to the first intermediate value to yield a second intermediate value, multiplying the second intermediate value by a modulus value to yield a third intermediate value, and subtracting the third intermediate value from the product.