Supervision : Jean-Claude BAJARD

Co-supervision : DIDIER Laurent-Stéphane

RNS arithmetic approach of asymmetric cryptography

This thesis is at the crossroads between cryptography and computer arithmetic. It deals with enhancement of cryptographic primitives with regard to computation acceleration and protection against fault injections through the use of residue number systems (RNS) and their associated arithmetic.

So as to contribute to secure the modular multiplication, which is a core operation for many asymmetric cryptographic primitives, a new modular reduction algorithm supplied with fault detection capability is presented. A formal proof guarantees that faults affecting one or more residues during a modular reduction are well detected. Furthermore, this approach is generalized to an arithmetic dedicated to non-prime finite fields.

Afterwards, RNS are used in lattice-based cryptography area. The aim is to exploit acceleration properties enabled by RNS, as it is widely done for finite field arithmetic. As first result, a new version of Babai's round-off algorithm based on hybrid RNS-MRS representation is presented. Then, a new and specific acceleration technique enables to create a full RNS algorithm computing a close lattice vector.

2013-2018 Publications

• 2018
  • J.‑C. Bajard, J. Eynard, N. Merkiche : “Montgomery reduction within the context of residue number system arithmetic”, Journal of Cryptographic Engineering, vol. 8 (3), pp. 189–200, (Springer) (2018)
• 2017
  • J.‑C. Bajard, J. Eynard, A. Hasan, P. Martins, L. Sousa, V. Zucca : “Efficient reductions in cyclotomic rings - Application to Ring-LWE based FHE schemes”, Selected Areas of Cryptography 2017, Ottawa, Canada (2017)
  • P. Martins, J. Eynard, J.‑C. Bajard, L. Sousa : “Arithmetical Improvement of the Round-Off for Cryptosystems in High-Dimensional Lattices”, IEEE Transactions on Computers, vol. PP (Issue: 99), (Institute of Electrical and Electronics Engineers) (2017)
  • J.‑C. Bajard, J. Eynard : “RNS Approach in Lattice-Based Cryptography”, chapter in Embedded Systems Design with Special Arithmetic and Number Systems, pp. pp345-368, (ISBN: 978-3-319-49741-9) (2017)
• 2016
  • J.‑C. Bajard, J. Eynard, A. Hasan, V. Zucca : “A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes”, Selected Areas in Cryptography - SAC LNCS, St. John's, Newfoundland and Labrador, Canada (2016)
  • J.‑C. Bajard, J. Eynard, N. Merkiche : “Multi-fault Attack Detection for RNS Cryptographic Architecture”, 2016 IEEE 23^rd Symposium on Computer Arithmetic, Santa Clara, CA, United States, (IEEE) (2016)
• 2015
  • J. Eynard : “Approche arithmétique RNS de la cryptographie asymétrique”, thesis, phd defence 05/28/2015, supervision Bajard, Jean-Claude, co-supervision : Didier, Laurent-Stéphane (2015)
  • J.‑C. Bajard, J. Eynard, N. Merkiche, Th. Plantard : “RNS Arithmetic Approach in Lattice-based Cryptography Accelerating the " Rounding-off " Core Procedure”, 2015 IEEE 22^nd Symposium on Computer Arithmetic, Lyon, France, pp. 113-120, (IEEE) (2015)
  • P. Martins, L. Sousa, J. Eynard, J.‑C. Bajard : “Programmable RNS lattice-based parallel cryptographic decryption”, IEEE ASAP 2015 Conference, Totonto, Canada (2015)
• 2014
  • J.‑C. Bajard, J. Eynard, N. Merkiche, Th. Plantard : “Babaï Round-Off CVP method in RNS Application to Lattice based cryptographic protocols”, International Symposium on Integrated Circuits, ISIC 2014, Singapore, Singapore, pp. 440-443, (IEEE) (2014)
• 2013
  • J.‑C. Bajard, J. Eynard, F. Gandino : “Fault Detection in RNS Montgomery Modular Multiplication”, 21^st IEEE Symposium on Computer Arithmetic, Austin, United States, pp. 119-126 (2013)