All reports by Author Eric Miles:

__
TR14-037
| 21st March 2014
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Succinct and explicit circuits for sorting and connectivity

__
TR13-099
| 6th July 2013
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Local reductions

Revisions: 3

__
TR13-003
| 2nd January 2013
__

Eric Miles, Emanuele Viola#### Shielding circuits with groups

Revisions: 2

__
TR12-125
| 2nd October 2012
__

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola#### From RAM to SAT

Revisions: 1

__
TR12-019
| 2nd March 2012
__

Eric Miles, Emanuele Viola#### On the complexity of constructing pseudorandom functions (especially when they don't exist)

__
TR11-076
| 7th May 2011
__

Eric Miles, Emanuele Viola#### The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT

instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$

such that there is an explicit circuit $C$ that on input

an index $i$ of $\log |\phi|$ bits outputs the $i$th

clause, and each output bit of $C$ depends on ...
more >>>

Eric Miles, Emanuele Viola

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 ...
more >>>

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

Common presentations of the NP-completeness of SAT suffer

from two drawbacks which hinder the scope of this

flagship result. First, they do not apply to machines

equipped with random-access memory, also known as

direct-access memory, even though this feature is

critical in basic algorithms. Second, they incur a

quadratic blow-up ...
more >>>

Eric Miles, Emanuele Viola

We study the complexity of black-box constructions of

pseudorandom functions (PRF) from one-way functions (OWF)

that are secure against non-uniform adversaries. We show

that if OWF do not exist, then given as an oracle any

(inefficient) hard-to-invert function, one can compute a

PRF in polynomial time with only $k(n)$ oracle ...
more >>>

Eric Miles, Emanuele Viola

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous

constructions. In particular, we ...
more >>>