SIS ⇒ Hash function

SIS implies Hash function.

Statement

Migrated verbatim from shortest-integer-solution § Shortest Integer Solution:

The Shortest Integer Solution (SIS) problem is a lattice problem used as the hardness foundation for collision-resistant hash functions and lattice-based signature schemes. Unlike LWE, which is an indistinguishability problem, SIS is a search problem.

Migrated verbatim from shortest-integer-solution § Collision-resistant hash functions:

The function family $\{f_{\mathbf{A}}:\mathbf{z}\mapsto \mathbf{Az}\mathrm{mod}q\}$, restricted to inputs $\mathbf{z}\in \{0,\dots ,\lfloor \beta /2\rfloor {\}}^m$, is a collision-resistant hash function family under SIS hardness — Ajt96. Any collision $f_{\mathbf{A}}(\mathbf{z})=f_{\mathbf{A}}({\mathbf{z}}^{\prime })$ with $\mathbf{z}\ne {\mathbf{z}}^{\prime }$ yields $\mathbf{A}(\mathbf{z}-{\mathbf{z}}^{\prime })=0(\mathrm{mod}q)$ with $\Vert \mathbf{z}-{\mathbf{z}}^{\prime }\Vert \le \beta$, which is exactly a SIS solution.

Notes

class: unstated: no citing page says which notion of reduction is meant. Recording a class the wiki does not state would add a claim.

This relation is stated on 2 pages; the statements above are all of them.

Citations disagree across pages: [object Object]

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• Intro sentence packs two applications (CRHF, lattice-based signatures) with no citation on either; both are cited later, at lines 48 and 60. Recorded separately.
• Duplicates the cited claim at line 48.
• BROKEN-ISH WIKILINK: [[collision-resistant-hash-function|...]] has no page of that name. It resolves only through the alias “Collision-resistant hash function” on content/Primitives/hash-function.md — a page that ALSO carries the aliases OWF and One-way function, so the link lands on a node that conflates CRHF with OWF.
• SUSPECTED NORM ERROR (report only): with inputs in {0,…,floor(beta/2)}^m the difference z - z′ has entries in [-beta/2, beta/2], so ||z - z′|| ⇐ beta holds for the L-infinity norm. The game defined at line 27 of this page writes ||z|| ⇐ beta without naming a norm, and under the usual L2 reading the bound would be (beta/2)sqrt(m), not beta.