From Algebraic Complexity to Zero Knowledge Protocols

Friday, March 24, 2017 - 10:30am to 12:00pm
Hewlett Room G-882
Alessandro Chiesa

We present new techniques for achieving unconditional zero knowledge within models that combine probabilistic checking and interaction. Our techniques establish novel connections to algebraic complexity, and enable us to obtain natural zero-knowledge analogues of classical PCP and IP protocols. Our constructions require only simple and cheap modifications to the verifier of the original (non-zero-knowledge) protocol.