TY - JOUR
T1 - Homomorphic AES evaluation using the modified LTV scheme
AU - Doröz, Yarkın
AU - Hu, Yin
AU - Sunar, Berk
N1 - Funding Information:
We would like to thank Jeffrey Hoffstein for pointing us to Coppersmith and Shamir’s paper [], and for helpful discussions to William J. Martin on the LTV scheme and to Joppe W. Bos and Michael Naehrig for clarifying the YASHE scheme. This work was in part supported by the NSF-CNS Awards #1117590 and #1319130.
Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - Since its introduction more than a decade ago the homomorphic properties of the NTRU encryption scheme have gone largely ignored. A variant of NTRU proposed by Stehlé and Steinfeld was recently extended into a full fledged multi-key fully homomorphic encryption scheme by López-Alt, Tromer and Vaikuntanathan (LTV). This NTRU based FHE presents a viable alternative to the currently dominant BGV style FHE schemes. While the scheme appears to be more efficient, a full implementation and comparison to BGV style implementations has been missing in the literature. In this work, we develop a customized implementation of the LTV. First parameters are selected to yield an efficient and yet secure LTV instantiation. We present an analysis of the noise growth that allows us to formulate a modulus cutting strategy for arbitrary circuits. Furthermore, we introduce a specialization of the ring structure that allows us to drastically reduce the public key size making evaluation of deep circuits such as the AES block cipher viable on a standard computer with a reasonable amount of memory. Moreover, with the modulus specialization the need for key switching is eliminated. Finally, we present a generic bit-sliced implementation of the LTV scheme that embodies a number of optimizations. To assess the performance of the scheme we homomorphically evaluate the full 10 round AES circuit in 29 h with 2048 message slots resulting in 51 s per AES block evaluation time.
AB - Since its introduction more than a decade ago the homomorphic properties of the NTRU encryption scheme have gone largely ignored. A variant of NTRU proposed by Stehlé and Steinfeld was recently extended into a full fledged multi-key fully homomorphic encryption scheme by López-Alt, Tromer and Vaikuntanathan (LTV). This NTRU based FHE presents a viable alternative to the currently dominant BGV style FHE schemes. While the scheme appears to be more efficient, a full implementation and comparison to BGV style implementations has been missing in the literature. In this work, we develop a customized implementation of the LTV. First parameters are selected to yield an efficient and yet secure LTV instantiation. We present an analysis of the noise growth that allows us to formulate a modulus cutting strategy for arbitrary circuits. Furthermore, we introduce a specialization of the ring structure that allows us to drastically reduce the public key size making evaluation of deep circuits such as the AES block cipher viable on a standard computer with a reasonable amount of memory. Moreover, with the modulus specialization the need for key switching is eliminated. Finally, we present a generic bit-sliced implementation of the LTV scheme that embodies a number of optimizations. To assess the performance of the scheme we homomorphically evaluate the full 10 round AES circuit in 29 h with 2048 message slots resulting in 51 s per AES block evaluation time.
KW - AES
KW - Fully homomorphic encryption
KW - NTRU
KW - Ring-LWE
UR - http://www.scopus.com/inward/record.url?scp=84930168755&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84930168755&partnerID=8YFLogxK
U2 - 10.1007/s10623-015-0095-1
DO - 10.1007/s10623-015-0095-1
M3 - Article
AN - SCOPUS:84930168755
SN - 0925-1022
VL - 80
SP - 333
EP - 358
JO - Designs, Codes, and Cryptography
JF - Designs, Codes, and Cryptography
IS - 2
ER -