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

Jean-Claude Bajard, Julien Eynard, Paulo Martins, 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Fan-VercauterenResidue Number SystemHomomorphic Encryption
Contact author(s)
paulo sergio @ netcabo pt
las @ inesc-id pt
Jean-Claude Bajard @ lip6 fr
vzucca @ uow edu au
History
Short URL
https://ia.cr/2019/500

CC BY

BibTeX

@misc{cryptoeprint:2019/500,
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{https://eprint.iacr.org/2019/500}},
url = {https://eprint.iacr.org/2019/500}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.