Generalized compact knapsacks are collision resistant. (English) Zbl 1133.68353

Lyubashevsky, Vadim; Micciancio, Daniele

Bugliesi, Michele (ed.) et al., Automata, languages and programming. 33rd international colloquium, ICALP 2006, Venice, Italy, July 10–14, 2006. Proceedings, Part II. Berlin: Springer (ISBN 978-3-540-35907-4/pbk). Lecture Notes in Computer Science 4052, 144-155 (2006).

Summary: In [D. Micciancio, “Generalized compact knapsacks, cyclic lattices, and efficient one-way functions”, Comput. Complexity 16, No. 4, 365–411 (2007; Zbl 1133.68024)], it was proved that solving the generalized compact knapsack problem on the average is as hard as solving certain worst-case problems for cyclic lattices. This result immediately yielded very efficient one-way functions whose security was based on worst-case hardness assumptions. In this work, we show that, while the function proposed by Micciancio is not collision resistant, it can be easily modified to achieve collision resistance under essentially the same complexity assumptions on cyclic lattices. Our modified function is obtained as a special case of a more general result, which yields efficient collision-resistant hash functions based on the worst-case hardness of various new problems. These include new problems from algebraic number theory as well as classic lattice problems (e.g., the shortest vector problem) over ideal lattices, a class of lattices that includes cyclic lattices as a special case.
For the entire collection see [Zbl 1113.68003].

MSC:

68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25	Analysis of algorithms and problem complexity
94A60	Cryptography

Citations:

Zbl 1133.68024

Software:

NTRU