The Analysis of Constructing Fully Homomorphic Encryption over Integers

Abstract:

Fully homomorphic encryption has long been regarded as cryptography’s prized “holy grail”–extremely useful yet rather elusive. At 2010 van Dijk et al. described a fully homomorphic encryption scheme over theintegers. The main appeal of this scheme is its conceptual simplicity. This simplicity comes at the expense of a public key size inÕ(λ¹⁰) which is too large for any practical system. The construction is based on the hardness of the approximate-GCD problem. At 2011 Coron et al. reduced the public key size to about Õ(λ⁷) by encrypting with a quadratic form in the public key elements, instead of a linear form. This scheme is based on a stronger variant of the approximate-GCD problem. An implementation of the full scheme was obtained with a 802MB public key. At 2012 Coron et al. described a compression technique that reduces the public key size to aboutÕ(λ⁵). This variant remains semantically secure, but in the random oracle model.A level of efficiency very similar to above scheme was obtained but with a 10.1MB public key instead of a 802MB one.Coron et al. also described a new modulus switching technique for the DGHV scheme that enables to use the new FHE framework without bootstrapping from Brakerski, Gentry and Vaikuntanathan with theDGHV scheme. At present asymptotics of FHE over integers are much better.

• Periodical: Advanced Materials Research (Volumes 989-994)
• Pages: 4780-4784
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.989-994.4780
• Online since: July 2014
• Authors: Lei Jin*, Xin Xia Song
• Keywords: Approximate-GCD Problem, Encryption, Fully Homomorphic Encryption

References

[1] W. Diffieand M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, vol. IT-22, p.644–654, (1976).

DOI: 10.1109/tit.1976.1055638

[2] R. L. Rivest, A. Shamir, and L. M. Adleman, A method for obtaining digital signatures and public-key cryptosystems(reprint), Commun. ACM, vol. 26, no. 1, p.96–99, (1983).

DOI: 10.1145/357980.358017

[3] C. Gentry. Fully homomorphic encryption using ideal lattices. STOC, 2009, 169–178.

[4] M. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, Fully homomorphic encryption over the integers, EUROCRYPT, 2010, 24–43.

DOI: 10.1007/978-3-642-13190-5_2

[5] J.S. Coron,A. Mandal,D. Naccache and M. Tibouchi, Fully Homomorphic Encryption.

[6] Integers withShorter Public Keys. CRYPTO, 2011, 6841: 487-504.

[7] J.S. Coron, D. Naccache and M. Tibouchi. Public key compression and modulus switching for fully homomorphic encryption over the integers. EUROCRYPT, 2012, 7237: 446–464.

DOI: 10.1007/978-3-642-29011-4_27

[8] C. Gentry, A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University, (2009).

[9] Enderton, Herbert. A mathematical introduction to logic(2nded. ), Boston, Academic Press, (2001).

[10] N.P. Smart,F. Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes. PKC 2010, 6056: 420-443.

DOI: 10.1007/978-3-642-13013-7_25

[11] D. Stehle,R. Steinfeld, Faster fully homomorphic encryption. ASIACRYPT 2010, 2010, 6477: 377-394.

DOI: 10.1007/978-3-642-17373-8_22

[12] C. Gentry, S. Halevi, Implementing Gentry's fully homomorphic encryption scheme. EUROCRYPT 2011, 6632: 129-148.

DOI: 10.1007/978-3-642-20465-4_9

[13] Z. Brakerski,V. Vaikuntanathan. Fully Homomorphic Encryption from Ring-LWE and security for Key Dependent Messages, CRYPTO 2011, 6841: 505-524.

DOI: 10.1007/978-3-642-22792-9_29

[14] C. Gentry,S. Halevi N.P. Smart. Better Bootstrapping in Fully Homomorphic Encryption, Cryptology ePrint Archive, 2011, Report 2011/680.

[15] C. Gentry,S. Halevi. Fully Homomorphic Encryption without Squashing using depth-3 arithmetic circuits, FOCS 2011, 107-109.

DOI: 10.1109/focs.2011.94

[16] N. Howgrave-Graham. Approximate integer common divisors. CaLC'01, 2001, 2146: 51–66.

DOI: 10.1007/3-540-44670-2_6

[17] J. C. Lagarias. The computational complexity of simultaneous diophantine approximation problems. SIAM J. Comput., 1985, 14(1): 196–209.

DOI: 10.1137/0214016

[18] P. Q. Nguyen, J. Stern. The two faces of lattices in cryptology. Cryptography and Lattices, CaLC'01, 2001, 2146: 146–180.

DOI: 10.1007/3-540-44670-2_12

[19] D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities.J. Cryptology, 1997, 10(4): 233–260.

DOI: 10.1007/s001459900030

[20] V. Vaikuntanathan. Computing blindfolded: New developments in Fully Homomorphic Encryption, FOCS 2011, 5-16.

DOI: 10.1109/focs.2011.98

[21] Z. Brakerski, C. Gentry and V. Vaikuntanathan, Fully Homomorphic Encryption without Bootstrapping. Cryptology ePrint Archive, Report 2011/277.

DOI: 10.1145/2090236.2090262