KEYNOTE Building Succinct Arguments from Ideal Hash Functions
summary
Construction shows succinct arguments from the random oracle model using PCPs and IOPs, committing PCP strings with a Merkle tree whose root is λ bits and openings cost O(log n). Security bounds depend on adversary queries T (success grows roughly with T^2 via collisions) so soundness degrades by about T·ε and has a T·ε lower bound; noninteractive proofs use Fiat–Shamir, requiring round‑by‑round or extractable commitments to recover soundness.
AI-written summary · about
chapters (10)
- 0:00Succinct arguments overview
- 3:17Cryptographic hash functions
- 7:30Random Oracle model
- 10:20Succinct arguments from Merkle trees
- 14:39Security analysis
- 17:53Interactive vs non-interactive proofs
- 21:08IOPs role
- 22:34Non-interactive security challenges
- 25:48Commitment schemes alternatives
- 27:12Conclusion
related talks
44mIOP based Zero-Knowledge Proofs
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
31mSequential Composition of Rational Proofs
18mHopping Proofs of Expectation-Based Properties: Applications to Skiplists and Security(…)
34mThe Concrete Security of Two-Party Computation: Simple Definitions, and Tight Proofs for PSI and...
40mPost-Quantum
41mGKR based Zero-Knowledge Proofs
35mEfficient Zero Knowledge Protocols: The Modular Approach