How to Compute under AC^0
Leakage without Secure Hardware
Guy Rothblum (Microsoft Research
Abstract:
We study the problem of computing securely in the presence of leakage on the
computation's internals. Our main result is a general compiler that compiles
any algorithm $P$, viewed as a boolean circuit,
into a functionally equivalent algorithm $P'$. The compiled $P'$ can then be
run repeatedly on adversarially chosen inputs in
the presence of leakage on its internals: In each execution of $P'$, an
$AC^0$ adversary can (adaptively) choose any leakage function that can be
computed in $AC^0$ and has bounded output length, apply it to the values on $P'$'s internal wires in that execution, and view its
output. We show that no such leakage adversary can learn more than $P$'s input-output behavior. In particular, the internals
of $P$ are protected.
Security does not rely on any secure hardware, and is proved under a
computational intractability assumption regarding the hardness of computing
inner products for $AC^0$ circuits with pre-processing. This new assumption
has connections to long-standing open problems in complexity theory.