Author name cluster

Eric Miles

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

2 author rows

I&C Journal 2018 Journal Article

Local reduction

Hamidreza Jahanjou
Eric Miles
Emanuele Viola

We reduce non-deterministic time T ≥ 2 n to a 3SAT instance ϕ of quasilinear size | ϕ | = T ⋅ log O ( 1 ) ⁡ T such that there is an explicit NC 0 circuit C that encodes ϕ in the following way: on input a ( log ⁡ | ϕ | ) -bit index i, C outputs the ith clause of ϕ. The previous best result was C in NC1. Even in the simpler setting of polynomial size ( | ϕ | = poly ( T ) ), the previous best result was C in AC0. More generally, for any time T ≥ n and parameter r ≤ n we obtain | ϕ | = max ⁡ ( T, 2 n / r ) ⋅ ( n log ⁡ T ) O ( 1 ), and each output bit of C is a decision tree of depth O ( log ⁡ r ). As an application, we tighten Williams' connection between satisfiability algorithms and circuit lower bounds (STOC 2010; SIAM J. Comput. 2013).

Details DOI

STOC Conference 2013 Conference Paper

Shielding circuits with groups

Eric Miles
Emanuele Viola

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'| Ω(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 ' TC 0 then 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.

Details