Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Candidate Multilinear Maps from Ideal Lattices

  • Conference paper

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

Abstract

We describe plausible lattice-based constructions with properties that approximate the sought-after multilinear maps in hard-discrete-logarithm groups, and show an example application of such multi-linear maps that can be realized using our approximation. The security of our constructions relies on seemingly hard problems in ideal lattices, which can be viewed as extensions of the assumed hardness of the NTRU function.

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. Agrawal, S., Gentry, C., Halevi, S., Sahai, A.: Sampling discrete gaussians efficiently and obliviously. Cryptology ePrint Archive, Report 2012/714 (2012),http://eprint.iacr.org/

  2. Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  3. Boneh, D., Lipton, R.J.: Algorithms for black-box fields and their application to cryptography (extended abstract). In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 283–297. Springer, Heidelberg (1996)

    Google Scholar 

  4. Boneh, D., Silverberg, A.: Applications of multilinear forms to cryptography. Contemporary Mathematics 324, 71–90 (2003)

    Article MathSciNet  Google Scholar 

  5. Coppersmith, D., Shamir, A.: Lattice attacks on ntru. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 52–61. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  6. Gentry, C.: Key recovery and message attacks on ntru-composite. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 182–194. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  7. 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)

    Chapter  Google Scholar 

  8. Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. Cryptology ePrint Archive, Report 2012/610 (2012),http://eprint.iacr.org/

  9. Garg, S., Gentry, C., Halevi, S., Sahai, A., Waters, B.: Attribute-based encryption for circuits from multilinear maps. Cryptology ePrint Archive, Report 2013/128 (2013),http://eprint.iacr.org/

  10. Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: STOC (2013)

    Google Scholar 

  11. Goldwasser, S., Kalai, Y., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Succinct functional encryption and applications: Reusable garbled circuits and beyond. In: STOC (2013)

    Google Scholar 

  12. Gentry, C., Szydlo, M.: Cryptanalysis of the revised ntru signature scheme. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 299–320. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  13. Gorbunov, S., Vaikuntanathan, V., Wee, H.: Predicate encryption for circuits. In: STOC (2013)

    Google Scholar 

  14. Howgrave-Graham, N., Szydlo, M.: A method to solve cyclotomic norm equations. In: Buell, D.A. (ed.) ANTS 2004. LNCS, vol. 3076, pp. 272–279. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  15. Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: Ntrusign: Digital signatures using the ntru lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  16. Hoffstein, J., Kaliski, B.S., Lieman, D.B., Robshaw, M.J.B., Yin, Y.L.: Secure user identification based on constrained polynomials. US Patent 6,076,163 (2000)

    Google Scholar 

  17. 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 

  18. Hoffstein, J., Pipher, J., Silverman, J.H.: Nss: An ntru lattice-based signature scheme. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 211–228. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  19. Joux, A.: A one round protocol for tripartite diffie-hellman. In: Bosma, W. (ed.) ANTS 2000. LNCS, vol. 1838, pp. 385–394. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

  21. Nguyên, P.Q., Regev, O.: Learning a parallelepiped: Cryptanalysis of ggh and ntru signatures. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 271–288. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  22. Papamanthou, C., Tamassia, R., Triandopoulos, N.: Optimal authenticated data structures with multilinear forms. In: Joye, M., Miyaji, A., Otsuka, A. (eds.) Pairing 2010. LNCS, vol. 6487, pp. 246–264. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  23. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84–93 (2005)

    Google Scholar 

  24. Rothblum, R.D.: On the circular security of bit-encryption. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 579–598. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  25. Rückert, M., Schröder, D.: Aggregate and verifiably encrypted signatures from multilinear maps without random oracles. In: Park, J.H., Chen, H.-H., Atiquzzaman, M., Lee, C., Kim, T.-h., Yeo, S.-S. (eds.) ISA 2009. LNCS, vol. 5576, pp. 750–759. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  26. Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairing. In: SCIS 2000, Okinawa, Japan (January 2000)

    Google Scholar 

  27. Szydlo, M.: Hypercubic lattice reduction and analysis of ggh and ntru signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 433–448. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. UCLA, USA

    Sanjam Garg

  2. IBM Research, USA

    Craig Gentry & Shai Halevi

Authors
  1. Sanjam Garg
  2. Craig Gentry
  3. Shai Halevi

Editor information

Editors and Affiliations

  1. Dept. of Electrical and Information Technology, Lund University, P.O. Box 118, 221 00, Lund, Sweden

    Thomas Johansson

  2. Départment d’informatique, Ecole normale supérieure, 45, rue d’Ulm, 75230, Paris Cedex 05, France

    Phong Q. Nguyen

Rights and permissions

Copyright information

© 2013 International Association for Cryptologic Research

About this paper

Cite this paper

Garg, S., Gentry, C., Halevi, S. (2013). Candidate Multilinear Maps from Ideal Lattices. In: Johansson, T., Nguyen, P.Q. (eds) Advances in Cryptology – EUROCRYPT 2013. EUROCRYPT 2013. Lecture Notes in Computer Science, vol 7881. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38348-9_1

Download citation

Publish with us

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