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.Category / Keywords: cryptographic protocols / Continual Leakage, Zero Knowledge, Rerandomizable NIZKs Original Publication (in the same form): IACR-CRYPTO-2014 Date: received 24 Aug 2014 Contact author: prabhanjan va at gmail com Available format(s): PDF | BibTeX Citation Version: 20140827:074917 (All versions of this report) Discussion forum: Show discussion | Start new discussion