The main challenge in this setting is maintaining soundness against a malicious prover who can iteratively submit malformed proofs and use the verifier's binary (accept/reject) feedback to progressively learn the reused query set. This question is motivated in part by attractive features of designated-verifier NIZK (Non-Interactive Zero-Knowledge proofs) that can be obtained by combining symmetric encryption with a query-reusable honest-verifier ZK-PCP.

We show that, under standard complexity-theoretic assumptions, fully query-reusable PCPs and statistical ZK-PCPs are impossible. To bypass this impossibility, we investigate a more refined notion, bounded query-reusability, in which the prover interacts with the verifier over a bounded number of rounds, submitting polynomially many proofs in each round and learning the verifier's decisions. In this model, we obtain a nearly tight characterization of the number of rounds of query-reusability in terms of the size of the query set.

This talk is based on joint work with Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Akash Shah. The only assumed background is basic familiarity with core concepts in complexity theory and cryptography.