Protecting Circuits from Computationally-Bounded Leakage

Sebastian Faust, Leonid Reyzin and Eran Tromer

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 device that maintains secrecy even in the presence of well-defined classes of side-channel leakage. Our construction requires only a minimal leak-proof component: one that draws random elements from a simple distribution. We thus reduce the problem of shielding arbitrary 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 capture the notion of "limited" measurements using computational complexity classes, and our proofs of security rely on the hardness of certain functions for these classes. Thus, for example, AC^0 lower bounds yield a construction that is resilient to any leakage that can be computed by constant-depth circuits. More generally, we give a generic composition theorem that shows how to build a provably secure devices of arbitrary complexity out of components that satisfy a simulatability condition. Several applications are shown.

In contrast to previous works, we allow the side-channel leakage to depend on the whole state and on all the wires in the device, and to grow unbounded over time.

Preliminary version: [pdf] [eprint]
Slides: [PowerPoint] [PDF]

— Eran Tromer