Omer Reingold, Guy Rothblum, Ron Rothblum

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>>

Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon

A statistical zero-knowledge proof (SZK) for a problem $\Pi$ enables a computationally unbounded prover to convince a polynomial-time verifier that $x \in \Pi$ without revealing any additional information about $x$ to the verifier, in a strong information-theoretic sense.

Suppose, however, that the prover wishes to convince the verifier that $k$ ... more >>>

Guy Rothblum, Ron Rothblum

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? ... more >>>

Inbar Kaslasi, Ron Rothblum, Prashant Nalini Vasudevan

Suppose that a problem $\Pi$ has a statistical zero-knowledge (SZK) proof with communication complexity $m$. The question of batch verification for SZK asks whether one can prove that $k$ instances $x_1,\ldots,x_k$ all belong to $\Pi$ with a statistical zero-knowledge proof whose communication complexity is better than $k \cdot m$ (which ... more >>>