Protecting Circuits from Leakage: The Computationally-Bounded and Noisy Cases

Joint work with Sebastian Faust, Tal Rabin, Eran Tromer, and Vinod Vaikuntanathan

Computational devices leak side-channel information that may, and often does, reveal secret internal states. Such leakage is often not modeled properly by the analysis of security protocols, where the internals of computing devices are simply abstracted away. To make such analysis relevant, computational devices must be fully shielded from the oustide world.

We present a general transformation that compiles any circuit into a new circuit with the same functionality and on top of that with resiliency 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 either in its computational ability (it lacks the ability to decode certain linear encodings and outputs a limited number of bits per iteration) or its precision (each observed bit is flipped with some probability). While our results apply in general to such leakage classes, in particular, we obtain security against:

— Constant-depth circuits leakage, where the measurement apparatus can be computed by an AC0 circuit (composed of NOT gates and unbounded fan-in AND and OR gates), or an ACC0[m] circuit (which is the same as AC[0] except that it also uses mod m gates).

— Noisy leakage, where the measurement apparatus reveals all the bits of the state of the circuit, perturbed by independent binomial noise. Namely, each bit of the computation is perturbed with probability p, and remains unchanged with probability 1-p.