Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-003 | 5th March 2014 19:43

Shielding circuits with groups

RSS-Feed




Revision #2
Authors: Eric Miles, Emanuele Viola
Accepted on: 5th March 2014 19:43
Downloads: 463
Keywords: 


Abstract:

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 to TR13-003 | 25th February 2014 13:42

Shielding circuits with groups





Revision #1
Authors: Eric Miles, Emanuele Viola
Accepted on: 25th February 2014 13:42
Downloads: 378
Keywords: 


Abstract:

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.



Changes to previous version:

Discussion of OCL, and conjectures.


Paper:

TR13-003 | 2nd January 2013 17:45

Shielding circuits with groups





TR13-003
Authors: Eric Miles, Emanuele Viola
Publication: 2nd January 2013 17:46
Downloads: 1215
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint