ECCC-Report TR13-003https://eccc.weizmann.ac.il/report/2013/003Comments and Revisions published for TR13-003en-usWed, 05 Mar 2014 19:43:24 +0200
Revision 2
| Shielding circuits with groups |
Eric Miles,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2013/003#revision2We 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.Wed, 05 Mar 2014 19:43:24 +0200https://eccc.weizmann.ac.il/report/2013/003#revision2
Revision 1
| Shielding circuits with groups |
Eric Miles,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2013/003#revision1We 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.Tue, 25 Feb 2014 13:42:44 +0200https://eccc.weizmann.ac.il/report/2013/003#revision1
Paper TR13-003
| Shielding circuits with groups |
Eric Miles,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2013/003We 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.Wed, 02 Jan 2013 17:46:16 +0200https://eccc.weizmann.ac.il/report/2013/003