Probabilistically Checkable Proofs with Zero-Knowledge at (almost) no cost

Can you check a proof without even reading (most) of it? Can you prove to someone that you know your Gmail password without revealing it to them? Amazingly, the answer is - YES! This can be done using Zero-Knowledge Probabilistically Checkable Proofs (ZK-PCPs).

In this talk, I will provide an overview of zero-knowledge - a powerful cryptographic notion with numerous applications, ranging from guaranteeing honest behavior in distributed systems, to obtaining anonymity in cryptographic currencies. Then, I will survey classical ZK-PCP constructions, and describe their limitations. Finally, I will present a new ZK-PCP construction, which achieves zero-knowledge at (almost) no cost.