Paper 2019/500

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

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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Fan-VercauterenResidue Number SystemHomomorphic Encryption
Contact author(s)
paulo sergio @ netcabo pt
las @ inesc-id pt
Jean-Claude Bajard @ lip6 fr
eynard julien @ wanadoo fr
vzucca @ uow edu au
2019-05-20: received
Short URL
Creative Commons Attribution


      author = {Jean-Claude Bajard and Julien Eynard and Paulo Martins and Leonel Sousa and Vincent Zucca},
      title = {An HPR variant of the FV scheme: Computationally Cheaper, Asymptotically Faster},
      howpublished = {Cryptology ePrint Archive, Paper 2019/500},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.