A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes
International audience Since Gentry's breakthrough work in 2009, homomorphic cryptography has received a widespread attention. Implementation of a fully homomorphic cryptographic scheme is however still highly expensive. Somewhat Homomorphic Encryption (SHE) schemes, on the other hand, allow on...
Main Authors: | , , , |
---|---|
Other Authors: | , , , , , |
Format: | Conference Object |
Language: | English |
Published: |
HAL CCSD
2016
|
Subjects: | |
Online Access: | https://hal.sorbonne-universite.fr/hal-01371941 https://hal.sorbonne-universite.fr/hal-01371941/document https://hal.sorbonne-universite.fr/hal-01371941/file/SAC2016.pdf https://doi.org/10.1007/978-3-319-69453-5_23 |
id |
ftccsdartic:oai:HAL:hal-01371941v1 |
---|---|
record_format |
openpolar |
spelling |
ftccsdartic:oai:HAL:hal-01371941v1 2023-06-06T11:56:43+02:00 A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes Bajard, Jean-Claude Eynard, Julien Hasan, Anwar Zucca, Vincent Performance et Qualité des Algorithmes Numériques (PEQUAN) Laboratoire d'Informatique de Paris 6 (LIP6) Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS) Department of Electrical and Computer Engineering Waterloo (ECE) University of Waterloo Waterloo ANR-15-CE39-0002,ARRAND,Arithmétiques Randomisées(2015) St. John's, Newfoundland and Labrador, Canada 2016-08-09 https://hal.sorbonne-universite.fr/hal-01371941 https://hal.sorbonne-universite.fr/hal-01371941/document https://hal.sorbonne-universite.fr/hal-01371941/file/SAC2016.pdf https://doi.org/10.1007/978-3-319-69453-5_23 en eng HAL CCSD info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-69453-5_23 hal-01371941 https://hal.sorbonne-universite.fr/hal-01371941 https://hal.sorbonne-universite.fr/hal-01371941/document https://hal.sorbonne-universite.fr/hal-01371941/file/SAC2016.pdf doi:10.1007/978-3-319-69453-5_23 info:eu-repo/semantics/OpenAccess Selected Areas in Cryptography - SAC LNCS Selected Areas in Cryptography - SAC https://hal.sorbonne-universite.fr/hal-01371941 Selected Areas in Cryptography - SAC, Aug 2016, St. John's, Newfoundland and Labrador, Canada. ⟨10.1007/978-3-319-69453-5_23⟩ https://www.engr.mun.ca/~sac2016/organization/program/ Lattice-based Cryptography Homomorphic Encryption FV Residue Number Systems Software Implementation [INFO]Computer Science [cs] info:eu-repo/semantics/conferenceObject Conference papers 2016 ftccsdartic https://doi.org/10.1007/978-3-319-69453-5_23 2023-04-16T05:49:40Z International audience Since Gentry's breakthrough work in 2009, homomorphic cryptography has received a widespread attention. Implementation of a fully homomorphic cryptographic scheme is however still highly expensive. Somewhat Homomorphic Encryption (SHE) schemes, on the other hand, allow only a limited number of arithmetical operations in the encrypted domain, but are more practical. Many SHE schemes have been proposed, among which the most competitive ones rely on (Ring-) Learning With Error (RLWE) and operations occur on high-degree polynomials with large coecients. This work focuses in particular on the Chinese Remainder Theorem representation (a.k.a. Residue Number Systems) applied to large coecients. In SHE schemes like that of Fan and Vercauteren (FV), such a representation remains hardly compatible with procedures involving coecient-wise division and rounding required in decryption and homomorphic multiplication. This paper suggests a way to entirely eliminate the need for multi-precision arithmetic, and presents techniques to enable a full RNS implementation of FV-like schemes. For dimensions between 2 11 and 2 15 , we report speed-ups from 5⇥ to 20⇥ for decryption, and from 2⇥ to 4⇥ for multiplication. Conference Object Newfoundland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) Canada Newfoundland 423 442 |
institution |
Open Polar |
collection |
Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
op_collection_id |
ftccsdartic |
language |
English |
topic |
Lattice-based Cryptography Homomorphic Encryption FV Residue Number Systems Software Implementation [INFO]Computer Science [cs] |
spellingShingle |
Lattice-based Cryptography Homomorphic Encryption FV Residue Number Systems Software Implementation [INFO]Computer Science [cs] Bajard, Jean-Claude Eynard, Julien Hasan, Anwar Zucca, Vincent A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes |
topic_facet |
Lattice-based Cryptography Homomorphic Encryption FV Residue Number Systems Software Implementation [INFO]Computer Science [cs] |
description |
International audience Since Gentry's breakthrough work in 2009, homomorphic cryptography has received a widespread attention. Implementation of a fully homomorphic cryptographic scheme is however still highly expensive. Somewhat Homomorphic Encryption (SHE) schemes, on the other hand, allow only a limited number of arithmetical operations in the encrypted domain, but are more practical. Many SHE schemes have been proposed, among which the most competitive ones rely on (Ring-) Learning With Error (RLWE) and operations occur on high-degree polynomials with large coecients. This work focuses in particular on the Chinese Remainder Theorem representation (a.k.a. Residue Number Systems) applied to large coecients. In SHE schemes like that of Fan and Vercauteren (FV), such a representation remains hardly compatible with procedures involving coecient-wise division and rounding required in decryption and homomorphic multiplication. This paper suggests a way to entirely eliminate the need for multi-precision arithmetic, and presents techniques to enable a full RNS implementation of FV-like schemes. For dimensions between 2 11 and 2 15 , we report speed-ups from 5⇥ to 20⇥ for decryption, and from 2⇥ to 4⇥ for multiplication. |
author2 |
Performance et Qualité des Algorithmes Numériques (PEQUAN) Laboratoire d'Informatique de Paris 6 (LIP6) Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS) Department of Electrical and Computer Engineering Waterloo (ECE) University of Waterloo Waterloo ANR-15-CE39-0002,ARRAND,Arithmétiques Randomisées(2015) |
format |
Conference Object |
author |
Bajard, Jean-Claude Eynard, Julien Hasan, Anwar Zucca, Vincent |
author_facet |
Bajard, Jean-Claude Eynard, Julien Hasan, Anwar Zucca, Vincent |
author_sort |
Bajard, Jean-Claude |
title |
A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes |
title_short |
A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes |
title_full |
A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes |
title_fullStr |
A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes |
title_full_unstemmed |
A Full RNS Variant of FV like Somewhat Homomorphic Encryption Schemes |
title_sort |
full rns variant of fv like somewhat homomorphic encryption schemes |
publisher |
HAL CCSD |
publishDate |
2016 |
url |
https://hal.sorbonne-universite.fr/hal-01371941 https://hal.sorbonne-universite.fr/hal-01371941/document https://hal.sorbonne-universite.fr/hal-01371941/file/SAC2016.pdf https://doi.org/10.1007/978-3-319-69453-5_23 |
op_coverage |
St. John's, Newfoundland and Labrador, Canada |
geographic |
Canada Newfoundland |
geographic_facet |
Canada Newfoundland |
genre |
Newfoundland |
genre_facet |
Newfoundland |
op_source |
Selected Areas in Cryptography - SAC LNCS Selected Areas in Cryptography - SAC https://hal.sorbonne-universite.fr/hal-01371941 Selected Areas in Cryptography - SAC, Aug 2016, St. John's, Newfoundland and Labrador, Canada. ⟨10.1007/978-3-319-69453-5_23⟩ https://www.engr.mun.ca/~sac2016/organization/program/ |
op_relation |
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-69453-5_23 hal-01371941 https://hal.sorbonne-universite.fr/hal-01371941 https://hal.sorbonne-universite.fr/hal-01371941/document https://hal.sorbonne-universite.fr/hal-01371941/file/SAC2016.pdf doi:10.1007/978-3-319-69453-5_23 |
op_rights |
info:eu-repo/semantics/OpenAccess |
op_doi |
https://doi.org/10.1007/978-3-319-69453-5_23 |
container_start_page |
423 |
op_container_end_page |
442 |
_version_ |
1767964458870636544 |