An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

Shai Halevi; Yuriy Polyakov; Victor Shoup

doi:10.1007/978-3-030-12612-4_5

An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

Shai Halevi, Yuriy Polyakov, Victor Shoup

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

106 Scopus citations

Abstract

We present an optimized variant of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme and its efficient implementation in PALISADE. Our algorithmic improvements focus on optimizing decryption and homomorphic multiplication in the Residue Number System (RNS), using the Chinese Remainder Theorem (CRT) to represent and manipulate the large coefficients in the ciphertext polynomials. These improvements are based on our original general-purpose techniques for CRT basis extension and scaling that can be applied to many other lattice-based cryptographic primitives. Our variant is simpler and significantly more efficient than the RNS variant proposed by Bajard et al. both in terms of noise growth and the computational complexity of the underlying CRT basis extension and scaling procedures.

Original language	English (US)
Title of host publication	Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings
Editors	Mitsuru Matsui
Publisher	Springer Verlag
Pages	83-105
Number of pages	23
ISBN (Print)	9783030126117
DOIs	https://doi.org/10.1007/978-3-030-12612-4_5
State	Published - 2019
Event	Cryptographers Track at the RSA Conference 2019, CT-RSA 2019 - San Francisco, United States Duration: Mar 4 2019 → Mar 8 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11405 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Cryptographers Track at the RSA Conference 2019, CT-RSA 2019
Country/Territory	United States
City	San Francisco
Period	3/4/19 → 3/8/19

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

Homomorphic encryption
Lattice-based cryptography
Post-quantum cryptography
Residue number systems
Software implementation

Access to Document

10.1007/978-3-030-12612-4_5

Cite this

Halevi, S., Polyakov, Y., & Shoup, V. (2019). An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. In M. Matsui (Ed.), Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings (pp. 83-105). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11405 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-12612-4_5

Halevi, Shai ; Polyakov, Yuriy ; Shoup, Victor. / An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings. editor / Mitsuru Matsui. Springer Verlag, 2019. pp. 83-105 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d84fe3a6feff47fbacbd5db19898dce9,

title = "An Improved RNS Variant of the BFV Homomorphic Encryption Scheme",

abstract = "We present an optimized variant of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme and its efficient implementation in PALISADE. Our algorithmic improvements focus on optimizing decryption and homomorphic multiplication in the Residue Number System (RNS), using the Chinese Remainder Theorem (CRT) to represent and manipulate the large coefficients in the ciphertext polynomials. These improvements are based on our original general-purpose techniques for CRT basis extension and scaling that can be applied to many other lattice-based cryptographic primitives. Our variant is simpler and significantly more efficient than the RNS variant proposed by Bajard et al. both in terms of noise growth and the computational complexity of the underlying CRT basis extension and scaling procedures.",

keywords = "Homomorphic encryption, Lattice-based cryptography, Post-quantum cryptography, Residue number systems, Software implementation",

author = "Shai Halevi and Yuriy Polyakov and Victor Shoup",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; Cryptographers Track at the RSA Conference 2019, CT-RSA 2019 ; Conference date: 04-03-2019 Through 08-03-2019",

year = "2019",

doi = "10.1007/978-3-030-12612-4_5",

language = "English (US)",

isbn = "9783030126117",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "83--105",

editor = "Mitsuru Matsui",

booktitle = "Topics in Cryptology – CT-RSA 2019 - The Cryptographers{\textquoteright} Track at the RSA Conference 2019, Proceedings",

address = "Germany",

}

Halevi, S, Polyakov, Y & Shoup, V 2019, An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. in M Matsui (ed.), Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11405 LNCS, Springer Verlag, pp. 83-105, Cryptographers Track at the RSA Conference 2019, CT-RSA 2019, San Francisco, United States, 3/4/19. https://doi.org/10.1007/978-3-030-12612-4_5

An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. / Halevi, Shai; Polyakov, Yuriy; Shoup, Victor.
Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings. ed. / Mitsuru Matsui. Springer Verlag, 2019. p. 83-105 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11405 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

AU - Halevi, Shai

AU - Polyakov, Yuriy

AU - Shoup, Victor

PY - 2019

Y1 - 2019

N2 - We present an optimized variant of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme and its efficient implementation in PALISADE. Our algorithmic improvements focus on optimizing decryption and homomorphic multiplication in the Residue Number System (RNS), using the Chinese Remainder Theorem (CRT) to represent and manipulate the large coefficients in the ciphertext polynomials. These improvements are based on our original general-purpose techniques for CRT basis extension and scaling that can be applied to many other lattice-based cryptographic primitives. Our variant is simpler and significantly more efficient than the RNS variant proposed by Bajard et al. both in terms of noise growth and the computational complexity of the underlying CRT basis extension and scaling procedures.

AB - We present an optimized variant of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme and its efficient implementation in PALISADE. Our algorithmic improvements focus on optimizing decryption and homomorphic multiplication in the Residue Number System (RNS), using the Chinese Remainder Theorem (CRT) to represent and manipulate the large coefficients in the ciphertext polynomials. These improvements are based on our original general-purpose techniques for CRT basis extension and scaling that can be applied to many other lattice-based cryptographic primitives. Our variant is simpler and significantly more efficient than the RNS variant proposed by Bajard et al. both in terms of noise growth and the computational complexity of the underlying CRT basis extension and scaling procedures.

KW - Homomorphic encryption

KW - Lattice-based cryptography

KW - Post-quantum cryptography

KW - Residue number systems

KW - Software implementation

UR - http://www.scopus.com/inward/record.url?scp=85062782801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85062782801&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-12612-4_5

DO - 10.1007/978-3-030-12612-4_5

M3 - Conference contribution

AN - SCOPUS:85062782801

SN - 9783030126117

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 83

EP - 105

BT - Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings

A2 - Matsui, Mitsuru

PB - Springer Verlag

T2 - Cryptographers Track at the RSA Conference 2019, CT-RSA 2019

Y2 - 4 March 2019 through 8 March 2019

ER -

Halevi S, Polyakov Y, Shoup V. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. In Matsui M, editor, Topics in Cryptology – CT-RSA 2019 - The Cryptographers’ Track at the RSA Conference 2019, Proceedings. Springer Verlag. 2019. p. 83-105. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-12612-4_5

An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this