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

A Parallel Repetition Theorem for Leakage Resilience.

Zvika Brakerski, Yael Tauman Kalai

Published Jan 1, 2011• 0 citations
OpenAlex

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 λ 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.

Related papers

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

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

Leakage-Resilient Public-Key Cryptography in the Bounded-Retrieval Model.

Joël Alwen, Yevgeniy Dodis, Daniel Wichs

We study the design of cryptographic primitives resilient to key-leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random-Oracle model. This protocol ensures that session keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext. Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage ℓ (potentially many gigabytes of

•Jan 1, 2009•0 citations

Continual Leakage-Resilient Hedged Public-Key Encryption

Meijuan Huang, Bo Yang, Yanwei Zhou +1 more

Abstract Hedged public-key encryption (HPKE), introduced by Bellare et al. (ASIACRYPT 2009), provides useful security when the per-message randomness fails to be uniform due to faulty implementations or adversarial actions. The HPKE scheme achieves IND-CPA (chosen plaintext attack) security when the randomness they used is of high quality, but, when the randomness is poor quality, rather than breaking completely, it achieves a weaker but a useful notion of security called IND-CDA (chosen distribution attack) as long as the message and randomness together have sufficient min-entropy. However, little research on HPKE in the presence of key leakage was done. In this paper, we study HPKE featuring key leakage-resilience and formulate appropriate security notion for key leakage-resilient HPKE. We work in the continual key leakage model where the secret key is refreshed periodically and an adversary can learn arbitrary but bounded leakage on the secret key between the updates. We present two generic constructions of continual leakage-resilient HPKE in the standard model by using a continual leakage-resilient all-but-one lossy trapdoor function. Finally, we give an instantiation of leakage-resilient HPKE under the linear assumption in bilinear groups.

The Computer Journal•Jan 1, 2021•5 citations

Post-Challenge Leakage Resilient Public-Key Cryptosystem in Split State Model

Eiichiro Fujisaki, Akinori Kawachi, Ryo Nishimaki +2 more

Leakage resilient cryptography is often considered in the presence of a very strong leakage oracle: An adversary may submit arbitrary efficiently computable function f to the leakage oracle to receive f(x), where x denotes the entire secret that a party possesses. This model is somewhat too strong in the setting of public-key encryption (PKE). It is known that no secret-key leakage resilient PKE scheme exists if the adversary may have access to the secret-key leakage oracle to receive only one bit after it was given the challenge ciphertext. Similarly, there exists no sender-randomness leakage resilient PKE scheme if one-bit leakage occurs after the target public key was given to the adversary. At TCC 2011, Halevi and Lin have broken the barrier of after-the-fact leakage, by proposing the so-called split state model, where a secret key of a party is explicitly divided into at least two pieces, and the adversary may have not access to the entire secret at once, but each divided pieces, one by one. In the split-state model, they have constructed post-challenge secret-key leakage resilient CPA secure PKEs from hash proof systems, but the construction of CCA secure post-challenge secret-key leakage PKE has remained open. They have also remained open to construct sender-randomness leakage PKE in the split state model. This paper provides a solution to the open issues. We also note that the proposal of Halevi and Lin is post-challenge secret-key leakage CPA secure against a single challenge ciphertext; not against multiple challenges. We present an efficient generic construction that converts any CCA secure PKE scheme into a multiple-challenge CCA secure PKE that simultaneously tolerates post-challenge secret-key and sender-randomness leakage in the split state model, without any additional assumption. In addition, our leakage amount of the resulting schemes is the same as that of Halevi and Lin CPA PKE, i.e., (1/2+γ)l/2 where l denotes the length of the entire secret (key or randomness) and γ denotes a universal (possitive) constant less than 1/2. Our conversion is generic and available for many other public-key primitives. For instance, it can convert any identity-based encryption (IBE) scheme to a post-challenge master-key leakage and sender-randomness leakage secure IBE.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2015•3 citations

Protecting Distributed Primitives Against Leakage: Equivocal Secret Sharing and more

Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss

Abstract Leakage-resilient cryptography aims to protect cryptographic primitives from so-called “side channel attacks” that exploit their physical implementation to learn their input or secret state. Starting from the works of Ishai, Sahai and Wagner (CRYPTO‘03) and Micali and Reyzin (TCC‘04), most works on leakage-resilient cryptography either focus on protecting general computations, such as circuits or multiparty computation protocols, or on specific non-interactive primitives such as storage, encryption, and signatures. This work focuses on leakage resilience for the middle ground, namely for distributed and interactive cryptographic primitives. Our main technical contribution is designing the first secret sharing scheme that is equivocal, resists adaptive probing of a constant fraction of bits from each share, while incurs only a constant blowup in share size. Equivocation is a strong leakage-resilience guarantee, recently introduced by Hazay et al. (ITC, 2021). Our construction is obtained via a general compiler which we introduce, that transforms any secret sharing scheme into an equivocal scheme against adaptive leakage. An attractive feature of our compiler is that it respects additive reconstruction; namely, if the original scheme has additive reconstruction, then the transformed scheme has linear reconstruction. We extend our compiler to a general paradigm for protecting distributed primitives against leakage and show its applicability to various primitives, including secret sharing, verifiable secret sharing, function secret sharing, distributed encryption and signatures, and distributed zero-knowledge proofs. For each of these primitives, our paradigm transforms any construction of the primitive into a scheme that resists adaptive party corruptions, as well as adaptive probing leakage of a constant fraction of bits in each share when the share is stored in memory (but not when it is used in computations). Moreover, the transformation incurs only a constant blowup in the share size and respects additive reconstruction—an important feature for several of these primitives, such as function secret sharing and distributed encryption.

Journal of Cryptology•Oct 30, 2024•3 citations
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. 1
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.
We study the design of cryptographic primitives resilient to key-leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter ℓ. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random-Oracle model. This protocol ensures that session keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext. Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage ℓ (potentially many gigabytes of
Abstract Hedged public-key encryption (HPKE), introduced by Bellare et al. (ASIACRYPT 2009), provides useful security when the per-message randomness fails to be uniform due to faulty implementations or adversarial actions. The HPKE scheme achieves IND-CPA (chosen plaintext attack) security when the randomness they used is of high quality, but, when the randomness is poor quality, rather than breaking completely, it achieves a weaker but a useful notion of security called IND-CDA (chosen distribution attack) as long as the message and randomness together have sufficient min-entropy. However, little research on HPKE in the presence of key leakage was done. In this paper, we study HPKE featuring key leakage-resilience and formulate appropriate security notion for key leakage-resilient HPKE. We work in the continual key leakage model where the secret key is refreshed periodically and an adversary can learn arbitrary but bounded leakage on the secret key between the updates. We present two generic constructions of continual leakage-resilient HPKE in the standard model by using a continual leakage-resilient all-but-one lossy trapdoor function. Finally, we give an instantiation of leakage-resilient HPKE under the linear assumption in bilinear groups.
Leakage resilient cryptography is often considered in the presence of a very strong leakage oracle: An adversary may submit arbitrary efficiently computable function f to the leakage oracle to receive f(x), where x denotes the entire secret that a party possesses. This model is somewhat too strong in the setting of public-key encryption (PKE). It is known that no secret-key leakage resilient PKE scheme exists if the adversary may have access to the secret-key leakage oracle to receive only one bit after it was given the challenge ciphertext. Similarly, there exists no sender-randomness leakage resilient PKE scheme if one-bit leakage occurs after the target public key was given to the adversary. At TCC 2011, Halevi and Lin have broken the barrier of after-the-fact leakage, by proposing the so-called split state model, where a secret key of a party is explicitly divided into at least two pieces, and the adversary may have not access to the entire secret at once, but each divided pieces, one by one. In the split-state model, they have constructed post-challenge secret-key leakage resilient CPA secure PKEs from hash proof systems, but the construction of CCA secure post-challenge secret-key leakage PKE has remained open. They have also remained open to construct sender-randomness leakage PKE in the split state model. This paper provides a solution to the open issues. We also note that the proposal of Halevi and Lin is post-challenge secret-key leakage CPA secure against a single challenge ciphertext; not against multiple challenges. We present an efficient generic construction that converts any CCA secure PKE scheme into a multiple-challenge CCA secure PKE that simultaneously tolerates post-challenge secret-key and sender-randomness leakage in the split state model, without any additional assumption. In addition, our leakage amount of the resulting schemes is the same as that of Halevi and Lin CPA PKE, i.e., (1/2+γ)l/2 where l denotes the length of the entire secret (key or randomness) and γ denotes a universal (possitive) constant less than 1/2. Our conversion is generic and available for many other public-key primitives. For instance, it can convert any identity-based encryption (IBE) scheme to a post-challenge master-key leakage and sender-randomness leakage secure IBE.
Abstract Leakage-resilient cryptography aims to protect cryptographic primitives from so-called “side channel attacks” that exploit their physical implementation to learn their input or secret state. Starting from the works of Ishai, Sahai and Wagner (CRYPTO‘03) and Micali and Reyzin (TCC‘04), most works on leakage-resilient cryptography either focus on protecting general computations, such as circuits or multiparty computation protocols, or on specific non-interactive primitives such as storage, encryption, and signatures. This work focuses on leakage resilience for the middle ground, namely for distributed and interactive cryptographic primitives. Our main technical contribution is designing the first secret sharing scheme that is equivocal, resists adaptive probing of a constant fraction of bits from each share, while incurs only a constant blowup in share size. Equivocation is a strong leakage-resilience guarantee, recently introduced by Hazay et al. (ITC, 2021). Our construction is obtained via a general compiler which we introduce, that transforms any secret sharing scheme into an equivocal scheme against adaptive leakage. An attractive feature of our compiler is that it respects additive reconstruction; namely, if the original scheme has additive reconstruction, then the transformed scheme has linear reconstruction. We extend our compiler to a general paradigm for protecting distributed primitives against leakage and show its applicability to various primitives, including secret sharing, verifiable secret sharing, function secret sharing, distributed encryption and signatures, and distributed zero-knowledge proofs. For each of these primitives, our paradigm transforms any construction of the primitive into a scheme that resists adaptive party corruptions, as well as adaptive probing leakage of a constant fraction of bits in each share when the share is stored in memory (but not when it is used in computations). Moreover, the transformation incurs only a constant blowup in the share size and respects additive reconstruction—an important feature for several of these primitives, such as function secret sharing and distributed encryption.