Using Hierarchical Approach to Speed-up RNS Base Extensions in Homomorphic Encryption Context

Morgane Vollmer (1, 2, 3) , Karim Bigou (1, 2) , Arnaud Tisserand (4, 1)

1 Lab-STICC_ARCAD - Equipe Hardware ARchitectures and CAD tools
2 UBO - Université de Brest
3 Lab-STICC_IRIS - Equipe SecurIty and Resilience of Information Systems
4 CNRS - Centre National de la Recherche Scientifique

The numerous and huge operations involved in homomorphic encryption applications require fast arithmetic. RNS arithmetic is popular in their software implementations. In this context, we proposed a hierarchical approach for RNS base extension. It leads to 50-60 % reduction of both computation time and constant storage requirements for large homomorphic parameters in our experimental setup. When state-of-the-art parameters are not suitable for our approach, we propose to use equivalent parameters leading to similar reductions.

Keywords: residue number system; base extension; homomorphic encryption

Domains: Computer Arithmetic; Cryptography and Security [cs.CR]

Morgane Vollmer, Karim Bigou, Arnaud Tisserand. Using Hierarchical Approach to Speed-up RNS Base Extensions in Homomorphic Encryption Context. ARITH: 2023 IEEE 30th International Symposium on Computer Arithmetic, Sep 2023, Portland, Oregon, United States. ⟨hal-04206377⟩