Unknowable Math Can Help Hide Secrets
4 days ago
- #cryptography
- #zero-knowledge-proofs
- #proof-complexity
- Gödel's incompleteness theorems showed that mathematical axioms cannot guarantee self-consistency, introducing the concept of unknowability in mathematics.
- Zero-knowledge proofs, developed in 1985, allow proving a statement's truth without revealing why it is true, using interaction between a prover and verifier.
- In 1994, Goldreich and Oren proved noninteractive zero-knowledge proofs are impossible under the original definition, as they lack simulators.
- Rahul Ilango's breakthrough uses proof complexity to create effective zero-knowledge proofs by leveraging the difficulty of proving certain mathematical statements.
- Ilango's approach adds an assumption to statements, making it impossible to distinguish if a proof lacks a simulator, thus bypassing the noninteractivity limitation.
- The work connects mathematical logic and cryptography, suggesting further applications of proof complexity in cryptography to overcome other impossibility results.