Coinductive Proofs of Regular Expression Equivalence in Zero Knowledge
summary
Crepe is a zero-knowledge protocol that encodes full regular-expression equivalence proofs (PSPACE-complete) using a custom calculus based on coinduction and derivatives, converts a derivative-search trace into a sound and complete proof tree, and validates committed proof steps on a proof VM with multiplexed rule-checkers. Evaluation generates proofs for 7,353 equivalent regex pairs (72 hit a 10-minute timeout) and shows large proofs validate in only a few seconds under the default multiplexing; Crepe hides values with commitments and trades speed versus security across multiplexing modes.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:25Zero knowledge regex equivalence
- 3:28Proof format and co-induction
- 7:05Proof generation and validation
- 9:11CREPE performance evaluation
- 10:55Related work and future
- 11:56Conclusion and Q&A
related talks
33mAn Introduction to Zero Knowledge Proofs
01h 09mProofs - Practice 1
26mA Core Calculus for Equational Proofs of Cryptographic Protocols
19mAutomated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs
01h 13mA Zero-Knowledge PCP Theorem
48mProving UNSAT in Zero Knowledge
01h 06mLattice-based Zero-knowledge Proofs
31mProgrammable Zero Knowledge