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). STOC '96,pp. 99--108.
2. M. Ajtai and C. Dwork.A public key cryptosystem with worst-case / average-case equivalence. STOC '97, pp. 284--293.
3. J.H. An, Y. Dodis, and T. Rabin.On the security of joint signature and encryption. Eurocrypt '02, LNCS 2332,pp. 83--107.
4. F. Armknecht and A.-R. Sadeghi.A new approach for algebraically homomorphic encryption. Eprint 2008/422.
5. L. Babai.On Lovász's lattice reduction and the nearest lattice point problem. Combinatorica 6 (1986), 1--14.
6. D. Barrington.Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. STOC '86,pp. 1--5.
7. D. Beaver.Minimal-latency secure function evaluation. Eurocrypt '00, pp. 335--350.
8. J. Benaloh. Verifiable secret-ballot elections. Ph.D. thesis, Yale Univ., Dept. of Comp. Sci., 1988.
9. J. Black, P. Rogaway, and T. Shrimpton. Encryption-scheme security in the presence of key-dependent messages. SAC '02, LNCS 2595,pp. 62--75.
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. D. Boneh, S. Halevi, M. Hamburg, and R. Ostrovsky. Circular-Secure Encryption from Decision Diffie-Hellman. Crypto '08, LNCS 5157,pp. 108--125.
13. D. Boneh and R. Lipton.Searching for Elements in Black-Box Fields and Applications. Crypto '96, LNCS 1109,pp. 283--297.
14. J. Boyar, R. Peralta, and D. Pochuev.On the Multiplicative Complexity of Boolean Functions over the Basis (∧,øplus,1).Theor. Comput. Sci. 235(1), pp. 43--57, 2000.
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. W. van Dam, S. Hallgren, and L. Ip. Quantum Algorithms for Some Hidden Shift Problems. SIAM J. Comput., v. 36., no. 3, pp. 763--778, 2006.
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. S. Goldwasser and S. Micali.Probabilistic encryption and how to play mental poker keeping secret all partial information. STOC '82,pp. 365--377.
24. S. Halevi and H. Krawczyk. Security under key-dependent inputs. ACM CCS '07.
25. J. Hoffstein, J. Silverman, and J. Pipher.NTRU: A Ring Based Public Key Cryptosystem. In Proc. of ANTS '98, LNCS 1423,pages 267--288.
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. T. Matsumoto, K. Kato, and H. Imai. Speeding up secret computations with insecure auxiliary devices. Crypto '88, LNCS 403,pp. 497--506.
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. J. Merkle. Multi-round passive attacks on server-aided RSA protocols. ACM CCS '00,pp. 102--107.
39. D. Micciancio. Improving Lattice Based Cryptosystems Using the Hermite Normal Form. CaLC '01, LNCS 2146, pp. 126--145.
40. D. Micciancio. Improved cryptographic hash functions with worst-case / average-case connection. STOC '02,pp. 609--618.
41. D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. FOCS '02,pp. 356--365.
42. D. Naccache and J. Stern.A New Public-Key Cryptosystem Based on Higher Residues. ACM CCS '98.
43. P.Q. Nguyen and I. Shparlinski. On the Insecurity of Some Server-Aided RSA Protocol. Asiacrypt '01, LNCS 2248, pp. 21--35.
44. P.Q. Nguyen and J. Stern. The Beguin-Quisquater server-aided RSA protocol from Crypto '95 is not secure. Asiacrypt '98,pp. 372--379.
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. C. Peikert and A. Rosen. Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors. STOC '07,pp. 478--487.
50. C. Peikert and B. Waters.Lossy Trapdoor Functions and Their Applications. STOC '08,pp. 187--196.
51. B. Pfitzmann and M. Waidner. Attacks on protocols for server-aided RSA computation. Eurocrypt '92, LNCS 658,pp. 153--162.
52. M. Prabhakaran and M. Rosulek. Homomorphic Encryption with CCA Security. ICALP '08.
53. O. Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. STOC '05,pp. 84--93.
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. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. In Comm. of the ACM, 21:2,pages 120--126,1978.
56. T. Sander, A. Young, and M. Yung. Non-interactive cryptocomputing for NC1. FOCS '99,pp. 554--567,1999.
57. C.P. Schnorr. A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms. Theoretical Computer Science, 53(2-3):201--224, 1987.
58. D.R. Stinson. Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. Mathematics of Computation,vol. 71, no. 237, pages 379--391, 2001.

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption