Interactive Proofs under Continual Memory Leakage.
Prabhanjan Ananth, Vipul Goyal, Omkant Pandey · 2014
We consider the task of constructing interactive proofs for NP which can provide meaningful security for a prover even in the presence of continual memory leakage. We imagine a setting where an adversarial verifier participates in multiple sequential interactive proof executions for a fixed NP statement x. In every execution, the adversarial verifier is additionally allowed to leak a fraction of the (secret) memory of the prover. This is in contrast to the recently introduced notion of leakage-resilient zero-knowledge (Garg-Jain-Sahai’11) where there is only a single execution. Under multiple executions, in fact the entire prover witness might end up getting leaked thus leading to a complete compromise of prover security. Towards that end, we define the notion of non-transferable proofs for all languages in NP. In such proofs, instead of receiving w as input, the prover will receive an “encoding ” of the witness w such that the encoding is sufficient to prove the validity of x; further, this encoding can be “updated ” to a fresh new encoding for the next execution. We then require that if (x,w) are sampled from a “hard” distribution, then no PPT adversary A ∗ can gain the ability to prove x (on its own) to an honest verifier, even if A ∗ has participated in polynomially many interactive proof executions (with leakage) with an honest prover whose input is (x,w). Non-transferability is a strong security guarantee which suffices for