From Algebraic Complexity to Zero Knowledge Protocols

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.