Collision-free hashing from lattice problems

被引：0

作者：

Goldreich O.

Goldwasser S.

Halevi S.

机构：

来源：

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 2011年 / 6650 LNCS卷

关键词：

Collision-Resistent Hashing; Integer Lattices; One-EWay Functions; Worst-Case to Average-Case Reductions;

D O I：

10.1007/978-3-642-22670-0_5

中图分类号：

学科分类号：

摘要：

In 1995, Ajtai 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. © 2011 Springer-Verlag Berlin Heidelberg.

引用

页码：30 / 39

页数：9

共 6 条

[1]

Ajtai M., Generating hard instances of lattice problems, 28th ACM Symposium on Theory of Computing, pp. 99-108, (1996)

[2]

Carter L., Wegman M., Universal classes of hash functions, J. Computer and System Sciences, 18, pp. 143-154, (1979)

[3]

Goldreich O., Krawczyk H., Luby M., On the existence of pseudorandom generators, SIAM J. on Computing, 22, 6, pp. 1163-1175, (1993)

[4]

Hastad J., Impagliazzo R., Levin L.A., Luby M., A pseudorandom generator from any one-way function, SIAM J. on Computing, 28, 4, pp. 1364-1396, (1990)

[5]

Lenstra A.K., Lenstra H.W., Lovasz L., Factoring polynomials with rational coefficients, Mathematische Annalen, 261, pp. 515-534, (1982)

[6]

Schnorr C.P., A more efficient algorithm for a lattice basis reduction, Journal of Algorithms, 9, pp. 47-62, (1988)

← 1 →