Abstract | ||
---|---|---|
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 many cryptographic applications (and in particular, implies witness hiding). 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-resilient (CLR) properties: The encodings can be randomized to yield a fresh new encoding, There does not exist any efficient adversary, who receiving only a constant fraction of leakage on polynomially many fresh encodings of the same witness w, can output a valid encoding provided that the witness w along with its corresponding input instance x 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 interest. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1007/978-3-662-44381-1_10 | ADVANCES IN CRYPTOLOGY - CRYPTO 2014, PT II |
DocType | Volume | ISSN |
Journal | 8617 | 0302-9743 |
Citations | PageRank | References |
9 | 0.48 | 41 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Prabhanjan Ananth | 1 | 234 | 18.43 |
Vipul Goyal | 2 | 2859 | 129.53 |
Omkant Pandey | 3 | 2015 | 82.24 |