Ring-SIS ⇒ CRHF

Fully-black-box reduction · standard model · LM06 · security loss: Tight: one call to the collision finder, ${\mathbf{Adv}}^{\mathrm{cr}}\le {\mathbf{Adv}}^{\mathrm{ring}\text{-}\mathrm{sis}}$.

Statement

Let $R_q={\mathbb{Z}}_q[x]/⟨x^n+1⟩$ with $n$ a power of $2$, and let $\ell >\log q$, so that $m=n\ell >n\log q$. The generalized compact knapsack $h_{a_1,\dots ,a_{\ell }}(z_1,\dots ,z_{\ell })={\sum }_i{a}_i{z}_i\in R_q$, keyed by uniform $a_i\in R_q$ and restricted to inputs whose coefficients lie in $\{0,1\}$, is a compressing collision-resistant hash function family whenever Ring-SIS over $R_q$ with $\ell$ ring elements and norm bound $\beta \ge \sqrt{n\ell }$ is hard — LM06. With inputs of coefficients bounded by $d$ in absolute value and $\ell >\log q/\log (2d)$, as in LM06, the same argument needs $\beta \ge 2d\sqrt{n\ell }$.

Sketch

A collision $(z_i{)}_i\ne (z_i^{\prime }{)}_i$ gives ${\sum }_i{a}_i(z_i-z_i^{\prime })=0$ in $R_q$, where the coefficients of $z_i-z_i^{\prime }$ lie in $\{-1,0,1\}$, not all zero, so the difference is a Ring-SIS solution of Euclidean norm at most $\sqrt{n\ell }\le \beta$. The reduction runs the collision finder once on $(a_1,\dots ,a_{\ell })$ and outputs the difference.

Notes

• Efficiency: a key is $\ell$ ring elements, $n\ell \log q$ bits against $n\cdot n\ell \log q$ for the unstructured SIS hash with the same input length, and evaluation takes $\tilde{O}(n\ell )$ time through ring products — LM06.
• LM06 base Ring-SIS on worst-case approximate SVP on ideal lattices, for $f$ irreducible with polynomially bounded expansion factor (Ideal-SVP ⇒ Ring-SIS). Over the reducible $f=x^n-1$, PR06 independently obtain collision-resistant knapsacks from worst-case problems on cyclic lattices, with the domain suitably restricted.