An asymptotically faster version of FV supported on HPR

Due to the Covid-19 crisis all around the world in 2020, the face-to-face meeting has been canceled. However, the paper selection process was completed. The accepted papers have been included in the ARITH-2020 proceedings and will soon be published on IEEE Xplore. They are also posted in the Programme section of this web site: http://arith2020.arithsymposium.org/; International audience; State-of-the-art implementations of homomorphic encryption exploit the Fan and Vercauteren (FV) scheme and the Residue Number System (RNS). While the RNS breaks down large integer arithmetic into smaller independent channels, its non-positional nature makes operations such as division and rounding hard to implement, and makes the representation of small values inefficient. In this work, we propose the application of the Hybrid Position-Residues Number System representation to the FV scheme. This is a positional representation of large radix where the digits are represented in RNS. It inherits the benefits from RNS and allows to accelerate the critical division and rounding operations while also making the representation of smaller values more compact. This directly benefits the decryp-tion and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension n, from O(n 2 log n) to O(n log n) and from O(n 3 log n) to O(n 3), respectively and has resulted in noticeable speedups when experimentally compared to related art RNS implementations.