Modified Multi-Key Fully Homomorphic Encryption Based on NTRU Cryptosystem without Key-Switching

Xiaoliang Che; Tanping Zhou; Ningbo Li; Haonan Zhou; Zhenhua Chen; Xiaoyuan Yang

doi:10.26599/TST.2019.9010076

Tsinghua Science and Technology 2020, 25(5): 564-578 https://doi.org/10.26599/TST.2019.9010076

Open Access | Issue | Published: 16 March 2020

Modified Multi-Key Fully Homomorphic Encryption Based on NTRU Cryptosystem without Key-Switching

Show Author's Information Hide Author's Information Xiaoliang Che, Tanping Zhou, Ningbo Li, Haonan Zhou, Zhenhua Chen, Xiaoyuan Yang(

)

Engineering University of People’s Armed Police, Xi’an 710086, China.

Xi’an University of Science and Technology, Xi’an 710054, China.

Keywords:

NTRU-type Multi-Key Fully Homomorphic Encryption (MKFHE), prime cyclotomic rings, Low Bit Discarded (LBD), homomorphic multiplication decryption structure

Cite this article:

Che X, Zhou T, Li N, et al. Modified Multi-Key Fully Homomorphic Encryption Based on NTRU Cryptosystem without Key-Switching. Tsinghua Science and Technology, 2020, 25(5): 564-578. https://doi.org/10.26599/TST.2019.9010076

Download citation

EndNote(RIS)

BibTeX

575

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

The Multi-Key Fully Homomorphic Encryption (MKFHE) based on the NTRU cryptosystem is an important alternative to the post-quantum cryptography due to its simple scheme form, high efficiency, and fewer ciphertexts and keys. In 2012, López-Alt et al. proposed the first NTRU-type MKFHE scheme, the LTV12 scheme, using the key-switching and modulus-reduction techniques, whose security relies on two assumptions: the Ring Learning With Error (RLWE) assumption and the Decisional Small Polynomial Ratio (DSPR) assumption. However, the LTV12 and subsequent NTRU-type schemes are restricted to the family of power-of-2 cyclotomic rings, which may affect the security in the case of subfield attacks. Moreover, the key-switching technique of the LTV12 scheme requires a circular application of evaluation keys, which causes rapid growth of the error and thus affects the circuit depth. In this paper, an NTRU-type MKFHE scheme over prime cyclotomic rings without key-switching is proposed, which has the potential to resist the subfield attack and decrease the error exponentially during the homomorphic evaluating process. First, based on the RLWE and DSPR assumptions over the prime cyclotomic rings, a detailed analysis of the factors affecting the error during the homomorphic evaluations in the LTV12 scheme is provided. Next, a Low Bit Discarded & Dimension Expansion of Ciphertexts (LBD&DEC) technique is proposed, and the inherent homomorphic multiplication decryption structure of the NTRU is proposed, which can eliminate the key-switching operation in the LTV12 scheme. Finally, a leveled NTRU-type MKFHE scheme is developed using the LBD&DEC and modulus-reduction techniques. The analysis shows that the proposed scheme compared to the LTV12 scheme can decrease the magnitude of the error exponentially and minimize the dimension of ciphertexts.

Full text

Abstract

Full text

Outline

About this article

Modified Multi-Key Fully Homomorphic Encryption Based on NTRU Cryptosystem without Key-Switching

Show Author's information Hide Author's Information Xiaoliang Che, Tanping Zhou, Ningbo Li, Haonan Zhou, Zhenhua Chen, Xiaoyuan Yang(

)

Engineering University of People’s Armed Police, Xi’an 710086, China.

Xi’an University of Science and Technology, Xi’an 710054, China.

Abstract

Keywords: NTRU-type Multi-Key Fully Homomorphic Encryption (MKFHE), prime cyclotomic rings, Low Bit Discarded (LBD), homomorphic multiplication decryption structure

References(34)

[1]

