Cryptology ePrint Archive: Report 2019/500

An HPR variant of the FV scheme: Computationally Cheaper, Asymptotically Faster

Jean-Claude Bajard and Julien Eynard and Paulo Martins and Leonel Sousa and Vincent Zucca

Abstract: 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 decryption and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension $n$, from $\mathcal{O} (n^2 \log n)$ to $\mathcal{O} (n \log n)$ and from $\mathcal{O}(n^3 \log n)$ to $\mathcal{O} (n^{3})$, respectively. This has also resulted in noticeable speedups when experimentally compared to related art RNS implementations.

Category / Keywords: public-key cryptography / Fan-Vercauteren, Residue Number System, Homomorphic Encryption

Date: received 15 May 2019

Contact author: paulo sergio at netcabo pt,las@inesc-id pt,Jean-Claude Bajard@lip6 fr,eynard julien@wanadoo fr,vzucca@uow edu au

Available format(s): PDF | BibTeX Citation

Version: 20190520:123602 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]