Shielding circuits with groups

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'| Ω(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 ' TC 0 then then the construction resists TC 0 leakage as well. We also conjecture that our construction resists NC 1 leakage. 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.

Authors

• Eric Miles
• Emanuele Viola

Keywords

• leakage-resistant cryptography