Hash Functions, Signatures, and the ROM¶
Job: develop the hash functions (collision-resistant, Merkle–Damgård), the signatures (EUF-CMA, Schnorr/ECDSA), the ROM / Fiat–Shamir, and the hash-based (SPHINCS+) — with the ECDSA / Fiat–Shamir as the worked example.
Core¶
The hash and the collision¶
| Hash / collision / Merkle–Damgård | Description |
|---|---|
| Collision-resistant | \(H\), no PPT finds \(H(x)=H(x')\) (the information theory) |
| Merkle–Damgård | the iteration / compression (the information theory) |
The signatures and the EUF-CMA¶
| EUF-CMA / Schnorr / ECDSA | Description |
|---|---|
| EUF-CMA | existential unforgeability under chosen-message (the foundations) |
| Schnorr / ECDSA | DL-based signatures (the number theory) |
The ROM and the Fiat–Shamir¶
| ROM / Fiat–Shamir / non-interactive | Description |
|---|---|
| ROM | random oracle model (the foundations) |
| Fiat–Shamir | \(e=H(t,m)\) the non-interactive (the foundations) |
The SPHINCS+ and the hash-based¶
| SPHINCS+ / hash-based / Merkle / post-quantum | Description |
|---|---|
| SPHINCS+ | hash-based signature, post-quantum |
| Merkle tree | the hash-based the Merkle, the post-quantum |
See it¶
ECDSA and the Fiat–Shamir / ROM. The ECDSA: the \((r,s)\) (the \(r=(kG)_x\), the \(s=k^{-1}(z+rx)\), the verify \(r=(s^{-1}zG+s^{-1}rX)_x\), the number theory). The Fiat–Shamir: the \(e=H(t,m)\) the non-interactive (the foundations). The key point: the ECDSA the DL, the Fiat–Shamir the ROM.
Check¶
Explain the ECDSA and the EUF-CMA.
The ECDSA: the \((r,s)\) (the \(r=(kG)_x\) the \(x\)-coordinate, the \(s=k^{-1}(z+rx)\) the \(z\) the hash of message, the \(k\) the nonce, the number theory). The EUF-CMA: the adversary queries \(\mathrm{Sign}\), must produce \((m,\sigma)\) for new \(m\) (the foundations). The ECDSA the EUF-CMA under the DL (the number theory). The nonce: the \(k\) the random, the \(k\) reuse the leak (the Sony PS3). So the ECDSA the DL, the EUF-CMA the unforgeability.
Explain the Merkle–Damgård and the SPHINCS+.
The Merkle–Damgård: the \(H(m)=h(H_{\mathrm{iv}},m)\) the iteration (the compression \(h\), the padding, the information theory). The collision: the \(H\) the collision-resistant (the information theory). The SPHINCS+: the hash-based signature (the WOTS+ / the FORS / the Merkle tree, the post-quantum, the foundations). The hash-based: the Merkle tree (the one-time, the few-times, the post-quantum). So the Merkle–Damgård the iteration, the SPHINCS+ the hash-based.
Pitfalls¶
- The collision-resistant the [information theory] (the \(H\), the information theory) — the collision the hard, the Merkle–Damgård the iteration.
- The EUF-CMA the [foundations] (the foundations) — the EUF-CMA the unforgeability, the Schnorr / ECDSA the DL.
- The ROM the heuristic (the foundations) — the ROM the idealized, the Fiat–Shamir the non-interactive.
- The SPHINCS+ the post-quantum (the hash-based, the Merkle) — the SPHINCS+ the hash, the post-quantum.
Refs¶
- Merkle–Damgård (1989); the hash iteration
- NIST FIPS 186-4; the ECDSA
- Schnorr, "Efficient signature generation by smart cards" (1990); the Schnorr
- SPHINCS+ (NIST PQC); the hash-based
Next¶
Crypto index · Foundations · Lattice & Post-Quantum · ZK & MPC · Protocols & TLS · Number theory · Information theory