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.
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.
We consider the problem of distributing a computation between two parties, such that any bounded-communication leakage function applied to the local views of the two parties reveals essentially nothing about the input. This problem can be motivated by the goal of outsourcing computations on sensitive data to two servers in the cloud, where both servers can be simultaneously corrupted by viruses that have a limited communication bandwidth. We present a simple and efficient reduction of the above problem to that of constructing parity-resilient circuits, namely circuits that map an encoded input to an encoded output so that the parity of any subset of the wires is essentially independent of the input. We then construct parity-resilient circuits from circuits that are resilient to local leakage, which can in turn be obtained from protocols for secure multiparty computation. Our main reduction builds on a novel generalization of the ε-biased masking lemma that applies to interactive protocols. Applying the above, we obtain two-party protocols with resilience to bounded-communication leakage either in the information-theoretic setting, relying on random oblivious transfer correlations, or in the computational setting, relying on non-committing encryption which can be based on a variety of standard cryptographic assumptions.
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.
The notion of secure computation is central to cryptography. Introduced in the seminal works of Yao [FOCS'82, FOCS'86] and Goldreich, Micali and Wigderson [STOC'87], secure multiparty computation allows a group of (mutually) distrustful parties to jointly compute any functionality over their individual private inputs in such a manner that the honest parties obtain the correct outputs and no group of malicious parties learn anything beyond their inputs and the prescribed outputs. General feasibility results for secure computation were given by Yao [FOCS'86] and Goldreich et al. [STOC'87] more than two decades ago. Subsequent to these works, designing secure computation protocols that can tolerate more powerful adversaries and satisfy stronger notions of security has been a very active area of research. In this dissertation, we study two such new frontiers in the area of secure computation.
In the first part of this dissertation, we initiate a study of designing leakage-resilient interactive protocols. Specifically, we consider the scenario where an adversary, in addition to corrupting a subset of parties, can leak (potentially via physical attacks) arbitrary information from the secret state of any honest party. This is in contrast to the standard notion of secure computation where it is assumed that the adversary only has black-box'' access to the honest parties. In particular, we formalize a meaningful definition of leakage-resilient zero knowledge proof systems and provide constructions that satisfy our notion. We also discuss various applications of our results.
The second part of this dissertation concerns with the general question of whether it is possible to securely run cryptographic protocols over an insecure network environment such as the Internet. It is well-known that the standard notion of secure computation is only relevant to the stand-alone setting where a single protocol is being executed in isolation; as such it does not guarantee security when multiple protocol sessions may be executed concurrently under the control of an adversary who is present across all sessions. We consider the open problem of constructing secure password-based authenticated key exchange protocols in such a setting in the plain model (i.e., without assuming any trusted infrastructure or random oracles). We give the first construction of such a protocol based on standard cryptographic assumptions. Our results are in fact much more general, and extend to other functionalities w.r.t. a (necessarily) weakened notion of concurrently secure computation.
The results presented in this dissertation stem from two papers which are joint works with Sanjam Garg and Amit Sahai, and with Vipul Goyal and Rafail Ostrovsky, respectively.
We study the question of designing leakage-resilient secure computation protocols. Our model is that of only computation leaks information with a leak-free input encoding phase. In more detail, we assume an offline phase called the input encoding phase in which each party encodes its input in a specified format. This phase is assumed to be free of any leakage and may or may not depend upon the function that needs to be jointly computed by the parties. Then finally, we have a secure computation phase in which the parties exchange messages with each other. In this phase, the adversary gets access to a leakage oracle which allows it to download a function of the computation transcript produced by an honest party to compute the next outgoing message.
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.
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.