Paper 2013/001
Shielding circuits with groups
Eric Miles and Emanuele Viola
Abstract
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.
Metadata
- Available format(s)
- Publication info
- Published elsewhere. Unknown where it was published
- Contact author(s)
- enmiles @ ccs neu edu
- History
- 2014-03-03: last of 2 revisions
- 2013-01-04: received
- See all versions
- Short URL
- https://ia.cr/2013/001
- License
-
CC BY