Aug 19 – 23
Santa Barbara




How to Compute under AC^0 Leakage without Secure Hardware


Guy Rothblum (Microsoft Research Silicon Valley)


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.




Back to Conference Program