Ideal-SVP ⇒ Ring-SIS

Fully-black-box reduction · standard model · LM06 · security loss: polynomial

Statement

For monic $f\in \mathbb{Z}[x]$ of degree $n$, irreducible over $\mathbb{Z}$ and with polynomially bounded expansion factor (e.g. $f=x^n+1$ for $n$ a power of $2$), finding collisions in the generalized compact knapsack function, that is, solving random Ring-SIS instances over $\mathbb{Z}[x]/⟨f⟩$, is at least as hard as worst-case approximate SVP on ideal lattices of $\mathbb{Z}[x]/⟨f⟩$ (Ideal-SVP) within a polynomial approximation factor — LM06.

Sketch

Ajtai’s iterative basis shortening (Ajt96) over the ring: random Ring-SIS instances are generated from Gaussian-perturbed points of the worst-case ideal lattice, and a short solution combines the samples into a vector of the ideal lattice shorter than the longest current basis vector; iterating shortens the basis to within a polynomial factor of the shortest vector.

Notes

• PR06 independently and concurrently obtain collision-resistant hashing from worst-case problems on cyclic lattices, $f=x^n-1$, with the knapsack domain suitably restricted.