Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. (English) Zbl 1112.94020

Halevi, Shai (ed.) et al., Theory of cryptography. Third theory of cryptography conference, TCC 2006, New York, NY, USA, March 4–7, 2006. Proceedings. Berlin: Springer (ISBN 3-540-32731-2/pbk). Lecture Notes in Computer Science 3876, 145-166 (2006).
Summary: The generalized knapsack function is defined as \(f_a(x) = \sum_i a_i\cdot x_i\), where \(a = (a_1,\ldots,a_m)\) consists of \(m\) elements from some ring \(R\), and \(x = (x_1,\ldots,x_m)\) consists of \(m\) coefficients from a specified subset \(S \subseteq R\). Micciancio (FOCS 2002) proposed a specific choice of the ring \(R\) and subset \(S\) for which inverting this function (for random \(\mathbf a\), \(\mathbf x\)) is at least as hard as solving certain worst-case problems on cyclic lattices.
We show that for a different choice of \(S \subset R\), the generalized knapsack function is in fact collision-resistant, assuming it is infeasible to approximate the shortest vector in \(n\)-dimensional cyclic lattices up to factors \(\tilde O(n)\). For slightly larger factors, we even get collision-resistance for any \(m \geq 2\). This yields very efficient collision-resistant hash functions having key size and time complexity almost linear in the security parameter \(n\). We also show that altering \(S\) is necessary, in the sense that Micciancio’s original function is not collision-resistant (nor even universal one-way).
Our results exploit an intimate connection between the linear algebra of \(n\)-dimensional cyclic lattices and the ring \(\mathbb Z[\alpha]/(\alpha^n-1)\), and crucially depend on the factorization of \(\alpha^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.
For the entire collection see [Zbl 1097.94002].


94A60 Cryptography
Full Text: DOI