Batch Proofs are Statistically Hiding

ePrint Report: Batch Proofs are Statistically Hiding

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalina Vasudevan

Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs are known for $UP$, the class of unique witness $NP$ languages. In …

batch case communication eprint report language omer report ron systems