We show how to efficiently compile any given circuit Cinto a leakage-resistant circuit C such that anyfunction on the wires of C that leaks informationduring a computation C(x) yields advantage incomputing the product of C(1) elementsof the alternating group Au. In combination with newcompression bounds for Au products, also obtainedhere, C withstands leakage from virtually any classof functions against which average-case lower bounds areknown. This includes communication protocols, and AC0circuits augmented with few arbitrary symmetric gates. IfNC1=TC0 then the construction resists TC0leakage as well. We also conjecture that our constructionresists NC1 leakage. In addition, we extend theconstruction to the multi-query setting by relying on asimple secure hardware component.

We build on Barrington's theorem [JCSS '89] and on theprevious leakage-resistant constructions by Ishai et al.\[Crypto '03] and Faust et al.\ [Eurocrypt '10]. Ourconstruction exploits properties of Au beyond what issufficient for Barrington's theorem.