A. Hamlin, A. Shelat, M. Weiss, and D. Wichs, Multi-key searchable encryption, revisited, in Proceedings of IACR International Workshop on Public Key Cryptography, Berlin, Germany, 2018, pp. 95-124.

DOI

[2]

O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, NY, USA, 1987, pp. 218-229.

DOI

[3]

M. Ben-Or, S. Goldwasser, and A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 1988, pp. 1-10.

DOI

[4]

D. Chaum, C. Crépeau, and I. Damgård, Multiparty unconditionally secure protocols (abstract), in Proceedings of Advances in Cryptology-CRYPTO’87, Berlin, Germany, 1987, pp. 462-462.

DOI

[5]

H. Huang, T. Gong, P. Chen, R. Malekian, and T. Chen, Secure two-party distance computation protocol based on privacy homomorphism and scalar product in wireless sensor networks, Tsinghua Science & Technology, vol. 21, no. 4, pp. 385-396, 2016.

DOI Google Scholar

[6]

A. López-Alt, E. Tromer, and V. 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, New York, NY, USA, 2012, pp. 1219-1234.

DOI

[7]

C. Gentry, A. Sahai, and B. Waters, Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attributebased, in Proceedings of Advances in Cryptology-CRYPTO 2013, Berlin, Germany, 2013, pp. 75-92.

DOI

[8]

M. Clear and C. McGoldrick, Multi-identity and multi-key leveled FHE from learning with errors, in Proceedings of Advances in Cryptology - CRYPTO 2015, Berlin, Germany, 2015, pp. 630-656.

DOI

[9]

P. Mukherjee and D. Wichs, Two round multiparty computation via multi-key FHE, in Proceedings of Advances in Cryptology - EUROCRYPT 2016, Berlin, Germany, 2016, pp. 735-763.

DOI

[10]

C. Peikert and S. Shiehian, Multi-key FHE from LWE, revisited, in Proceedings of Theory of Cryptography-14th International Conference, Berlin, Germany, 2016, pp. 217-238.

DOI

[11]

Z. Brakerski and R. Perlman, Lattice-based fully dynamic multi-key FHE with short ciphertexts, in Proceedings of Advances in Cryptology-CRYPTO 2016, Berlin, Germany, 2016, pp. 190-213.

DOI

[12]

L. Chen, Z. Zhang, and X. Wang, Batched multi-hop multi-key FHE from ring-LWE with compact ciphertext extension, in Proceedings of Theory of Cryptography Conference, Berlin, Germany, 2017, pp. 597-627.

DOI

[13]

W. Chongchitmate and R. Ostrovsky, Circuit-private multi-key FHE, in Proceedings of IACR International Workshop on Public Key Cryptography, Berlin, Germany, 2017, pp. 241-270.

DOI

[14]

T. Li, Q Liu, and R Huang, Multi-user fully homomorphic encryption scheme based on proxy re-encryption for cloud computing, Tsinghua Science & Technology, vol. 58, no. 2, pp. 143-149, 2018.

Google Scholar

[15]

J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte, NTRUSign: Digital signatures using the NTRU lattice, in Proceedings of Cryptographers Track at the RSA Conference, Berlin, Germany, 2003, pp. 122-140,

DOI

[16]

L. Ducas, V. Lyubashevsky, and T. Prest, Efficient identity-based encryption over NTRU lattices, in Proceedings of International Conference on the Theory and Application of Cryptology and Information Security, Berlin, Germany, 2014, pp. 22-41.

DOI

[17]

D. Li, J. Liu, Z. Zhang, Q. Wu, and W. Liu, Revocable hierarchical identity-based broadcast encryption, Tsinghua Science & Technology, vol. 5, no. 2, pp. 539-549, 2018.

DOI Google Scholar

[18]

S. Garg, C. Gentry, and S. Halevi, Candidate multilinear maps from ideal lattices, in Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Berlin, Germany, 2013, pp. 1-17.

DOI

[19]

