Survey on LWE-based Fully Homomorphic Encryption Scheme

doi:10.3969/j.issn.1671-1122.2015.01.006

Abstract

Abstract:

This paper introduced history and current situation in fully homomorphic encryption (FHE). We analyzed the idea and methods of constructing FHE scheme, and classified the main techniques that are used to construct FHE scheme. Then this paper summarized LWE-based fully homomorphic encryption scheme, firstly, a somewhat homomorphic encryption schemes is constructed by using a re-linearization technique, secondly, dimension-modulus reduction technique is utilized to reduce the size of ciphertexts and decryption circuit complexity, combined bootstrappable technology to achieve full homomorphic encryption. It mainly analyzed three aspects which from noise problem, parameters and performance as well as security. At last we compared with the fully homomorphic encryption over the integers, which from two aspects of performance and security, and point out the essence of the way to construct FHE and the main problems that need to be solved at present. We hope this paper can provide guidance for further in-depth study of fully homomorphic encryption.

Key words: fully homomorphic encryption, LWE, noise, parameters and performance, security

CLC Number:

TP309

LV Hai-feng, DING Yong, DAI Hong-yan, LI Xin-guo. Survey on LWE-based Fully Homomorphic Encryption Scheme[J]. Netinfo Security, 2015, 15(1): 32-38.

Figures/Tables 2

References 36

