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

The generalized knapsack function is defined as

f

a

(

x

) = ∑ 

i

a

i

·

x

i

, where a = (a

1

,...,a

m

) consists of

m

elements from some ring

R

, and x = (x

1

,...,x

m

) consists of

m

coefficients from a specified subset

S

 ⊆ 

R

. Micciancio (FOCS 2002) proposed a specific choice of the ring

R

and subset

S

for which inverting this function (for random

a,x

) is at least as hard as solving certain worst-case problems on cyclic lattices.

We show that for a different choice of

S

⊂

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

anym

≥ 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 ℤ[

α

]/(

α

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.