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 incurring only a constant blowup in share size. Equivocation is a strong leakage-resilience guarantee, recently introduced by Hazay et al. (ITC`21). 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.
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 (CRYPTO03) and Micali and Reyzin (TCC04), 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 incurring only a constant blowup in share size. Equivocation is a strong leakage-resilience guarantee, recently introduced by Hazay et al. (ITC`21). 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.
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.
In this work, we consider the natural goal of designing secret sharing schemes that ensure security against an adversary who may learn some “leaked'' information about all the shares. We say that a secret sharing scheme is p-party leakage-resilient, if the secret remains statistically hidden even after a computationally unbounded adversary learns a bounded amount of leakage, where each bit of leakage adaptively and jointly depends on the shares of an adaptively chosen subset of p parties. Existing multi-party secret sharing schemes (Dziembowski and Pietrzak FOCS 07), (Goyal and Kumar STOC 18) and (Benhamouda, Degwekar, Ishai and Rabin CRYPTO 18) have focused on handling non-adaptive and individual leakage for (limited special cases of) threshold secret sharing schemes. (1) We give an unconditional compiler that transforms any secret sharing scheme on n parties into a p-party leakage-resilient one for p upto O(log n). This yields the first multi-party secret sharing schemes that are secure against adaptive or joint leakage. (2) As a natural extension, we initiate the study of leakage-resilient non-malleable secret sharing. We empower the adversary to adaptively leak from each of the shares and then use the leakage to tamper with all of them arbitrarily and independently. Leveraging our p-party leakage-resilient schemes, we compile any secret sharing scheme into a non-malleable one ensuring that any such tampering either preserves the secret or completely `destroys' it. This improves upon the non-malleable secret sharing scheme of (Goyal and Kumar CRYPTO 18) where no leakage was permitted. Leakage-resilient non-malleable codes can be seen as 2-out-of-2 schemes satisfying our guarantee and have already found many applications in cryptography. (3) Our constructions rely on a clean connection we draw to communication complexity in the well-studied number-on-forehead (NOF) model and rely on functions that have strong communication-complexity lower bounds in the NOF model (in a black-box way). We get efficient p-party leakage-resilient schemes for p upto O(log n) as our share sizes have exponential dependence on p. We observe that improving this exponential dependence, even for simultaneous, non-adaptive leakage, will lead to progress on longstanding open problems in complexity theory.
Side-channel attacks have repeatedly falsified the assumption that cryptosystems are black boxes. Leakage-resilient cryptography studies the robustness of cryptographic constructions when an unforeseen revelation of information occurs. In this context, recently, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO–2018) motivated the study of the local leakage resilience of secret-sharing schemes against an adversary who obtains independent leakage from each secret share.Motivated by applications in secure computation, Benhamouda et al. (CRYPTO–2018) initiated the study of the local leakage resilience of Shamir’s secret-sharing scheme, an essential primitive for nearly all threshold cryptography. The objective is to achieve local leakage resilience with as small a fractional reconstruction threshold as possible. Previously, Benhamouda et al. showed that the reconstruction threshold k being at least 0.907 times the number of parties n is sufficient for Shamir’s secretsharing scheme to be resilient against arbitrary single-bit local leakage from each secret share. After that, Maji et al. (CRYPTO–2021) and Benhamouda et al. (Journal of Cryptology–2021) independently lowered this threshold to k/n ⩾ 0.8675 and k/n ⩾0.85, respectively.This paper contributes to this line of research and proves that k/n ⩾ 0.78 is sufficient. Next, motivated by applications in GMW-style leakage-resilient secure computation, our work extends this bound to a more general adversary who corrupts some parties (obtaining their entire secret shares) and obtains leakage from the remaining honest parties’ secret shares.Our technical analysis proceeds by Fourier analysis and accurately estimates an exponential sum arising in this analysis.
Recently there has been a huge emphasis on constructing cryptographic protocols that maintain their security guarantees even in the presence of side channel attacks. Such attacks exploit the physical characteristics of a cryptographic device to learn useful information about the internal state of the device. Designing protocols that deliver meaningful security even in the presence of such leakage attacks is a challenging task. The recent work of Garg, Jain, and Sahai formulates a meaningful notion of zero-knowledge in presence of leakage; and provides a construction which satisfies a weaker variant of this notion called (1 + ɛ)-leakage-resilient-zero-knowledge, for every constant ɛ> 0. In this weaker variant, roughly speaking, if the verifier learns ℓ bits of leakage during the interaction, then the simulator is allowed to access (1 + ɛ) · ℓ bits of leakage. The round complexity of their protocol is ⌈ n ɛ ⌉. In this work, we present the first construction of leakage-resilient zero-knowledge satisfying the ideal requirement of ɛ = 0. While our focus is on a feasibility result for ɛ = 0, our construction also enjoys a constant number of rounds. At the heart of our construction is a new “public-coin preamble ” which allows the simulator to recover arbitrary information from a (cheating) verifier in a “straight line. ” We use non-black-box simulation techniques to accomplish this goal. 1
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
Leakage-resilient secret sharing has mostly been studied in the compartmentalized models, where a leakage oracle can arbitrarily leak bounded number of bits from all shares, provided that the oracle only has access to a bounded number of shares when the leakage is taking place. We start a systematic study of leakage-resilient secret sharing against global leakage, where the leakage oracle can access the full set of shares simultaneously, but the access is restricted to a special class of leakage functions. More concretely, the adversary can corrupt several players and obtain their shares, as well as applying a leakage function from a specific class to the full share vector. We explicitly construct such leakage-resilient secret sharing with respect to affine leakage functions and low-degree multi-variate polynomial leakage functions, respectively. For affine leakage functions, we obtain schemes with threshold access structure that are leakage-resilient as long as there is a substantial difference between the total amount of information obtained by the adversary, through corrupting individual players and leaking from the full share vector, and the amount that the reconstruction algorithm requires for reconstructing the secret. Furthermore, if we assume the adversary is non-adaptive, we can even make the secret length asymptotically equal to the difference, as the share length grows. Specifically, we have a threshold scheme with parameters similar to Shamir’s scheme and is leakage-resilient against affine leakage. For multi-variate polynomial leakage functions with degree bigger than one, our constructions here only yield ramp schemes that are leakage-resilient against such leakage. Finally, as a result of independent interest, we show that our approach to leakage-resilient secret sharing also yields a competitive scheme compared with the state-of-the-art construction in the compartmentalized models.