Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient Public Key Encryption Based on Ideal Lattices

(Extended Abstract)

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 5912))

Abstract

We describe public key encryption schemes with security provably based on the worst case hardness of the approximate Shortest Vector Problem in some structured lattices, called ideal lattices. Under the assumption that the latter is exponentially hard to solve even with a quantum computer, we achieve CPA-security against subexponential attacks, with (quasi-)optimal asymptotic performance: if n is the security parameter, both keys are of bit-length \({\widetilde{O}}(n)\) and the amortized costs of both encryption and decryption are \({\widetilde{O}}(1)\) per message bit. Our construction adapts the trapdoor one-way function of Gentryet al. (STOC’08), based on the Learning With Errors problem, to structured lattices. Our main technical tools are an adaptation of Ajtai’s trapdoor key generation algorithm (ICALP’99) and a re-interpretation of Regev’s quantum reduction between the Bounded Distance Decoding problem and sampling short lattice vectors.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of STOC 1996, pp. 99–108. ACM, New York (1996)

    Google Scholar 

  2. Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 1–9. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  3. Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of STOC 1997, pp. 284–293. ACM, New York (1997)

    Google Scholar 

  4. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of STOC 2001, pp. 601–610. ACM, New York (2001)

    Google Scholar 

  5. Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. In: STACS 2009. LNCS. Springer, Heidelberg (2009)

    Google Scholar 

  6. Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6, 1–13 (1986)

    Article MATH MathSciNet  Google Scholar 

  7. Blake, I.F., Gao, S., Mullin, R.C.: Explicit factorization of\(x^{2^k} + 1\) overFp with prime\(p \equiv 3 \bmod 4\). App. Alg. in Eng., Comm. and Comp. 4, 89–94 (1992)

    Article MathSciNet  Google Scholar 

  8. Fiat, A., Shamir, A.: How to prove yourself – practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)

    Google Scholar 

  9. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC 2008, pp. 197–206. ACM, New York (2008)

    Google Scholar 

  10. Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. II. Cambridge University Press, Cambridge (2001)

    MATH  Google Scholar 

  11. Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 112–131. Springer, Heidelberg (1997)

    Google Scholar 

  12. Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  13. Holenstein, T., Maurer, U., Sjödin, J.: Complete classification of bilinear hard-core functions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 73–91. Springer, Heidelberg (2004)

    Google Scholar 

  14. Kawachi, A., Tanaka, K., Xagawa, K.: Concurrently secure identification schemes based on the worst-case hardness of lattice problems. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 372–389. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  15. Lyubashevsky, V.: Lattice-based identification schemes secure under active attacks. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 162–179. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  16. Lyubashevsky, V.: Towards Practical Lattice-Based Cryptography. PhD thesis, University of California, San Diego (2008)

    Google Scholar 

  17. Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  18. Lyubashevsky, V., Micciancio, D.: Asymptotically efficient lattice-based digital signatures. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 37–54. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  19. Lyubashevsky, V., Micciancio, D.: On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Halevi, S. (ed.) Crypto 2009. LNCS, vol. 5677, pp. 450–461. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  20. Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity 16(4), 365–411 (2007)

    Article MATH MathSciNet  Google Scholar 

  21. Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective. Kluwer Academic Press, Dordrecht (2002)

    MATH  Google Scholar 

  22. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007)

    Article MATH MathSciNet  Google Scholar 

  23. Micciancio, D., Regev, O.: Lattice-based Cryptography. In: Post-Quantum Cryptography. Springer, Heidelberg (2008)

    Google Scholar 

  24. Micciancio, D., Vadhan, S.: Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 282–298. Springer, Heidelberg (2003)

    Google Scholar 

  25. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)

    MATH  Google Scholar 

  26. Pan, V.Y.: Structured matrices and polynomials, unified superfast algorithms. Springer and Birkhäuser (2001)

    Google Scholar 

  27. Peikert, C.: Limits on the hardness of lattice problems in ℓp norms. Computational Complexity 2(17), 300–351 (2008)

    Article MathSciNet  Google Scholar 

  28. Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: Proceedings of STOC 2009, pp. 333–342. ACM, New York (2009)

    Google Scholar 

  29. Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145–166. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  30. Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008)

    Google Scholar 

  31. Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Proceedings of STOC 2008, pp. 187–196. ACM, New York (2008)

    Google Scholar 

  32. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. Extended version of [33], May 2 (2009),http://www.cs.tau.ac.il/~odedr/

  33. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of STOC 2005, pp. 84–93. ACM, New York (2005)

    Google Scholar 

  34. Rosen, A., Segev, G.: Chosen-ciphertext security via correlated products. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 419–436. Springer, Heidelberg (2009)

    Google Scholar 

  35. Schnorr, C.P.: A hierarchy of polynomial lattice basis reduction algorithms. Theor. Comput. Sci 53, 201–224 (1987)

    Article MATH MathSciNet  Google Scholar 

  36. Schnorr, C.P.: Hot topics of LLL and lattice reduction. In: The Proceedings of the LLL+25 conference (to appear, 2009)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CNRS/Department of Mathematics and Statistics, University of Sydney, NSW 2006, Australia

    Damien Stehlé

  2. Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, NSW 2109, Australia

    Damien Stehlé & Ron Steinfeld

  3. Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Japan

    Keisuke Tanaka & Keita Xagawa

Authors
  1. Damien Stehlé
  2. Ron Steinfeld
  3. Keisuke Tanaka
  4. Keita Xagawa

Editor information

Editors and Affiliations

  1. Information Technology R&D Center, Mitsubishi Electric Corporation, 247-8501, Kamakura, Kanagawa, Japan

    Mitsuru Matsui

Rights and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K. (2009). Efficient Public Key Encryption Based on Ideal Lattices. In: Matsui, M. (eds) Advances in Cryptology – ASIACRYPT 2009. ASIACRYPT 2009. Lecture Notes in Computer Science, vol 5912. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10366-7_36

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp