International Association
for Cryptologic Research

We show how to efficiently compile any given circuit C into a leakage-resistant circuit C\' such that any function on the wires of C\' that leaks information during a computation C\'(x) yields advantage in computing the product of |C\'|^{Omega(1)} elements of the alternating group A_u. In combination with new compression bounds for A_u products, also obtained here, C\' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC^0 circuits augmented with few arbitrary symmetric gates. If NC^1 \\neq TC^0 then then the construction resists TC^0 leakage as well. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component.

We build on Barrington\'s theorem [JCSS \'89] and on the previous leakage-resistant constructions by Ishai et al. [Crypto \'03] and Faust et al. [Eurocrypt \'10]. Our construction exploits properties of A_u beyond what is sufficient for Barrington\'s theorem.