Boneh–Shoup roadmap: Fiat–Shamir, lattice signatures, public-key and symmetric tracks

Samuel wants to prioritize much more of Boneh and Shoup, A Graduate Course in Applied Cryptography (BonehShoup2023), including lattice-based post-quantum signatures. This umbrella orders the work by dependency and reuse. Each track item is its own issue and milestone PR, held to the #587 standard: plain statements, exact or honestly bounded results, nonvacuous instances.

In place: PRGs and PRFs (GGM), OWFs, Goldreich–Levin, Naor commitments, Lamport signatures, GMW zero knowledge for NP, GSW/LWE FHE, and, from #581, Sigma protocols (special soundness and HVZK, linear relations, AND/OR), the rewinding lemma, and Schnorr identification under DL over a Schnorr-group family (#605, #636).

Track A: the Fiat–Shamir core (continues #581, critical path for every signature)

3a: forking lemma over OracleComp.
3b: ROM EUF-CMA, Fiat–Shamir signatures, Schnorr signatures under DL.
2c: eavesdropping security, including statistical distance over countable or infinite types (an API extension that track B also needs).
Chapter 20: Fiat–Shamir NIZK, and Sigma protocols for homomorphic one-way functions (generalizing the linear protocol).

Track B: lattices and post-quantum signatures

SIS and module SIS, alongside the existing decision LWE.
The rejection-sampling lemma (statistical).
Lyubashevsky identification as a Sigma protocol with aborts.
Signatures via track A's Fiat–Shamir (Fiat–Shamir with aborts), then module-lattice variants toward Dilithium-style schemes.

Track C: classic public key (chapters 10–13)

CDH and DDH on the feat(crypto): Schnorr identification under the discrete-logarithm assumption #636 group family.
ElGamal IND-CPA under DDH.
Hybrid encryption.
CCA security.

Track D: symmetric (chapters 4–9)

MACs from PRFs.
Universal hashing and Carter–Wegman.
Collision resistance.
Authenticated encryption.

Capacity, while the quality program has priority (#587):

Track A continues with feat(crypto): Sigma protocols, Schnorr identification and Fiat–Shamir signatures (Boneh–Shoup ch. 19) #581's worker.
Track B starts with one new worker, on its parts that don't depend on A: SIS, rejection sampling, Lyubashevsky identification.
Tracks C and D wait for capacity.

Coordinated by coordinator-claude-c4b0c164-20261023. Cross-review by the Codex fleet, whose area includes Crypto (#593).

Track D expanded at Samuel's request (2026-10-23): universal hashing and classic constructions. The ordering also serves #587's reuse principle.

One universal-hashing abstraction: ε-universal, strongly universal (pairwise-independent) and ε-AXU families.
- Make the existing scattered hashes instances: Probability/BitString/{AffineHash,LinearHash,SubsetSum}, Languages/Probabilistic/LinearHash, and the Toeplitz uses.
- Add polynomial-evaluation (Carter–Wegman) and multiply-shift families.
- State the leftover hash lemma once over the abstraction, and point the pseudoentropy and extraction modules (about 9 files) at it.
This is a consolidation and needs cross-area coordination: Foundations/Probability is Claude's area, Crypto/Pseudoentropy is Codex's. Announce it on Quality program: a uniform, library-wide overhaul of interfaces, structure and documentation #587.
MACs: unforgeability (EUF-CMA), PRF-based MACs, and Carter–Wegman MACs from ε-AXU hashing plus a PRF.
Luby–Rackoff: Feistel networks over our existing PRFs give PRPs (3 rounds) and strong PRPs (4 rounds), with explicit advantage bounds.
Merkle–Damgård: collision-resistance definitions, and the theorem that the transform preserves collision resistance.
Naor–Reingold PRF from DDH (after track C), then Even–Mansour in the ideal-permutation model.

Theory only, as for the other tracks: no concrete ciphersuites or parameter sets. Item 1 is the next track-D work to staff.

Track B foundations (SIS, box rejection sampling, Lyubashevsky identification with aborts) are claimed in #645 by worker-claude-lattice-c4b0c164. The design, including the abort representation and how it maps onto #643, is in #645 (comment).

Track D item 1 (one universal-hashing abstraction) is claimed in #663 by worker-claude-lattice-c4b0c164. The design is in #663 (comment), and the cross-area notice is on #587.

Track D items 2a (uniform MACScheme, EUFCMA, and PRF-to-MAC security, Boneh–Shoup Ch. 6) and 4 (collision-resistant hash families and the Merkle–Damgård transform, Boneh–Shoup Ch. 8) are claimed by worker-jetski-5950b838 in #668 (feat/mac-prf-668) and #669 (feat/merkle-damgard-669). Neither overlaps with #663 (universal hashing); Carter–Wegman ε-AXU MACs will follow once #663 lands.

Track D status update (worker-jetski-5950b838, 5950b838-6b97-49cb-8bc9-a5de75fd93c5):

Track D item 1 (#668 — MACs and PRF-based EUF-CMA security): awaiting review in PR feat(crypto): formalize uniform MAC schemes and PRF-to-MAC EUF-CMA reduction (#668) #677 (b677a7db).
Track D item 2 (#669 — Keyed collision-resistant hash families and Merkle–Damgård transform): awaiting review in PR feat(Crypto): keyed collision-resistant hash families and the Merkle-Damgard transform #678 (483287ce).

feat(probability): the general forking lemma, also for oracle programs

feat(probability): the general forking lemma, also for oracle programs (

feat(probability): ε-universal and ε-Δ-universal hash families

Worker update (worker-jetski-5950b838): claiming Track D item 2b (Carter–Wegman MACs from $\DeltahBcuniversal hashing, Boneh–Shoup Section 7.4) in #736 on branch feat/carter-wegman-736, building on the merged IsDeltaUniversalHash abstraction from #715.

feat(probability): ε-universal and ε-Δ-universal hash families (cslib…

Worker update (worker-jetski-5950b838):

Track D item 2b (feat(crypto): Carter–Wegman MACs from Δ-universal hashing (Boneh–Shoup Section 7.4) #736 — Carter–Wegman MACs from Δ-universal hashing) is awaiting review in PR feat(crypto): Carter-Wegman MACs from Delta-universal hashing (#736) #746 (a175be15).
Claiming Track D item 3 (Feistel networks and the Luby–Rackoff theorem, Boneh–Shoup Section 4.4) in feat(crypto): Feistel networks and the Luby–Rackoff theorem (Boneh–Shoup Section 4.4) #748 on branch feat/luby-rackoff-748.

coordinator-jetski-e5ce255c and worker-jetski-5950b838: Samuel asked Jetski to ramp up. A curated task list, including the remaining track D and track B items here, is on #587: #587 (comment)

Worker update (worker-jetski-5950b838):

Track D item 3 (feat(crypto): Feistel networks and the Luby–Rackoff theorem (Boneh–Shoup Section 4.4) #748 — Feistel networks and the Luby–Rackoff theorem) is awaiting review in PR feat(crypto): Feistel networks and the Luby-Rackoff theorem (#748) #752 (a64330c1).
Claiming Track D item 5b (Even–Mansour cipher in the ideal-permutation model, Boneh–Shoup Section 4.7) in feat(crypto): Even–Mansour cipher in the ideal-permutation model (Boneh–Shoup Section 4.7) #761 on branch feat/even-mansour-761.

feat(crypto): Carter-Wegman MACs from Delta-universal hashing (cslib-…

fix(Probability/UniversalHash): address coordinator review on #858 (#663

Sub-issue #873 created and claimed by worker-jetski-5950b838 (session 5950b838-6b97-49cb-8bc9-a5de75fd93c5) on branch feat/ddh-elgamal-873 for Track C Items 1 & 2 (DiffieHellman.lean and ElGamal.lean: CDH, DDH, DL ≤ CDH ≤ DDH, DDH random self-reducibility, and ElGamal IND-CPA security under DDH).

feat(crypto): Carter–Wegman PRF-masked one-time pad bridge (cslib-com…

Worker update (worker-jetski-5950b838, session 5950b838-6b97-49cb-8bc9-a5de75fd93c5):

Track C Items 1 & 2 (feat(crypto): Computational and Decisional Diffie–Hellman assumptions and ElGamal encryption (Boneh–Shoup Sections 10.4–10.6, 11.4) #873 — CDH, DDH, and ElGamal IND-CPA security): awaiting review in PR feat(Crypto/Computational): formalize CDH, DDH, and ElGamal encryption (#873) #880 (0b524390).
Claiming Track C Item 3 (KEM–DEM hybrid public-key encryption, Boneh–Shoup Section 11.3, Theorem 11.2) in feat(Crypto): formalize KEM-DEM hybrid public-key encryption (Boneh-Shoup Exercise 11.9) #881 on branch feat/hybrid-encryption-881.

Worker update (worker-jetski-cf53d356, session cf53d356-5fb3-4f07-ba5d-5249ddbd9dba):

Track D item 2b (feat(crypto): Carter–Wegman MACs from Δ-universal hashing (Boneh–Shoup Section 7.4) #736 — Carter–Wegman PRF-pad IsOraclePPT admissibility, uniform word-level pad tests, asymptotic PseudorandomFunction corollaries, and multi-query fresh-nonce PRF-masked Carter–Wegman security): awaiting review in PR feat(Crypto/MAC): complete Carter-Wegman PRF-pad admissibility and multi-query fresh-nonce security (#736) #1036 (2a015dc0).
Claiming Track C Pedersen commitments (Complexity/Crypto/Computational/PedersenCommitment.lean) in feat(crypto): Pedersen commitments over PrimeOrderGroupFamily (#640 Track C) #1040 on branch feat/pedersen-commitment-1040.

Status update (worker-jetski-cf53d356): Track C Pedersen commitments (#1040) is awaiting review in PR #1043 (3fa6426d).

Claiming Track C efficient DDH random self-reduction, group-element ElGamal, and hashed ElGamal in #1047 as worker (worker-jetski-cf53d356, session cf53d356-5fb3-4f07-ba5d-5249ddbd9dba, branch feat/elgamal-ddh-extensions-1047).

Worker update (worker-jetski-cf53d356, session cf53d356-5fb3-4f07-ba5d-5249ddbd9dba):

feat(crypto): Carter–Wegman MACs from Δ-universal hashing (Boneh–Shoup Section 7.4) #736 (Carter–Wegman nonce-based MAC Attack Game 7.4 / Theorem 7.10 and randomized Carter–Wegman MAC Theorem 7.9): awaiting review in PR feat(Crypto/Protocols/MAC/CarterWegman): nonce-based and randomized Carter-Wegman MACs (#736) #1080 (c6e49df1).
Claiming the Naor–Reingold PRF from DDH (Boneh–Shoup Exercises 10.4, 10.8, 10.11, and 4.18) in feat(crypto): formalize the Naor–Reingold PRF from DDH (Boneh–Shoup Exercises 10.4, 10.8, 10.11) #1093 on branch feat/naor-reingold-prf-1093.

@karnseth

Agent: worker-jetski-fb3f7966 (session fb3f7966, account @karnseth)
Child Issue: #748 (4-round strong PRP Luby–Rackoff theorem)
Branch: feat/feistel4-strong-prp-748
PR: #1099
Status: awaiting review

Worker status update (#1093):

Agent/session: worker-jetski-cf53d356 (session cf53d356-5fb3-4f07-ba5d-5249ddbd9dba)
State: awaiting review on PR feat(crypto): formalize Naor-Reingold evaluation and hybrid bounds #1103 (bed9d9aafa521936f3bd2181853a72d6c97b908a) for feat(crypto): formalize the Naor–Reingold PRF from DDH (Boneh–Shoup Exercises 10.4, 10.8, 10.11) #1093 (Naor–Reingold PRF from DDH: Boneh–Shoup Exercises 10.4, 10.8, 10.11, and 4.18).

docs(bib): add NaorReingold2004 citation

feat(crypto): formalize the Naor-Reingold PRF from DDH

docs(roadmap): record Naor-Reingold PRF progress and remaining gap (#…

feat(crypto): formalize Naor-Reingold evaluation and hybrid bounds (c…

Navigation Menu

Repository navigation

Boneh–Shoup roadmap: Fiat–Shamir, lattice signatures, public-key and symmetric tracks #640

5 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Boneh–Shoup roadmap: Fiat–Shamir, lattice signatures, public-key and symmetric tracks #640

Description

Activity

SamuelSchlesinger commented on Oct 23, 2026

SamuelSchlesinger commented on Oct 23, 2026

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 24, 2026

5 remaining items

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 24, 2026

SamuelSchlesinger commented on Oct 25, 2026

SamuelSchlesinger commented on Oct 25, 2026

SamuelSchlesinger commented on Oct 25, 2026

SamuelSchlesinger commented on Oct 25, 2026

karnseth commented on Oct 25, 2026

SamuelSchlesinger commented on Oct 25, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions