Cryptology ePrint Archive: Report 2022/411

Quotient Approximation Modular Reduction

Aurélien Greuet and Simon Montoya and Clémence Vermeersch

Abstract: Modular reduction is a core operation in public-key cryptography. While a standard modular reduction is often required, a partial reduction limiting the growth of the coefficients is enough for several usecases.

Knowing the quotient of the Euclidean division of an integer by the modulus allows to easily recover the remainder. We propose a way to compute efficiently, without divisions, an approximation of this quotient. From this approximation, both full and partial reductions are deduced. The resulting algorithms are modulus specific: the sequence of operations to perform in order to get a reduction depends on the modulus and the size of the input.

We analyse the cost of our algorithms for a usecase coming from post-quantum cryptography. We show that with this modulus, on a CPU with a slow multiplication, our method gives an algorithm faster than prior art algorithms.

Category / Keywords: implementation / modular reduction, lattice-based cryptography

Date: received 30 Mar 2022, last revised 8 Apr 2022

Contact author: simon montoya at idemia com

Available format(s): PDF | BibTeX Citation

Version: 20220408:163915 (All versions of this report)

Short URL: ia.cr/2022/411


[ Cryptology ePrint archive ]