zbMATH — the first resource for mathematics

Collision-free hashing from lattice problems. (English) Zbl 1343.94055
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 30-39 (2011).
Summary: M. Ajtai [in: Proceedings of the 28th annual ACM symposium on the theory of computing, STOC ’96. New York, NY: ACM. 99–108 (1996; Zbl 0921.11071)] described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same construction can also be used to obtain collision-free hashing. This paper contains a self-contained proof sketch of Ajtai’s result.
For the entire collection see [Zbl 1220.68005].

94A60 Cryptography
11H06 Lattices and convex bodies (number-theoretic aspects)
PDF BibTeX Cite
Full Text: DOI
[1] Ajtai, M.: Generating Hard Instances of Lattice Problems. In: 28th ACM Symposium on Theory of Computing, Philadelphia, pp. 99–108 (1996) · Zbl 0921.11071
[2] Carter, L., Wegman, M.: Universal Classes of Hash Functions. J. Computer and System Sciences 18, 143–154 (1979) · Zbl 0412.68090
[3] Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. SIAM J. on Computing 22(6), 1163–1175 (1993) · Zbl 0795.94011
[4] Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A Pseudorandom Generator from any One-way Function. SIAM J. on Computing 28(4), 1364–1396 (1990); Combines papers of Impagliazzo et al. (21st STOC, 1989) and Håstad (22nd STOC, 1990) · Zbl 0940.68048
[5] Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring Polynomials with Rational Coefficients. Mathematische Annalen 261, 515–534 (1982) · Zbl 0488.12001
[6] Schnorr, C.P.: A more efficient algorithm for a lattice basis reduction. Journal of Algorithms 9, 47–62 (1988) · Zbl 0825.11015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.