Paper 2022/411

Quotient Approximation Modular Reduction

Aurélien Greuet, 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
modular reductionlattice-based cryptography
Contact author(s)
simon montoya @ idemia com
History
2022-04-08: revised
2022-03-31: received
See all versions
Short URL
https://ia.cr/2022/411
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/411,
      author = {Aurélien Greuet and Simon Montoya and Clémence Vermeersch},
      title = {Quotient Approximation Modular Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2022/411},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/411}},
      url = {https://eprint.iacr.org/2022/411}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.