Flattening NTRU for evaluation key free homomorphic encryption. (English) Zbl 1448.94196

Summary: We propose a new FHE scheme F-NTRU that adopts the flattening technique proposed in GSW to derive an NTRU based scheme that (similar to GSW) does not require evaluation keys or key switching. Our scheme eliminates the decision small polynomial ratio assumption but relies only on the standard R-LWE assumption. It uses wide key distributions, and hence is immune to Subfield Lattice Attack. In practice, our scheme achieves competitive timings compared to the existing schemes. We are able to compute a homomorphic multiplication in 24.4 msec and 76.0 msec for 5 and 30 levels, respectively, without amortization. Furthermore, our scheme features small ciphertexts, e.g. 2376 KB for 30 levels. The assurance gained by using wide key distributions along with the message space flexibility of the scheme, i.e. bits, binary polynomials, and integers with a large message space, allows the use of the proposed scheme in a wide array of applications.


94A60 Cryptography
81P94 Quantum cryptography (quantum-theoretic aspects)


Full Text: DOI


[1] Martin Albrecht, lwe-estimator, https://bitbucket.org/malb/lwe-estimator.
[2] Joppe W. Bos, Kristin Lauter, Jake Loftus and Michael Naehrig, Cryptography and Coding: 14th IMA International Conference, IMACC 2013, Oxford, UK, December 17-19, 2013. Proceedings, ch. Improved Security for a ing-Based Fully Homomorphic Encryption Scheme, pp. 45-64, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. · Zbl 1317.94088
[3] Zvika Brakerski, Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, pp. 868-886, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. · Zbl 1296.94091
[4] Zvika Brakerski, Craig Gentry and Vinod Vaikuntanathan, Fully Homomorphic Encryption without Bootstrapping, Electronic Colloquium on Computational Complexity (ECCC)18 (2011), 111.
[5] Zvika Brakerski and Vinod Vaikuntanathan, Efficient Fully Homomorphic Encryption from (Standard) LWE, in: FOCS, pp. 97-106, 2011. · Zbl 1292.94038
[6] Yuanmi Chen and Phong Q. Nguyen, BKZ 2.0: Better Lattice Security Estimates, in: ASIACRYPT, pp. 1-20, 2011. · Zbl 1227.94037
[7] Jean-Sébastien Coron, Avradip Mandal, David Naccache and Mehdi Tibouchi, Fully Homomorphic Encryption over the Integers with Shorter Public Keys, in: CRYPTO, pp. 487-504, 2011. · Zbl 1290.94059
[8] Jean-Sébastien Coron, David Naccache and Mehdi Tibouchi, Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers, in: EUROCRYPT, pp. 446-464, 2012. · Zbl 1297.94062
[9] Yarkın Doröz, Yin Hu and Berk Sunar, Homomorphic AES evaluation using the modified LTV scheme, Designs, Codes and Cryptography (2015), 1-26. · Zbl 1402.94055
[10] Junfeng Fan and Frederik Vercauteren, Somewhat Practical Fully Homomorphic Encryption, IACR Cryptology ePrint Archive2012 (2012), 144.
[11] C. Gentry, A Fully Homomorphic Encryption Scheme, Ph.D. thesis, Stanford University, 2009.
[12] Craig Gentry and Shai Halevi, Implementing Gentry’s Fully-Homomorphic Encryption Scheme, in: EUROCRYPT, pp. 129-148, 2011. · Zbl 1281.94026
[13] Craig Gentry, Shai Halevi and Nigel P. Smart, Better Bootstrapping in Fully Homomorphic Encryption, pp. 1-16, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. · Zbl 1290.94077
[14] Craig Gentry, Shai Halevi and Nigel P. Smart, Fully Homomorphic Encryption with Polylog Overhead, pp. 465-482, Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. · Zbl 1297.94071
[15] Craig Gentry, Amit Sahai and Brent Waters, Advances in Cryptology - CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, ch. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based, pp. 75-92, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. · Zbl 1310.94148
[16] Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, Algorithmic Number Theory: Third International Symposiun, ANTS-III Portland, Oregon, USA, June 21-25, 1998 Proceedings, ch. NTRU: A ring-based public key cryptosystem, pp. 267-288, Springer Berlin Heidelberg, Berlin, Heidelberg, 1998. · Zbl 1067.94538
[17] Paul Kirchner and Pierre-Alain Fouque, Revisiting Lattice Attacks on Overstretched NTRU Parameters, pp. 3-26, Springer International Publishing, Cham, 2017. · Zbl 1410.94084
[18] Kristin Lauter, Adriana López-Alt and Michael Naehrig, Progress in Cryptology - LATINCRYPT 2014: Third International Conference on Cryptology and Information Security in Latin America Florianópolis, Brazil, September 17-19, 2014 Revised Selected Papers, ch. Private Computation on Encrypted Genomic Data, pp. 3-27, Springer International Publishing, Cham, 2015. · Zbl 1378.94053
[19] Tancréde Lepoint and Michael Naehrig, A Comparison of the Homomorphic Encryption Schemes FV and YASHE, pp. 318-335, Springer International Publishing, Cham, 2014. · Zbl 1318.94071
[20] Adriana López-Alt, Eran Tromer and Vinod Vaikuntanathan, On-the-fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption, in: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC ‘12, pp. 1219-1234, ACM, New York, NY, USA, 2012. · Zbl 1286.68114
[21] Vadim Lyubashevsky, Chris Peikert and Oded Regev, On Ideal Lattices and Learning with Errors over Rings, pp. 1-23, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. · Zbl 1279.94099
[22] Léo Ducas Martin Albrecht, Shi Bai, A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and Graded Encoding Schemes, Cryptology ePrint Archive, Report 2016/127, 2016, http://eprint.iacr.org/. · Zbl 1351.94019
[23] R. L. Rivest, L. Adleman and M. L. Dertouzos, On Data Banks and Privacy Homomorphisms, Foundations of Secure Computation (1978), 169-180.
[24] Victor Shoup, NTL: A Library for doing Number Theory.
[25] D. Stehlé and R. Steinfeld, Making NTRU as secure as worst-case problems over ideal lattices, Advances in Cryptology - EUROCRYPT ’11 (2011), 27-4. · Zbl 1281.94057
[26] Joop van de Pol and Nigel P. Smart, Estimating Key Sizes for High Dimensional Lattice-Based Systems, pp. 290-303, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. · Zbl 1317.94139
[27] Marten van Dijk, Craig Gentry, Shai Halevi and Vinod Vaikuntanathan, Fully Homomorphic Encryption over the Integers, in: EUROCRYPT, pp. 24-43, 2010. · Zbl 1279.94130
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.