An asymptotically faster version of FV supported on HPR
| Autor: | Vincent Zucca, Julien Eynard, Leonel Sousa, Jean-Claude Bajard, Paulo A.F. Martins |
|---|---|
| Přispěvatelé: | Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs (OURAGAN), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre d'Evaluation de la Sécurité des Technologies de l'Information (CESTI), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa (INESC-ID), Instituto Superior Técnico, Universidade Técnica de Lisboa (IST)-Instituto de Engenharia de Sistemas e Computadores (INESC), IMEC (IMEC), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven), ANR-15-CE39-0002,ARRAND,Arithmétiques Randomisées(2015), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP) |
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
Fan-Vercauteren scheme [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic Rounding 020208 electrical & electronic engineering Dimension (graph theory) Homomorphic encryption 02 engineering and technology Division (mathematics) Residue number system Binary logarithm Computer Science::Hardware Architecture 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Multiplication Radix Hardware_ARITHMETICANDLOGICSTRUCTURES Homomorphic Encryption Residue Number System Mathematics |
| Zdroj: | ARITH ARITH-2020-27th IEEE International Symposium on Computer Arithmetic ARITH-2020-27th IEEE International Symposium on Computer Arithmetic, Jun 2020, Portland, United States |
| Popis: | Due to the Covid-19 crisis all around the world in 2020, the face-to-face meeting has been canceled. However, the paper selection process was completed. The accepted papers have been included in the ARITH-2020 proceedings and will soon be published on IEEE Xplore. They are also posted in the Programme section of this web site: http://arith2020.arithsymposium.org/; International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|