We show how to efficiently compile any given circuit $C$
into a leakage-resistant circuit $\widehat{C}$ such that any
function on the wires of $\widehat{C}$ that leaks information
during a computation $\widehat{C}(x)$ yields advantage in
computing the product of $|\widehat{C}|^{\Omega(1)}$ elements
of the alternating group $A_u$. In combination with new
compression bounds for $A_u$ products, also obtained
here, $\widehat{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 \ne TC^0$ 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.
We show how to efficiently compile any given circuit $C$
into a leakage-resilient circuit $\widehat{C}$ such that any
function on the wires of $\widehat{C}$ that leaks information
during a computation $\widehat{C}(x)$ yields advantage in
computing the product of $|\widehat{C}|^{\Omega(1)}$ elements
of the alternating group $A_u$.
Our construction resists NC$^1$ leakage assuming L $\ne$ NC$^1$, as was conjectured here and proven later [Miles, ITCS '14].
Also, in combination with new
compression bounds for $A_u$ products obtained
here, $\widehat{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.
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-resilient 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.
Discussion of OCL, and conjectures.
We show how to efficiently compile any given circuit $C$
into a leakage-resistant circuit $\widehat{C}$ such that any
function on the wires of $\widehat{C}$ that leaks information
during a computation $\widehat{C}(x)$ yields advantage in
computing the product of $|\widehat{C}|^{\Omega(1)}$ elements
of the alternating group $A_u$. In combination with new
compression bounds for $A_u$ products, also obtained
here, $\widehat{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 \ne TC^0$ 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.
