Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

A Parallel Repetition Theorem for Leakage Resilience

Zvika Brakerski, Yael Tauman Kalai

Published Jan 1, 2012• 11 citations
Publisher
DOI
10.1007/978-3-642-28914-9_14

Related papers

Parallel Repetition for Leakage Resilience Amplification Revisited

Abhishek Jain, Krzysztof Pietrzak

Lecture notes in computer science•Jan 1, 2011•11 citations

An Efficient Parallel Repetition Theorem

Johan Håstad, Rafael Pass, Douglas Wikström +1 more

Lecture notes in computer science•Jan 1, 2010•46 citations

A Parallel Repetition Theorem for Leakage Resilience.

Zvika Brakerski, Yael Tauman Kalai

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 λ 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λ bits of leakage? Surprisingly, Lewko and Waters (FOCS 2010) showed that this is false. They gave an example of a public-key encryption scheme that is (CPA) resilient to λ bits of leakage, and yet its 2-repetition is not resilient to even (1 + ɛ)λ bits of leakage. In their counter-example, 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 non-trivial leakage resilience), parallel repetition does in fact amplify leakage (for CPA security). In particular, if fresh public parameters are used for each copy of the Lewko-Waters 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 λ1,..., λt bits of leakage, respectfully, their direct product is resilient to ∑ (λi − 1) bits. We present our amplification theorem in a general framework that applies other cryptographic primitives as well.

•Jan 1, 2011•0 citations

On the Insecurity of Parallel Repetition for Leakage Resilience

Allison Bishop Lewko, Brent R. Waters

A fundamental question in leakage-resilient cryptography is: can leakage resilience always be amplified by parallel repetition? It is natural to expect that if we have a leakage-resilient primitive tolerating ℓ bits of leakage, we can take n copies of it to form a system tolerating nℓ bits of leakage. In this paper, we show that this is not always true. We construct a public key encryption system which is secure when at most ℓ bits are leaked, but if we take n copies of the system and encrypt a share of the message under each using an n-out-of-n secret-sharing scheme, leaking nℓ bits renders the system insecure. Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption or in prime order bilinear groups under the decisional linear assumption. We note that the n copies of our public key systems share a common reference parameter.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•13 citations

Forward Security Under Leakage Resilience, Revisited

Suvradip Chakraborty, Harish Karthikeyan, Adam O’Neill +1 more

Lecture notes in computer science•Jan 1, 2023•3 citations

On the Insecurity of Parallel Repetition for Leakage Resilience.

Allison Bishop Lewko, Brent R. Waters

A fundamental question in leakage-resilient cryptography is: can leakage resilience always be amplified by parallel repetition? It is natural to expect that if we have a leakage-resilient primitive tolerating ℓ bits of leakage, we can take n copies of it to form a system tolerating nℓ bits of leakage. In this paper, we show that this is not always true. We construct a public key encryption system which is secure when at most ℓ bits are leaked, but if we take n copies of the system and encrypt a share of the message under each using an n-out-of-n secret-sharing scheme, leaking nℓ bits renders the system insecure. Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption or in prime order bilinear groups under the decisional linear assumption. We note that the n copies of our public key systems share a common reference parameter. 1

•Jan 1, 2010•1 citation
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 λ 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λ bits of leakage? Surprisingly, Lewko and Waters (FOCS 2010) showed that this is false. They gave an example of a public-key encryption scheme that is (CPA) resilient to λ bits of leakage, and yet its 2-repetition is not resilient to even (1 + ɛ)λ bits of leakage. In their counter-example, 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 non-trivial leakage resilience), parallel repetition does in fact amplify leakage (for CPA security). In particular, if fresh public parameters are used for each copy of the Lewko-Waters 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 λ1,..., λt bits of leakage, respectfully, their direct product is resilient to ∑ (λi − 1) bits. We present our amplification theorem in a general framework that applies other cryptographic primitives as well.
A fundamental question in leakage-resilient cryptography is: can leakage resilience always be amplified by parallel repetition? It is natural to expect that if we have a leakage-resilient primitive tolerating ℓ bits of leakage, we can take n copies of it to form a system tolerating nℓ bits of leakage. In this paper, we show that this is not always true. We construct a public key encryption system which is secure when at most ℓ bits are leaked, but if we take n copies of the system and encrypt a share of the message under each using an n-out-of-n secret-sharing scheme, leaking nℓ bits renders the system insecure. Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption or in prime order bilinear groups under the decisional linear assumption. We note that the n copies of our public key systems share a common reference parameter.
A fundamental question in leakage-resilient cryptography is: can leakage resilience always be amplified by parallel repetition? It is natural to expect that if we have a leakage-resilient primitive tolerating ℓ bits of leakage, we can take n copies of it to form a system tolerating nℓ bits of leakage. In this paper, we show that this is not always true. We construct a public key encryption system which is secure when at most ℓ bits are leaked, but if we take n copies of the system and encrypt a share of the message under each using an n-out-of-n secret-sharing scheme, leaking nℓ bits renders the system insecure. Our results hold either in composite order bilinear groups under a variant of the subgroup decision assumption or in prime order bilinear groups under the decisional linear assumption. We note that the n copies of our public key systems share a common reference parameter. 1