Paper 2011/250
A Parallel Repetition Theorem for Leakage Resilience
Zvika Brakerski and Yael Tauman Kalai
Abstract
A leakage resilient encryption scheme is one which stays secure even against an attacker that obtains a bounded amount of side information on the secret key (say $\lambda$ bits of ``leakage''). A fundamental question is whether parallel repetition amplifies leakage resilience. Namely, if we secret share our message, and encrypt the shares under two independent keys, will the resulting scheme be resilient to $2\lambda$ bits of leakage? Surprisingly, Lewko and Waters (FOCS 2010) showed that this is false. They gave an example of a publickey encryption scheme that is (CPA) resilient to $\lambda$ bits of leakage, and yet its $2$repetition is not resilient to even $(1+\epsilon)\lambda$ bits of leakage. In their counterexample, the repeated schemes share secretly generated public parameters. In this work, we show that under a reasonable strengthening of the definition of leakage resilience (one that captures known proof techniques for achieving nontrivial leakage resilience), parallel repetition \emph{does} in fact amplify leakage (for CPA security). In particular, if fresh public parameters are used for each copy of the LewkoWaters scheme, then their negative result does not hold, and leakage is amplified by parallel repetition. More generally, we show that given $t$ schemes that are resilient to $\lambda_1, \ldots, \lambda_t$ bits of leakage, respectfully, their direct product is resilient to $\sum (\lambda_i1)$ bits. We present our amplification theorem in a general framework that applies other cryptographic primitives as well.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Contact author(s)
 zvika brakerski @ weizmann ac il
 History
 20111221: revised
 20110523: received
 See all versions
 Short URL
 https://ia.cr/2011/250
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/250, author = {Zvika Brakerski and Yael Tauman Kalai}, title = {A Parallel Repetition Theorem for Leakage Resilience}, howpublished = {Cryptology ePrint Archive, Paper 2011/250}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/250}}, url = {https://eprint.iacr.org/2011/250} }