An asymptotically faster version of FV supported on HPR - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

An asymptotically faster version of FV supported on HPR

Résumé

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.
Fichier principal
Vignette du fichier
BEMSZ2020.pdf (402.61 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02883325 , version 1 (29-06-2020)

Identifiants

  • HAL Id : hal-02883325 , version 1

Citer

Jean-Claude Bajard, Julien Eynard, Paulo Martins, Leonel Sousa, Vincent Zucca. An asymptotically faster version of FV supported on HPR. ARITH-2020 - 27th IEEE International Symposium on Computer Arithmetic, Jun 2020, Portland, United States. ⟨hal-02883325⟩
69 Consultations
144 Téléchargements

Partager

Gmail Facebook X LinkedIn More