Protecting Circuits from Computationally-Bounded Leakage.
Sebastian Faust, Leonid Reyzin, Eran Tromer · 2009
Abstract. 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. 1