SIS ⇒ DS

Fully-black-box reduction · random oracle model · GPV08 · security loss: tight up to statistical terms: one run of the forger, with every hash value programmed as the image of a self-sampled short preimage, and a forgery differs from that preimage except with negligible probability

Statement

If SIS is hard, the GPV hash-and-sign signature scheme is SUF-CMA-unforgeable in the random-oracle model: the signature on $\mu$ is a short $\mathbf{z}$ with $\mathbf{Az}=H(\mu )\mathrm{mod}q$, sampled from a discrete Gaussian using a short basis of ${\Lambda }_q^{\perp }(\mathbf{A})$ generated together with $\mathbf{A}$, which makes $\mathbf{z}\mapsto \mathbf{Az}$ a preimage-sampleable function; strong unforgeability follows from its collision resistance on short inputs, which is SIS — GPV08.

Sketch

Trapdoor-sampled preimages are distributed as a discrete Gaussian conditioned on their image, so the reduction, holding a challenge $\mathbf{A}$ without a trapdoor, answers each hash query by sampling $\mathbf{z}$ first and programming $H(\mu ):=\mathbf{Az}$, and answers signing queries with those $\mathbf{z}$. A forgery ${\mathbf{z}}^{\ast }$ on ${\mu }^{\ast }$ differs from the reduction’s own preimage ${\mathbf{z}}^{\prime }$ of $H({\mu }^{\ast })$ except with negligible probability (preimage min-entropy), and ${\mathbf{z}}^{\ast }-{\mathbf{z}}^{\prime }$ is a short nonzero SIS solution for $\mathbf{A}$.

Notes

• Through ISIS, which is equivalent to SIS (ISIS ⇔ SIS), one-wayness of $\mathbf{z}\mapsto \mathbf{Az}$ alone gives EUF-CMA by the full-domain-hash argument, at a loss of the number of hash queries — standard.
• Signatures from SIS in the ROM without a lattice trapdoor, via Fiat–Shamir with aborts and rejection sampling — Lyu12.
• Stateless hash-and-sign signatures from SIS in the standard model, via bonsai-tree basis delegation — CHKP10.