In a continual memory leakage attack, we consider a cryptosystem which updates its secret state at the end of each execution. An adversary attacking the system can learn arbitrary, but bounded, leakage on its secret state between any two successive updates. The public parameters of the system do not change during updates. Several basic cryptographic primitives, including public-key encryption and signatures, resilient to such attacks are now known.
We consider the task of constructing interactive proofs for NP which can provide meaningful security to a prover's input, in face of continual memory leakage. We imagine a setting where an adversarial verifier receives multiple sequential proofs for a fixed NP statement x; the prover's secret is a witness w for x. The verifier is allowed to learn continual leakage on w. Since there may not exist any natural mechanism to "update" the secret w, eventually entire w can be leaked. It is not clear if any meaningful protection against continual leakage can be provided for the prover.
We therefore introduce encoding-based interactive proofs. 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 time interval. We then aim to construct encoding-based non-transferable proofs for NP even when the verifier can learn continual leakage on prover's state. Non-transferability is a strong security guarantee which suffices for many cryptographic applications. Informally, it states that if (x,w) are sampled from a "hard" distribution, then no PPT adversary A* can gain the ability to prove x to an honest verifier, even if A* has received polynomially many proofs.
We show how to construct non-transferable proofs for all languages in NP which can tolerate leaking a constant fraction of prover's secret-state during each execution. Our construction is in the common reference string (CRS) model. To obtain our results, we build a witness-encoding scheme which satisfies the following continual-leakage-resilience (CLR) properties:
1) The encodings can be randomized to yield a fresh new encoding,
2) No efficient adversary, receiving only a constant fraction of leakage on polynomially many fresh encodings of the same witness, can output a valid encoding provided (x,w) were sampled from a hard distribution.
Our encoding schemes are essentially re-randomizable non-interactive zero-knowledge (NIZK) proofs for circuit satisfiability, with the aforementioned CLR properties. We believe that our CLR-encodings , as well as our techniques to build them, may be of independent general interest.
This is in joint work with Vipul Goyal and Omkant Pandey.