Skip to content

Latest commit

 

History

History
68 lines (43 loc) · 10.9 KB

AdvancedCryptography.md

File metadata and controls

68 lines (43 loc) · 10.9 KB

Advanced Cryptography (DEFER)

A genuine first pass into research-level territory, not equivalent-depth treatment

Honest framing up front: everything else this month, you've reached real depth on — the kind where you could defend it under questioning. This topic is different in kind, not just degree: the material here (forking lemma, AGM/GGM, the precise assumption hierarchy) is what separates "strong engineer" from "can evaluate or construct novel security proofs," and that gap genuinely takes sustained graduate-level study to close, not one focused session. What follows is a real, correct foundation and the right next steps — treat it as your entry door, not your destination.

Sources:

  1. Continue with Boneh & Shoup, A Graduate Course in Applied Cryptography (free, your spine text). Covers DLOG/CDH/DDH and the classical assumption hierarchy rigorously.

  2. Boneh & Boyen, Short Signatures Without Random Oracles (free, IACR ePrint). For the specific q-SDH assumption Groth16 relies on.

  3. Pointcheval & Stern, Security Arguments for Digital Signatures and Blind Signatures (free, author's page). The original Fiat-Shamir + Forking Lemma paper, for the actual technique, not just the name.

  4. Fuchsbauer, Kiltz & Loss, The Algebraic Group Model and Its Applications (free, IACR ePrint). Now genuinely worth reading given your foundation, rather than deferred.

  5. Victor Shoup, Lower Bounds for Discrete Logarithms and Related Problems (free, author's page, look for the "Lower bounds for discrete logarithms" entry). The original GGM paper.

  6. Oded Goldreich, Foundations of Cryptography, Volume 1 (free preliminary draft). For the most rigorous treatment of rewinding, extractors, and simulation as formal proof techniques rather than just concepts.


Knowledge Assumptions, Random Oracle Model, Fiat-Shamir, Extractors, Simulation, Reductions (recap)

Fully established across your ZK Fundamentals, Crypto Foundations, and ZK Protocol Security notes — this topic assumes that foundation and builds the actual technical machinery on top of it.

The Classical Assumption Hierarchy — DLOG, CDH, DDH

These three assumptions form a strict strength ordering, worth having exact:

  • DLOG (Discrete Log): given g and gˣ, finding x is hard. The weakest (easiest to believe) assumption of the three.
  • CDH (Computational Diffie-Hellman): given g, gᵃ, gᵇ, computing g^(ab) is hard. A stronger assumption than DLOG — if you could solve DLOG, you could break CDH (extract a from gᵃ, then compute (gᵇ)ᵃ), but the reverse implication doesn't obviously hold.
  • DDH (Decisional Diffie-Hellman): given g, gᵃ, gᵇ, and a candidate Z, deciding whether Z = g^(ab) or a random group element is hard. Stronger still than CDH — if you could solve CDH, you could trivially solve DDH (compute the real answer and compare), but not vice versa.

The precise ordering: DDH hardness ⟹ CDH hardness ⟹ DLOG hardness (each implies the one before it is also hard, i.e., breaking the weaker one is "easier" than breaking the stronger one). Critically for you: DDH is false in any pairing-friendly group (the pairing itself lets you check g^(ab) vs. random directly, via e(gᵃ,gᵇ) vs e(g,Z)) — this is exactly why pairing-based constructions like Groth16 can't rely on DDH and instead need specialized pairing assumptions (below).

Pairing Assumptions & q-SDH

Since DDH breaks in pairing groups, pairing-based schemes need different, pairing-specific hardness assumptions. q-SDH (q-Strong Diffie-Hellman), introduced by Boneh and Boyen, is the specific assumption underlying Groth16's soundness proof (your Groth16 notes' earlier mention, now precisely named): roughly, given g, gˣ, gˣ², ..., gˣ^q (q powers of a secret x), it's hard to compute a pair (c, g^(1/(x+c))) for any c of the adversary's choosing. This is a "q-type" assumption — its hardness is parametrized by q, and generally, larger q makes the assumption stronger (riskier to rely on) — worth knowing this family of "q-type" assumptions exists and that they're considered somewhat less standard/more scrutinized than plain DLOG, precisely because they're more complex, less battle-tested, and harder to have full confidence in.

Algebraic Group Model (AGM) — now with real depth, not deferred

Recall your ZK Protocol Security notes flagged this as recognize-only. Now, properly: the AGM is an idealized model where an adversary, whenever it outputs a group element, is assumed to also implicitly "know" (and the proof can extract) the explicit algebraic representation of that element as a combination of group elements it has previously seen — i.e., if the adversary outputs some Z, the model assumes Z = Σcᵢ·Gᵢ for known coefficients cᵢ, where Gᵢ are elements the adversary has seen. This is a genuinely useful idealization because it lets security proofs "look inside" what the adversary algebraically did to produce its output, similar in spirit to how the Random Oracle Model lets proofs assume structure about hash function behavior. The real caveat, worth knowing at this level: like ROM, AGM is a heuristic idealization — a proof "in the AGM" is not a proof in the plain, standard model, and there's legitimate, ongoing research-community debate about how much confidence AGM-based security proofs deserve relative to standard-model proofs.

Generic Group Model (GGM)

An even stronger idealization than AGM (predating it, introduced by Shoup): the adversary is given access to group elements only through an oracle interface — it can request group operations be performed, but has no access to the actual bit-representation of group elements at all, treating them as fully opaque, structureless labels. GGM proofs establish that no algorithm using only generic group operations (and no exploitation of a specific group's concrete representation) can break a given assumption — a genuinely strong, clean result, but one that's been shown in some cases to be too optimistic: some real attacks exploit concrete representation details that a "generic" adversary, by GGM's definition, isn't allowed to use — meaning GGM security doesn't always translate to real-world security. Worth knowing GGM and AGM as two points on a spectrum of idealization strength, with AGM generally considered the more realistic, currently-preferred model for pairing-based proofs specifically.

Forking Lemma — the actual technique, not just the name

The Forking Lemma (Pointcheval-Stern) is the formal tool underlying special soundness's extraction recipe (your ZK Fundamentals notes) made fully rigorous: given an adversary that succeeds in forging a proof/signature with non-negligible probability, the lemma shows that running the adversary twice — once normally, and once "rewound" to before a specific random challenge was chosen and replayed with a different random challenge — succeeds in producing two related forgeries (sharing the same initial commitment, differing challenges) with probability that can be precisely bounded. Those two forgeries are exactly what a special-soundness-based extractor needs to actually compute the witness. This is a genuinely technical, careful probabilistic argument — the "obvious" version of this idea has subtle bugs that took real care to get right in the original proof, which is part of why it's treated as a named, citable lemma rather than an obvious folklore fact.

Rewinding

The formal proof technique underlying both the Forking Lemma and knowledge-soundness extractors generally: a simulator or extractor is allowed to run the adversary, "rewind" it back to an earlier point in its execution, and replay with different randomness (a different challenge) — extracting useful information by comparing the two resulting executions. This is a proof-construction technique, not something that happens in a real protocol execution — it's a tool the security proof uses, exploiting the fact that a proof gets to control the adversary as a subroutine, even though no real-world verifier can literally rewind a real prover.

Simulation Techniques (now more precisely)

Beyond the basic "simulator produces a fake transcript" idea from your ZK Fundamentals notes, real simulation proofs use specific, careful techniques: programming the random oracle (choosing hash outputs strategically within the simulation, exploiting ROM's idealization), using the trapdoor (Groth16's toxic-waste-dependent simulator, your Groth16 notes), and combining these with rewinding where needed. Constructing a correct simulator for a new protocol is genuinely one of the harder parts of writing an original ZK security proof.

Reductions (recap, now at research-writing level)

Your Proof by Contradiction notes established the shape; at research level, a good reduction proof needs to be tight (the reduction shouldn't lose too much in its success probability or running time when translating an adversary against the scheme into an adversary against the underlying hard problem) — reduction tightness is itself an active area of scrutiny in cryptographic research, since a "loose" reduction technically proves security but with much weaker concrete guarantees than the abstract statement suggests.


An honest map of what real mastery here requires

This file gives you correct vocabulary, correct relative positioning of each concept, and a real first understanding of why each idea exists — genuinely more than most working ZK engineers ever build. But actually operating at "compare to industry cryptographers" level on this specific material means: reading the primary papers listed above in full (not summaries), working through several complete security proofs by hand (not just reading their conclusions), and ideally working through a graduate cryptography course's problem sets on reductions and simulation. That's realistically a multi-month project layered on top of everything else you've built — which is exactly why your original roadmap correctly deferred it. Treat this month's pass as having opened the door, not walked through it.


Quick self-check — calibrated to "genuine entry point," not mastery

You're ready to call this a solid first pass once you can, without notes:

  1. Explain the DLOG/CDH/DDH strength ordering, and why DDH specifically breaks in pairing-friendly groups
  2. Explain what q-SDH asserts, and why "q-type" assumptions are considered less standard than plain DLOG
  3. Explain the difference between AGM and GGM, and why AGM is generally considered the more realistic of the two
  4. Explain what the Forking Lemma actually proves, and how rewinding is the technique making that proof possible