Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a circuit with the same functionality but resilience against well-defined classes of leakage. Our construction requires a small, stateless, and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component. Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component), and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited in the amount of output bits per iteration and the ability to decode certain linear encodings. While our results apply in general to such leakage classes, in particular, we obtain security against (a) constant-depth circuits leakage, where the leakage function is computed by an $\mathsf{AC}^0$ circuit (composed of NOT gates and unbounded fan-in AND and OR gates); (b) noisy leakage, where the leakage function reveals all the bits of the internal state of the circuit, but each bit is perturbed by independent binomial noise---i.e., flipped with some probability $p$. Namely, for some number $p\in(0,1/2]$, each bit of the computation is flipped with probability $p$, and remains unchanged with probability $1-p$.
Physical computational devices leak side-channel information that may, and often does, reveal secret internal states. We present a general transformation that compiles any circuit into a circuit with the same functionality but resilience against well-defined classes of leakage. Our construction requires a small, stateless, and computation-independent leak-proof component that draws random elements from a fixed distribution. In essence, we reduce the problem of shielding arbitrarily complex circuits to the problem of shielding a single, simple component. Our approach is based on modeling the adversary as a powerful observer that inspects the device via a limited measurement apparatus. We allow the apparatus to access all the bits of the computation (except those inside the leak-proof component), and the amount of leaked information to grow unbounded over time. However, we assume that the apparatus is limited in the amount of output bits per iteration and the ability to decode certain linear encodings. While our results apply in general to such leakage classes, in particular, we obtain security against (a) constant-depth circuits leakage, where the leakage function is computed by an AC0 circuit (composed of NOT gates and unbounded fan-in AND and OR gates); (b) noisy leakage, where the leakage function reveals all the bits of the internal state of the circuit, but each bit is perturbed by independent binomial noise---i.e., flipped with some probability p. Namely, for some number p∈(0,1/2], each bit of the computation is flipped with probability p, and remains unchanged with probability 1−p.
We consider the question of protecting a general computation device, modeled by a stateful Boolean circuit, against leakage of partial information about its internal wires. Goyal et al. (FOCS 2016) obtained a solution for the case of bounded-communication leakage, where the wires are partitioned into two parts and the leakage can be any function computed using t bits of communication between the parts. However, this solution suffers from two major limitations: (1) it only applies to a one-shot (stateless) computation, mapping an encoded input to an encoded output, and (2) the leakage-resilient circuit consumes fresh random bits, whose number scales linearly with the circuit complexity of the computed function. In this work, we eliminate the first limitation and make progress on the second. Concretely: - We present the first construction of stateful circuits that offer information-theoretic protection against continuous bounded-communication leakage. As an application, we extend a two-party “malware-resilient” protocol of Goyal et al. to the continuous-leakage case. - For simple types of bounded-communication leakage, which leak t parities or t disjunctions of circuit wires or their negations, we obtain a deterministic variant that does not require any fresh randomness beyond the randomness in the initial state. Here we get computational security based on a subexponentially secure one-way function. This is the first deterministic leakage-resilient circuit construction for any nontrivial class of global leakage.
Abstract Transforming any circuit into a circuit with the same functionality but resilience against well-defined classes of leakage is an essential subject of cryptography. Whereas, according to the relationship between VBB and simulated leakage-resilient circuit compiler, the compiling needs a specific mechanism to guarantee that its input is free of any leakage. Unfortunately, it makes it tough to implement this strategy in the context of actual leaks. In this work, we formally propose the indistinguishable bounded leakage-resilient circuit compiler Cˉ to solve the problem mentioned above. Specifically, it specifies that any polynomial-time adversary who derives the bound secret information from the circuit compiler can not distinguish an equivalent compiled circuit Cˉ′ with the same output. To achieve this goal, first, we utilize the leakage-resilient indistinguishable encoding as its input. Second, it takes advantage of the indistinguishability obfuscation (IO) program to construct an obfuscated circuit that removes the random coins of the input encoding . Its total running time is the original circuit C running time plus poly(κ), and the size is independent of the original C. As this new compiler overcomes the restriction of the simulated-based leakage resilient circuit compiler,it will bring an independent interest result in leakage-resilient cryptography.
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.
Physical implementations of cryptographic algorithms leak information, which makes them vulnerable to so-called side-channel attacks.Cryptography is now used in an ever-increasing variety of scenarios, and the assumption that the execution of cryptosystems is physically insulated is often not realistic.The field of leakage resilience proposes to mitigate side-channel attacks by designing protocols that are secure even if information leaks during execution.In this work, we study leakage-resilient computation, which concerns the problem of performing secure universal computation in the presence of leakage.Fault-tolerant quantum computation is concerned with the problem of noise in quantum computers.Since it is very hard to insulate quantum systems from noise, fault tolerance proposes schemes for performing computations correctly even if some noise is present.It turns out that there exists a connection between leakage resilience and fault tolerance.In this work, we show that leakage in a classical circuit is a form of noise, when the circuit is interpreted as quantum.We then prove that for an arbitrary leakage model, there exists a corresponding noise model in which a circuit that is fault-tolerant against the noise model is also resilient against the given leakage model.We also show how to use constructions for fault tolerance to implement classical circuits that are secure in specific leakage models.This is done by establishing criteria in which quantum circuits can be converted into classical circuits in such a way that the leakage resilience property is preserved.Using these criteria, we convert an implementation of universal fault-tolerant quantum computation into a classical leakageresilient compiler, i.e., a scheme that compiles an arbitrary circuit into a circuit of the same functionality that is leakage-resilient.vi 4.9 (a): Circuito de codificação para |0 no código de Steane.O circuito que codifica |+ é o mesmo, com a diferença de que alvos e controles são revertidos, e estados |0 são revertidos em |+ e vice-versa.(b):
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.
We show how to efficiently compile any given circuit C into a leakage-resistant circuit C' such that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing the product of |C'|Ω(1) elements of the alternating group Au. In combination with new compression bounds for Au products, also obtained here, C' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC0 circuits augmented with few arbitrary symmetric gates. If NC1 ' TC0 then then the construction resists TC0 leakage as well. We also conjecture that our construction resists NC1 leakage. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component. We build on Barrington's theorem [JCSS '89] and on the previous leakage-resistant constructions by Ishai et al. [Crypto '03] and Faust et al. [Eurocrypt '10]. Our construction exploits properties of Au beyond what is sufficient for Barrington's theorem.