Shielding Circuits with Groups: Eric Miles, Northeastern

Abstract: Traditionally, cryptography models an adversary as having only input/output access to a given algorithm. A recent line of work known as leakage-resistant cryptography additionally gives the adversary the output of a computationally limited leakage function applied to the algorithm's internal state (e.g. to the wires of a circuit implementing the algorithm). A general goal in this area is to compile any circuit into a new "shielded" circuit that remains secure under these attacks. In this work we give a new such compiler, producing shielded circuits that withstand leakage from virtually any class of functions against which average-case lower bounds are known, recovering and extending previous results. Specifically, our circuits derive their security from the hardness of computing iterated products over the alternating group A_5. We also conjecture that our circuits withstand NC^1 leakage if NC^1 is not equal to L. We build on previous constructions by Ishai et al. [Crypto ’03] and Faust et al. [Eurocrypt ’10], and also use and extend the relationship between group theory and computation first established by Barrington [STOC '86]. In particular we exploit properties of the alternating group beyond what is sufficient for Barrington's theorem. This is joint work with Emanuele Viola.