Discrete Log based Zero-Knowledge Proofs
summary
Presents a clear framework: discrete-log ZK and argument systems (Schnorr, Bulletproofs) extend to groups of unknown order but naive generalization fails (attack via rational half-exponents), so security requires elements with no known roots and analysis in the generic group plus an adaptive root assumption. Gives a 128-bit-prime proof of exponentiation with verifier cost independent of exponent size, shows aggregating many inclusion/exclusion proofs via an RSA accumulator into one short proof, and sketches compressing a Bitcoin UTXO commitment to ~256 bytes (implemented).
AI-written summary · about
chapters (10)
- 0:00Intro
- 2:13Review: The Schnorr Proof of Knowledge
- 5:25Example: equality of discrete-logs (DLEQ) Chaum-Pedersen 92
- 7:33Homomorphism preimage proof for R1CS
- 12:32Schnorr in a group of unknown order Bangerter, Camenisch, Krenn, 2010
- 19:21Step 1: proof of exp (PoExp) Wesolowski18 Prover
- 29:29Extracting the witness a
- 36:49Aggregating multiple inclusion proofs
- 39:10Aggregating multiple exclusion proofs
- 42:01Compressing the blockchain: a proposal
related talks
44mZero-Knowledge Proofs: Simultaneously ensuring integrity and privacy
51mWhy you shouldn't trust me
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
59mCommit-and-Prove Zero-Knowledge Proof Systems and Extensions
14mAdvancements in Cryptography and Zero Knowledge Proofs - Binius Curve
48mzkSNARKs — Cryptographic Proofs for Scaling and Security Challenges
37mUsing Zero to Attack Zero-Knowledge Proof (ZKP) PLONK
37mWhat ZK Can—and Can’t—Do for You