MIT grad student Rahul Ilango built noninteractive zero-knowledge proofs by grounding secrecy in Gödel-style proof complexity, bypassing a 1994 impossibility result.
Key Takeaways
Goldreich and Oren (1994) proved noninteractive proofs cannot be zero-knowledge under the standard simulator definition; Ilango found a way around this.
Ilango’s “effective zero knowledge” drops the simulator requirement, instead showing it is computationally infeasible to prove a simulator does not exist.
The construction embeds an extra assumption into the statement being proved: no efficient proof of a contradiction in standard math axioms exists.
Because that assumption is believed unprovable in practice (proof complexity hardness), the noninteractive proof leaks nothing exploitable, matching ordinary ZK utility.
The result opens a new research direction linking proof complexity and cryptography, which cryptographers like Amit Sahai called “an incredibly cool new direction.”
