A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes
Invited by Professor Anwar Hasan
All are welcome!
Homomorphic encryption (HE) enables arithmetic operations in the encrypted domain and hence makes it possible to secure outsourced computations. Gentry's breakthrough work in 2009 opened the way to the development of fully HE schemes, allowing the possibility of unlimited number of additions and multiplications on encrypted data. However,
practicality of such schemes still remains severely restricted due to their poor performance. For this reason, somewhat homomorphic encryption (SHE) schemes, which support only a limited number of operations but offer much better performance, are considered suitable for a variety of practical applications.
Many of the leading SHE schemes proposed so far rely on Ring Learning With Errors (RLWE) problems. For such schemes the underlying operations occur on high-degree polynomials with large coefficients. Various techniques are applied to improve the performance of polynomial and integer arithmetic. For instance, the Residue Number Systems (RNS) can be applied to large coefficients. In SHE schemes like that of Fan and
Vercauteren (FV), such a representation has been exploited to a limited extent only, since RNS is hardly compatible with coefficient-wise division and rounding required in decryption and homomorphic multiplication. Thus, costly switching between RNS and classical positional representation is still used for such operations. In our recent work, we show how to entirely eliminate the need for multi-precision arithmetic in FV like schemes. We present a full RNS implementation of FV. For realistic parameters, we report speedups from 5x to 20x (resp. 2x to 4x) for software implementation of decryption (resp.homomorphic multiplication).
Dr. Julien Eynard is a post-doctoral fellow in the Department of Electrical and Computer Engineering at the University of Waterloo, and hosted by Prof. Anwar Hasan. Dr. Eynardreceived his MSc (2011) at University Joseph Fourier (Grenoble, France), and obtained a PhD (2015) from University Pierre and Marie Curie (Paris, France). His interests are
related to applied cryptography focussing on acceleration of cryptographic algorithms and their protection against side channel attacks.
200 University Avenue West
Waterloo, ON N2L 3G1