SIS ⇒ CRHF

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

Statement

For $m>n\log q$ and $\beta \ge \sqrt{m}$, if SIS is hard for $(n,m,q,\beta )$, then $\{f_{\mathbf{A}}:\{0,1{\}}^m\to {\mathbb{Z}}_q^n,\mathbf{z}\mapsto \mathbf{Az}\mathrm{mod}q\}$, keyed by uniform $\mathbf{A}\in {\mathbb{Z}}_q^{n\times m}$, is a compressing collision-resistant hash function family — GGH96.

Sketch

A collision $\mathbf{z}\ne {\mathbf{z}}^{\prime }$ gives $\mathbf{A}(\mathbf{z}-{\mathbf{z}}^{\prime })=0(\mathrm{mod}q)$ with $\mathbf{z}-{\mathbf{z}}^{\prime }\in \{-1,0,1{\}}^m$ nonzero, a SIS solution of Euclidean norm at most $\sqrt{m}\le \beta$. The reduction runs the collision finder once on $\mathbf{A}$ and outputs the difference.

Notes

• The family $\{f_{\mathbf{A}}\}$ and its one-wayness are due to Ajt96.
• Efficiency: the key $\mathbf{A}$ has $nm\log q$ bits and evaluation costs $O(nm)$ additions modulo $q$, since $\mathbf{z}$ is binary; over ideal lattices the key shrinks to $\tilde{O}(m)$ bits — LM06.