Generating Very Large RNS Bases - Sorbonne Université
Journal Articles IEEE Transactions on Emerging Topics in Computing Year : 2022

Generating Very Large RNS Bases

Abstract

Residue Number Systems (RNS) are proven to be effective in speeding up computations involving additions and products. For these representations, there exists efficient modular reduction algorithms that can be used in the context of arithmetic over finite fields or modulo large numbers, especially when used in the context of cryptographic engineering. Their independence allows random draws of bases, which also makes it possible to protect against side-channel attacks, or even to detect them using redundancy. These systems are easily scalable, however the existence of large bases for some specific uses remains a difficult question. In this paper, we present four techniques to extract RNS bases from specific sets of integers, giving better performance and flexibility to previous works in the litterature. While our techniques do not allow to solve efficiently every possible case, we provide techniques to provably and efficiently find the largest possible available RNS bases in several cases, improving the state-of-the-art on various works of the recent literature.
Fichier principal
Vignette du fichier
main_black_white.pdf (1.33 Mo) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03719386 , version 1 (11-07-2022)

Identifiers

Cite

Jean Claude Bajard, Kazuhide Fukushima, Thomas Plantard, Arnaud Sipasseuth. Generating Very Large RNS Bases. IEEE Transactions on Emerging Topics in Computing, 2022, pp.1-12. ⟨10.1109/TETC.2022.3187072⟩. ⟨hal-03719386⟩
47 View
207 Download

Altmetric

Share

More