Multi-key Fully Homomorphic Encryption Scheme over Prime Power Cyclotomic Rings

doi:10.3969/j.issn.1671-1122.2020.05.010

Abstract

Abstract:

The traditional fully homomorphic encryption scheme allows arbitrary evaluations on the ciphertext from a single user.After decryption, a result consistent with the plaintext evaluations can be obtained.The multi-key fully homomorphic encryption schemes allow the cloud server to perform arbitrary evaluations on ciphertexts from multiple parties, which is more suitable for cloud computing application. The multi-key fully homomorphic encryption schemes based on NTRU have the characteristics of short keys, small ciphertext sizes, high operation speed and potential resistant from quantum attacks. However, the existing NTRU multi-key fully homomorphic encryption schemes have the problems that they have rare optional ring structures, and the ring structure is vulnerable to subfield attacks. In this paper, the power of 2 cyclotomic ring in the multi-key homomorphic scheme LTV12 was changed into the prime power cyclotomic ring. The key generation algorithm uses the Gaussian distribution over canonical embedding. Therefore, the number of optional ring structures increased and the scheme is not vulnerable to subfield attacks anymore, which has a driving significance for the practicability and security of the scheme, which has a driving significance for the practicability and security of the scheme.

Key words: multi-key, fully homomorphic encryption, prime power cyclotomic rings, canonical embedding

CLC Number:

TP309

ZHOU Haonan, LI Ningbo, CHE Xiaoliang, YANG Xiaoyuan. Multi-key Fully Homomorphic Encryption Scheme over Prime Power Cyclotomic Rings[J]. Netinfo Security, 2020, 20(5): 83-87.

References 15

[1]	GENTRY C . Fully Homomorphic Encryption Using Ideal Lattices [C]// ACM. Proceedings of the 41st Annual ACM Symposium on Theory of Computing(STOC), May 31-June 2, 2009, Bethesda, MD, USA. New York: ACM, 2009: 169.
[2]	BRAKERSKI Z, VAIKUNTANATHAN V . Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages [C]// Springer. Advances in Cryptology(CRYPTO), August 14-18, 2011, Santa Barbara, CA, USA. Berlin Heidelberg: Springer, 2011: 505-524.
[3]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V . (Leveled) Fully Homomorphic Encryption without Bootstrapping [C]// ACM. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference(ITCSC), January 1-10, 2012, Cambridge, Massachusetts. New York: ACM, 2012: 309-325.
[4]	GENTRY C, SAHAI A, WATERS B . Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based [C]// Springer. Advances in Cryptology(CRYPTO), August 18-22, 2013, Santa Barbara, CA, USA. Berlin Heidelberg: Springer, 2013: 75-92.
[5]	LOPEZ A, ADRIANA, TROMER E, VAIKUNTANATHAN V . On-the-fly Multiparty Computation on the Cloud via Multi-key Fully Homomorphic Encryption[C]// ACM. Proceedings of the 44th Symposium on Theory of Computing(STOC), May 19-22, 2012, New York, USA. New York: ACM: 1219-1234.
[6]	STEHLE D, STEINFELD R . Making NTRU as Secure as Worst-Case Problems over Ideal Lattices [C]// ACM. Advances in Cryptology- EUROCRYPT 2011(EUROCRYPT), May 15-19, 2011, Tallinn, Estonia. New York: ACM, 2011: 27-47.
[7]	GENTRY C . A Fully Homomorphic Encryption Scheme[M]. California: Stanford University, 2009.
[8]	LYUBASHEVSKY V, PEIKERT C, REGEV O . On Ideal Lattices and Learning with Errors over Rings [C]// Springer. Advances in Cryptology-EUROCRYPT 2010(EUROCRYPT), May 30-June 3, 2010, Riviera, French. Berlin, Heidelberg: Springer, 2010: 1-23.
[9]	DOROZ Y, HU Yin, SUNAR B . Homomorphic AES Evaluation Using the Modified LTV Scheme[J]. Designs, Codes and Cryptography, 2016,80(2):333-358.
[10]	CHEN Zhigang, SHI Yafeng, SONG Xinxia . Estimating Concert Security Parameters of Fully Homomorphic Encryption[J]. Journal of Cryptologic Research, 2016,3(5):480-491.
	陈智罡, 石亚峰, 宋新霞 . 全同态加密具体安全参数分析[J]. 密码学报, 2016,3(5):480-491.
[11]	YU Yang, XU Guangwu, WANG Xiaoyun . Provably Secure NTRU Instances over Prime Cyclotomic Rings[EB/OL]. https://www.researchgate.net/publication/314071350_Provably_Secure_NTRU_Instances_over_Prime_Cyclotomic_Rings?ev=auth_pub, 2019-7-15.
[12]	YU Yang, XU Guangwu, WANG Xiaoyun . Provably Secure NTRU Encrypt over More General Cyclotomic Rings[R]. Cryptology ePrint Archive, Report 2017/304, 2017.
[13]	ASHAROV G, JAIN A, WICHS D . ultiparty Computation with Low Communication, Computation and Interaction via Threshold FHE[EB/OL]. https://www.researchgate.net/publication/220333428_Multiparty_Computation_with_Low_Communication_Computation_and_Interaction_via_Threshold_FHE, 2019-7-15.
[14]	MICCIANCIO D, REGEV O . Worst-Case to Average-Case Reductions Based on Gaussian Measures[J]. SIAM Journal on Computing, 2007,37(1):267-302.
[15]	ALBRECHT M, BAI S, DUCAS L A . Subfield Lattice Attack on Overstretched NTRU Assumptions[EB/OL]. http://link.springer.com/content/pdf/10.1007/978-3-662-53018-4_6.pdf, 2019-7-15.