אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Zero-knowledge proofs enable verifying the correctness of computations without revealing any additional information beyond their validity. We focus on proofs that are statistically sound - ensuring that even an unbounded prover cannot convince the verifier of a false statement except with negligible probability, and computationally zero-knowledge. In this work, we study the communication complexity of such proofs. While the original constructions have a large polynomial communication overhead, later works have shown that this overhead can often be significantly reduced.

We show that every NP relation that can be verified by a bounded-depth, polynomial-size circuit or a bounded-space, polynomial-time algorithm have a computational zero-knowledge proof whose communication is only additively larger than the witness length. Our construction relies solely on the minimal assumption that one-way functions exist. Moreover, in some cases we achieve the same while making only a black-box use of the one-way function.