Fully homomorphic encryption using ideal lattices

ABSTRACT

We propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt. Our solution comes in three steps. First, we provide a general result -- that, to construct an encryption scheme that permits evaluation of arbitrary circuits, it suffices to construct an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable.

Next, we describe a public key encryption scheme using ideal lattices that is almost bootstrappable.

Lattice-based cryptosystems typically have decryption algorithms with low circuit complexity, often dominated by an inner product computation that is in NC1. Also, ideal lattices provide both additive and multiplicative homomorphisms (modulo a public-key ideal in a polynomial ring that is represented as a lattice), as needed to evaluate general circuits.

Unfortunately, our initial scheme is not quite bootstrappable -- i.e., the depth that the scheme can correctly evaluate can be logarithmic in the lattice dimension, just like the depth of the decryption circuit, but the latter is greater than the former. In the final step, we show how to modify the scheme to reduce the depth of the decryption circuit, and thereby obtain a bootstrappable encryption scheme, without reducing the depth that the scheme can evaluate. Abstractly, we accomplish this by enabling the encrypter to start the decryption process, leaving less work for the decrypter, much like the server leaves less work for the decrypter in a server-aided cryptosystem.

REFERENCES

• 1: M. Ajtai, Generating hard instances of lattice problems (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.99-108, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237838]
• 2: Miklós Ajtai , Cynthia Dwork, A public-key cryptosystem with worst-case/average-case equivalence, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.284-293, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258604]
• 3: Jee Hea An , Yevgeniy Dodis , Tal Rabin, On the Security of Joint Signature and Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.83-107, May 02, 2002
• 4: F. Armknecht and A.-R. Sadeghi.A new approach for algebraically homomorphic encryption. Eprint 2008/422.
• 5: L Babai, On Lova´sz' lattice reduction and the nearest lattice point problem, Combinatorica, v.6 n.1, p.1-13, 1986 [doi>10.1007/BF02579403]
• 6: D A Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.1-5, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12131]
• 7: D. Beaver.Minimal-latency secure function evaluation. Eurocrypt '00, pp. 335--350.
• 8: Josh Daniel Cohen Benaloh, Verifiable secret-ballot elections, Yale University, New Haven, CT, 1987
• 9: John Black , Phillip Rogaway , Thomas Shrimpton, Encryption-Scheme Security in the Presence of Key-Dependent Messages, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, p.62-75, August 15-16, 2002
• 10: M. Blaze, G. Bleumer, and M. Strauss. Divertible protocols and atomic proxy cryptography. Eurocrypt '98, LNCS 1403,pp. 127--144.
• 11: D. Boneh, E.-J. Goh, and K. Nissim.Evaluating 2-DNF formulas on ciphertexts. TCC '05, LNCS 3378,pp. 325--341.
• 12: Dan Boneh , Shai Halevi , Mike Hamburg , Rafail Ostrovsky, Circular-Secure Encryption from Decision Diffie-Hellman, Proceedings of the 28th Annual conference on Cryptology: Advances in Cryptology, August 17-21, 2008, Santa Barbara, CA, USA [doi>10.1007/978-3-540-85174-5_7]
• 13: Dan Boneh , Richard J. Lipton, Algorithms for Black-Box Fields and their Application to Cryptography (Extended Abstract), Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.283-297, August 18-22, 1996
• 14: Joan Boyar , René Peralta , Denis Pochuev, On the multiplicative complexity of Boolean functions over the basis ∧,⊕,1 , Theoretical Computer Science, v.235 n.1, p.43-57, March 17, 2000 [doi>10.1016/S0304-3975(99)00182-6]
• 15: R. Canetti. Personal communication, 2008.
• 16: R. Canetti, H. Krawczyk, and J.B. Nielsen.Relaxing chosen-ciphertext security. Crypto '03,pp. 565--582.
• 17: D. Coppersmith and G. Seroussi. On the minimum distance of some quadratic residue codes. IEEE Trans. Inform. Theory 30 (1984), 407--411.
• 18: Wim van Dam , Sean Hallgren , Lawrence Ip, Quantum Algorithms for Some Hidden Shift Problems, SIAM Journal on Computing, v.36 n.3, p.763-778, August 2006 [doi>10.1137/S009753970343141X]
• 19: I. Damgard and M. Jurik. A Length-Flexible Threshold Cryptosystem with Applications. ACISP '03, LNCS 2727,pp. 350--356.
• 20: T. ElGamal.A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. Crypto '84,pp. 469--472.
• 21: M. Fellows and N. Koblitz. Combinatorial cryptosystems galore! Contemporary Mathematics,v. 168 of Finite Fields: Theory, Applications, and Algorithms, FQ2,pp. 51--61, 1993.
• 22: S. Goldwasser and D. Kharchenko. Proof of plaintext knowledge for the Ajtai-Dwork cryptosystem. TCC 2005,pp. 529--555.
• 23: Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
• 24: Shai Halevi , Hugo Krawczyk, Security under key-dependent inputs, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315303]
• 25: Jeffrey Hoffstein , Jill Pipher , Joseph H. Silverman, NTRU: A Ring-Based Public Key Cryptosystem, Proceedings of the Third International Symposium on Algorithmic Number Theory, p.267-288, June 21-25, 1998
• 26: Y. Ishai and A. Paskin. Evaluating Branching Programs on Encrypted Data. TCC '07.
• 27: A. Kawachi, K. Tanaka, K. Xagawa. Multi-bit cryptosystems based on lattice problems. PKC '07, LNCS 4450,pp. 315--329.
• 28: A.K. Lenstra, H.W. Lenstra, L. Lovász. Factoring polynomials with rational coefficients. Math. Ann. 261(4) (1982) 515--534.
• 29: F. Levy-dit-Vehel and L. Perret. A Polly Cracker system based on satisfiability. In Coding, Crypt. and Comb., Prog. in Comp.Sci. and App. Logic, v. 23, pp. 177--192.
• 30: L. Ly. A public-key cryptosystem based on Polly Cracker,Ph.D. thesis, Ruhr-Universitat Bochum, Germany, 2002.
• 31: L. Ly. Polly two -- a new algebraic polynomial-based public-key scheme.AAECC, 17(3-4), 2006.
• 32: V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. ICALP '06.
• 33: V. Lyubashevky and D. Micciancio. Asymptotically efficient lattice-based digital signatures. TCC '08.
• 34: Tsutomu Matsumoto , Koki Kato , Hideki Imai, Speeding Up Secret Computations with Insecure Auxiliary Devices, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.497-506, August 21-25, 1988
• 35: U. Maurer and D. Raub. Black-Box Extension Fields and the Inexistence of Field-Homomorphic One-Way Permutations. Asiacrypt '07,pp. 427--443.
• 36: C.A. Melchor, G. Castagnos, and P. Gaborit. Lattice-based homomorphic encryption of vector spaces. ISIT '08,pp. 1858--1862.
• 37: C.A. Melchor, P. Gaborit, and J. Herranz. Additive Homomorphic Encryption with t-Operand Multiplications. Eprint 2008/378.
• 38: Johannes Merkle, Multi-round passive attacks on server-aided RSA protocols, Proceedings of the 7th ACM conference on Computer and communications security, p.102-107, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352616]
• 39: Daniele Micciancio, Improving Lattice Based Cryptosystems Using the Hermite Normal Form, Revised Papers from the International Conference on Cryptography and Lattices, p.126-145, March 29-30, 2001
• 40: Daniele Micciancio, Improved cryptographic hash functions with worst-case/average-case connection, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509995]
• 41: Daniele Micciancio, Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.356-365, November 16-19, 2002
• 42: David Naccache , Jacques Stern, A new public key cryptosystem based on higher residues, Proceedings of the 5th ACM conference on Computer and communications security, p.59-66, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288106]
• 43: Phong Q. Nguyen , Igor Shparlinski, On the Insecurity of a Server-Aided RSA Protocol, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.21-35, December 09-13, 2001
• 44: Phong Q. Nguyen , Jacques Stern, The Béguin-Quisquater Server-Aided RSA Protocol from Crypto '95 is not Secure, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.372-379, October 18-22, 1998
• 45: A.M. Odlyzko. The rise and fall of knapsack cryptosystems. In Crypt. and Comp. Num. Th., Proc. Sympos. Appl. Math., vol. 42, AMS, 1990, pp. 75--88.
• 46: T. Okamoto and Uchiyama. A New Public-Key Cryptosystem as Secure as Factoring. Eurocrypt '98, LNCS 1403,pp. 308--318.
• 47: P. Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Eurocrypt '99,pp. 223--238.
• 48: C. Peikert and A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. TCC '06,pp. 145--166.
• 49: Chris Peikert , Alon Rosen, Lattices that admit logarithmic worst-case to average-case connection factors, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250860]
• 50: Chris Peikert , Brent Waters, Lossy trapdoor functions and their applications, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374406]
• 51: B. Pfitzmann and M. Waidner. Attacks on protocols for server-aided RSA computation. Eurocrypt '92, LNCS 658,pp. 153--162.
• 52: Manoj Prabhakaran , Mike Rosulek, Homomorphic Encryption with CCA Security, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part II, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70583-3_54]
• 53: Oded Regev, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060603]
• 54: R. Rivest, L. Adleman, and M. Dertouzos. On data banks and privacy homomorphisms. In Foundations of Secure Computation, pp. 169--180, 1978.
• 55: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 56: Tomas Sander , Adam Young , Moti Yung, Non-Interactive CryptoComputing For NC1, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.554, October 17-18, 1999
• 57: C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, v.53 n.2-3, p.201-224, Aug. 1987 [doi>10.1016/0304-3975(87)90064-8]
• 58: D. R. Stinson, Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem, Mathematics of Computation, v.71 n.237, p.379-391, January 2002 [doi>10.1090/S0025-5718-01-01310-2]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Design, Security, Theory

Keywords:
fully homomorphic encryption