Module-SIS ⇒ CRHF

Fully-black-box reduction · standard model · folklore · security loss: Tight: one call to the collision finder, and each collision it finds is a Module-SIS solution.

Statement

Let $R=\mathbb{Z}[x]/⟨x^n+1⟩$ with $n$ a power of $2$, let $R_q=R/qR$, and let $k,\ell ,q,\beta$ satisfy $\ell >k\log q$ and $\sqrt{n\ell }\le \beta <q$. If Module-SIS over $R_q$ with matrices in $R_q^{k\times \ell }$ and Euclidean norm bound $\beta$ on the coefficient vector is hard, then the family $\{h_{\mathbf{A}}:\mathbf{z}\mapsto \mathbf{Az}\in R_q^k\}$, keyed by uniform $\mathbf{A}\in R_q^{k\times \ell }$ and restricted to inputs $\mathbf{z}\in R^{\ell }$ whose $n\ell$ coefficients lie in $\{0,1\}$, is a compressing collision-resistant hash function family: its domain has $2^{n\ell }>q^{nk}=|R_q^k|$ elements, and for every efficient collision finder $\mathcal{A}$ there is an efficient Module-SIS solver whose success probability is at least ${\mathbf{Adv}}_{h,\mathcal{A}}^{\mathrm{cr}}(\lambda )$ — standard. With input coefficients in $\{0,\dots ,d-1\}$ for an integer $d\ge 2$, the same holds, with a domain of $d^{n\ell }>q^{nk}$ elements, whenever $\ell \log d>k\log q$ and $(d-1)\sqrt{n\ell }\le \beta <q$ — standard.

Sketch

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

Notes

• Rank $k=1$ is the generalized compact knapsack of Ring-SIS ⇒ CRHF — LM06; degree $n=1$, where $R=\mathbb{Z}$, is the SIS hash $\mathbf{z}\mapsto \mathbf{Az}\mathrm{mod}q$ of SIS ⇒ CRHF — Ajt96, GGH96.
• Writing each coefficient of $R_q^k$ in $\lceil \log q\rceil$ bits makes $h_{\mathbf{A}}$ a map $\{0,1{\}}^{n\ell }\to \{0,1{\}}^{nk\lceil \log q\rceil }$, which shortens its input when $\ell >k\lceil \log q\rceil$ — standard.
• For $q$ sufficiently large relative to $\beta$, Module-SIS is at least as hard as worst-case approximate SIVP on module lattices to within polynomial factors (Module-SIVP ⇒ Module-SIS) — LS15.
• Under the ${\ell }_{\infty }$ norm, as in Dilithium’s Module-SIS (DKL+18), the difference of two colliding binary inputs has $\Vert \mathbf{z}-{\mathbf{z}}^{\prime }{\Vert }_{\infty }=1$, so ${\ell }_{\infty }$ Module-SIS with any bound $1\le \beta <q$ suffices — standard.