CSAIL Event Calendar

Shielding Circuits with Groups Note -- Unusual starting Time

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.
*Joint Work with Emanuele Viola.

See other events that are part of CIS Seminars 2012/2013

See other events happening in February 2013