Welcome to the resource topic for 2019/500
Title:
An HPR variant of the FV scheme: Computationally Cheaper, Asymptotically Faster
Authors: Jean-Claude Bajard, Julien Eynard, Paulo Martins, Leonel Sousa, 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.
ePrint: https://eprint.iacr.org/2019/500
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .