Revision #2 Authors: Eric Miles, Emanuele Viola

Accepted on: 5th March 2014 19:43

Downloads: 846

Keywords:

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.

Revision #1 Authors: Eric Miles, Emanuele Viola

Accepted on: 25th February 2014 13:42

Downloads: 747

Keywords:

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.

TR13-003 Authors: Eric Miles, Emanuele Viola

Publication: 2nd January 2013 17:46

Downloads: 2279

Keywords:

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.