Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

  • Conference paper

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

Included in the following conference series:

Abstract

The generalized knapsack function is defined asfa(x) = ∑ iai ·xi, where a = (a1,...,am) consists ofm elements from some ringR, and x = (x1,...,xm) consists ofm coefficients from a specified subsetS ⊆ R. Micciancio (FOCS 2002) proposed a specific choice of the ringR and subsetS for which inverting this function (for randoma,x) is at least as hard as solving certain worst-case problems on cyclic lattices.

We show that for a different choice ofS ⊂R, the generalized knapsack function is in factcollision-resistant, assuming it is infeasible to approximate the shortest vector inn-dimensional cyclic lattices up to factors\(\tilde{O}(n)\). For slightly larger factors, we even get collision-resistance foranym≥ 2. This yieldsvery efficient collision-resistant hash functions having key size and time complexity almost linear in the security parametern. We also show that alteringS is necessary, in the sense that Micciancio’s original function isnot collision-resistant (nor even universal one-way).

Our results exploit an intimate connection between the linear algebra ofn-dimensional cyclic lattices and the ring ℤ[α]/(αn − 1), and crucially depend on the factorization ofαn-1 into irreducible cyclotomic polynomials. We also establish a new bound on the discrete Gaussian distribution over general lattices, employing techniques introduced by Micciancio and Regev (FOCS 2004) and also used by Micciancio in his study of compact knapsacks.

Part of this work done while at MIT CSAIL.

The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI:10.1007/978-3-540-32732-5_32

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: Proc. 28th Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 99–108 (1996)

    Google Scholar 

  2. Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: Proc. 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 10–19 (1998)

    Google Scholar 

  3. Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proc. 29th Annual ACM Symposium on Theory of Computing (STOC 1997), pp. 284–293 (1997)

    Google Scholar 

  4. Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Computer and System Sciences 54(2), 317–331 (1997)

    Article MathSciNet MATH  Google Scholar 

  5. Cai, J.-Y., Nerurkar, A.: Approximating the SVP to within a factor (1 + 1/dimε) is NP-hard under randomized reductions. Jounal of Computer and System Sciences 59(2), 221–239 (1999)

    Article MATH  Google Scholar 

  6. Cai, J.-Y., Nerurkar, A.P.: An improved worst-case to average-case connection for lattice problems. In: Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS 1997), p. 468 (1997)

    Google Scholar 

  7. Dinur, I., Kindler, G., Safra, S.: Approximating-CVP to within almostpolynomial factors is NP-hard. In: Proc. 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 99–111. IEEE Computer Society, Los Alamitos (1998)

    Google Scholar 

  8. Dummit, D.S., Foote, R.M.: Abstract Algebra, 2nd edn. Prentice Hall, Upper Saddle River (1999)

    MATH  Google Scholar 

  9. Genarro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM J. Computing 35(1), 217–246 (2005)

    Article MathSciNet MATH  Google Scholar 

  10. Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Electronic Colloquium on Computational Complexity (ECCC) Report TR96-042 (1996)

    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)

    Chapter  Google Scholar 

  12. Khot, S.: Hardness of approximating the shortest vector problem in lattices. In: Proc. 45th Symposium on Foundations of Computer Science (FOCS 2004), pp. 126–135. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  13. Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. Electronic Colloquium on Computational Complexity (ECCC) Report TR05-142 (2005)

    Google Scholar 

  14. Micciancio, D.: Generalized compact knapsaks, cyclic lattices, and efficient oneway functions from worst-case complexity assumptions. In: Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS (2002)

    Google Scholar 

  15. Micciancio, D.: The shortest vector problem is NP-hard to approximate to within some constant. SIAM J. Computing 30(6), 2008–2035 (March 2001)

    Article MathSciNet MATH  Google Scholar 

  16. Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: a cryptographic perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston, Massachusetts (2002)

    Book MATH  Google Scholar 

  17. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measure, pp. 371–381

    Google Scholar 

  18. Regev, O.: New lattice-based cryptographic constructions. J. ACM 51(6), 899–942 (2004)

    Article MathSciNet MATH  Google Scholar 

  19. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proc. 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pp. 84–93 (2005)

    Google Scholar 

  20. van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam (1981)

    Google Scholar 

  21. Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  22. Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. MIT Computer Science and AI Laboratory (CSAIL), Cambridge, MA

    Chris Peikert

  2. DEAS, Harvard, Cambridge, MA

    Alon Rosen

Authors
  1. Chris Peikert
  2. Alon Rosen

Editor information

Editors and Affiliations

  1. IBM Research, Hawthorne, NY, USA

    Shai Halevi

  2. IBM T.J.Watson Research Center, Hawthorne, NY, USA

    Tal Rabin

Rights and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Peikert, C., Rosen, A. (2006). Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices. In: Halevi, S., Rabin, T. (eds) Theory of Cryptography. TCC 2006. Lecture Notes in Computer Science, vol 3876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11681878_8

Download citation

Publish with us

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