A. Langlois, D. Stehlé, and R. Steinfeld, GGHLite: More efficient multilinear maps from ideal lattices, in Proceedings of EUROCRYPT 2014, Lecture Notes in Computer Science, Berlin, Germany, 2014, pp. 239-256.

DOI

[20]

D. Stehlé and R. Steinfeld, Making NTRU as secure as worst-case problems over ideal lattices, in Proceedings of EUROCRYPT 2011, Lecture Notes in Computer Science, Berlin, Germany, 2011, pp. 27-47.

DOI

[21]

V. Lyubashevsky, C. Peikert, and O. Regev, On ideal lattices and learning with errors over rings, in Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques, Berlin, Germany, 2010, pp. 1-23.

DOI

[22]

M. Albrecht, S. Bai, and L. Ducas, A subfield lattice attack on overstretched NTRU assumptions, in Proceedings of Annual Cryptology Conference, Berlin, Germany, 2016, pp. 153-178.

DOI

[23]

J. H. Cheon, J. Jeong, and C. Lee, An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without an encoding of zero, LMS Journal of Computation and Mathematics, vol. 19, no. 1, pp. 255-266, 2016.

DOI Google Scholar

[24]

Y. Wang, R. Chen, C. Liu, B. Wang, and Y. Wang, Asymmetric subversion attacks on signature and identification schemes, https://doi.org/10.1007/s00779-018-01193-x, 2019.

DOI

[25]

Z. Yang, R. Chen, C. Li, L. Qu, and G. Yang, On the security of LWE cryptosystem against subversion attacks, https://doi.org/10.1093/comjnl/bxz084, 2019.

DOI

[26]

Y. Yu, G. Xu, and X. Wang, Provably secure NTRU instances over prime cyclotomic rings, in Proceedings of IACR International Workshop on Public Key Cryptography, Berlin, Germany, 2017, pp. 409-434.

DOI

[27]

Y. Yu, G. Xu, and X. Wang, Provably secure NTRU encrypt over more general cyclotomic rings, https://eprint.iacr.org/2017/304.pdf, 2017.

DOI

[28]

Z. Brakerski and V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, in Proceedings of Annual Symposium on Foundations of Computer Science, Los Alamitos, CA, USA, 2011, pp. 97-106.

DOI

[29]

Z. Brakerski, C. Gentry, and V. Vaikuntanathan, (Leveled) Fully homomorphic encryption without bootstrapping, in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Cambridge, MA, USA, 2012, pp. 309- 325.

DOI

[30]

Y. Doröz, Y. Hu, and B. Sunar, Homomorphic AES evaluation using the modified LTV scheme, Designs Codes and Cryptography, vol. 80, no. 2, pp. 1-26, 2015.

DOI Google Scholar

[31]

J. W. Bos, K. Lauter, J. Loftus, and M. Naehrig, Improved security for a ring-based fully homomorphic encryption scheme, in Proceedings of International Conference on Cryptography and Coding, Berlin, Germany, 2013, pp. 45-64.

DOI

[32]

D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures, Society for Industrial and Applied Mathematics Journal on Computing, vol. 37, no. 1, pp. 267-302, 2004.

DOI Google Scholar

[33]

Z. Chen, Research and design of fully homomorphic encryption based on lattice, PhD dissertation, Nanjing University of Aeronautics and Astronautics, Nanjing, China, 2015.

[34]

T. Zhou, X. Yang, L. Liu, W. Zhang, and N. Li, Faster bootstrapping with multiple addends, IEEE Access, vol. 1, no. 1, pp. 49868- 49876, 2018.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 29 October 2019

Revised: 05 December 2019

Accepted: 06 December 2019

Published: 16 March 2020

Issue date: October 2020

Copyright

Acknowledgements

This work was supported by the National Key R&D Program of China (No. 2017YFB0802000), the National Natural Science Foundation of China (Nos. U1636114 and 61872289), and National Cryptography Development Fund of China (No. MMJJ20170112).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).