[1]	GENTRY C.Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 41st annual ACM symposium on Theory of computing. Bethesda, MD, USA; ACM. 2009: 169-178.
[2]	RIVEST R L, ADLEMAN L, DERTOUZOS M L.On data banks and privacy homomorphisms[J]. Foundations of secure computation, 1978,4(11): 169-180.
[3]	MICCIANCIO D.A first glimpse of cryptography's Holy Grail[J]. Communications of the ACM, 2010, 53(3): 96-96.
[4]	RIVEST R L, SHAMIR A, ADLEMAN L.A method for obtaining digital signatures and public-key cryptosystems[J]. Communication ACM, 1978, 21(2): 120-126.
[5]	GOLDWASSER S, MICALI S.Probabilistic encryption[J]. Journal of computer and system sciences, 1984, 28(2): 270-299.
[6]	ELGAMAL T.A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Trans Inf Theory, 1985, 31(4): 469-472.
[7]	PAILLIER P.Public-Key Cryptosystems Based on Composite Degree Residuosity Classes[C]//STERN J. Advances in Cryptology—EUROCRYPT'99. Springer Berlin Heidelberg. 1999: 223-238.
[8]	Damgård I, JURIK M.A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System[C]//Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography. Springer-Verlag. 2001: 119-136.
[9]	AJTAI M S, DWORK C.A public-key cryptosystem with worst-case/average-case equivalence[C]//Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. El Paso, Texas, United States; ACM. 1997: 284-293.
[10]	REGEV O.New lattice-based cryptographic constructions[J]. JACM, 2004, 51(6): 899-942.
[11]	REGEV O.On lattices, learning with errors, random linear codes, and cryptography[C]//Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. Baltimore, MD, USA; ACM. 2005: 84-93.
[12]	COHEN J D, FISCHER M J.A robust and verifiable cryptographically secure election scheme[C]//Proceedings of the 26th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 1985: 372-382.
[13]	NACCACHE D, STERN J.A new public key cryptosystem based on higher residues[C]//Proceedings of the 5th ACM conference on Computer and communications security. San Francisco, California, United States;ACM. 1998: 59-66.
[14]	OKAMOTO T, UCHIYAMA S.A new public-key cryptosystem assecure as factoring[C]//NYBERG K. Advances in Cryptology.
[15]	BONEH D, GOH E J, NISSIM K.Evaluating 2-DNF Formulas on Ciphertexts[C]//KILIAN J. Theory of Cryptography. Springer Berlin Heidelberg. 2005: 325-341.
[16]	GENTRY C, HALEVI S, VAIKUNTANATHAN V.A Simple BGN-Type Cryptosystem from LWE[C]//GILBERT H. Advances in Cryptology-EUROCRYPT 2010. Springer Berlin Heidelberg. 2010:506-522.
[17]	ISHAI Y, PASKIN A.Evaluating Branching Programs on Encrypted Data[C]//VADHAN S. Theory of Cryptography. Springer Berlin Heidelberg. 2007: 575-594.
[18]	MELCHOR C, GABORIT P, HERRANZ J.Additively Homomorphic Encryption with d-Operand Multiplications[C]//RABIN T. Advances in Cryptology-CRYPTO 2010. Springer Berlin Heidelberg. 2010: 138-154.
[19]	SANDER T, YOUNG A, YUNG M.Non-Interactive CryptoComputing For NC1[C]//Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 1999: 554-556.
[20]	ALBRECHT M, FARSHIM P, FAUG RE J-C, et al. Polly Cracker, Revisited[C]//LEE D, WANG X. Advances in Cryptology-ASIACRYPT 2011. Springer Berlin Heidelberg. 2011: 179-196.
[21]	YAO A C.Protocols for secure computations[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 1982: 160-164.
[22]	VAIKUNTANATHAN V.Computing Blindfolded: New Developments in Fully Homomorphic Encryption[C]//Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 2011: 5-16.
[23]	GOLDWASSER S, KALAI Y, POPA R, et al.How to Run Turing Machines on Encrypted Data[C]//CANETTI R, GARAY J. Advances in Cryptology-CRYPTO 2013. Springer Berlin Heidelberg. 2013: 536-553.
[24]	GOLDWASSER S, KALAI Y, POPA R A, et al.Reusable garbled circuits and succinct functional encryption[C]//Proceedings of the 45th annual ACM symposium on Symposium on theory of computing. Palo Alto, California, USA; ACM. 2013: 555-564.
[25]	VAN DIJK M, GENTRY C, HALEVI S, et al.Fully Homomorphic Encryption over the Integers[C]//GILBERT H. Advances in Cryptology -EUROCRYPT 2010. Springer Berlin/Heidelberg. 2010: 24-43.
[26]	SMART N P, VERCAUTEREN F.Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes[C]//NGUYEN P, POINTCHEVAL D. Public Key Cryptography-PKC 2010. Springer Berlin Heidelberg. 2010: 420-443.
[27]	STEHL D, STEINFELD R.Faster Fully Homomorphic Encryption[C]//ABE M. Advances in Cryptology-ASIACRYPT 2010. Springer Berlin Heidelberg. 2010: 377-394.
[28]	BRAKERSKI Z, VAIKUNTANATHAN V.Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[C]//ROGAWAY P. Advances in Cryptology-CRYPTO 2011. Springer Berlin Heidelberg. 2011: 505-524.
[29]	CORON J-S, MANDAL A, NACCACHE D, et al.Fully Homomorphic Encryption over the Integers with Shorter Public Keys[C]//ROGAWAY P. Advances in Cryptology-CRYPTO 2011. Springer Berlin Heidelberg. 2011: 487-504.
[30]	CORON J S, NACCACHE D, TIBOUCHI M.Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers[C]//POINTCHEVAL D, JOHANSSON T. Advances in Cryptology-EUROCRYPT 2012. Springer Berlin Heidelberg. 2012: 446-464.
[31]	BRAKERSKI Z, VAIKUNTANATHAN V.Efficient Fully Homomorphic Encryption from (Standard) LWE[C]//Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society. 2011: 97-106.
[32]	BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V.(Leveled) fully homomorphic encryption without bootstrapping[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Cambridge, Massachusetts; ACM. 2012: 309-325.
[33]	BRAKERSKI Z.Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[C]//SAFAVI-NAINI R, CANETTI R. Advances in Cryptology-CRYPTO 2012. Springer Berlin Heidelberg.2012: 868-886.
[34]	L PEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C]//Proceedings of the 44th symposium on Theory of Computing. New York, New York, USA; ACM. 2012: 1219-1234.
[35]	GENTRY C, SAHAI A, WATERS B.Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based[C]//CANETTI R, GARAY J. Advances in Cryptology -CRYPTO 2013. Springer Berlin Heidelberg. 2013: 75-92.
[36]	LYUBASHEVSKY V, PEIKERT C, REGEV O.On Ideal Lattices and Learning with Errors over Rings[C]//GILBERT H. Advances in Cryptology-EUROCRYPT 2010. Springer Berlin Heidelberg. 2010: 1-23.