Revision #1 Authors: Eric Miles, Emanuele Viola

Accepted on: 9th December 2011 22:59

Downloads: 2919

Keywords:

This paper takes a new step towards closing the troubling gap between

pseudorandom functions (PRF) and their popular, bounded-input-length

counterpart: block ciphers. This gap is both quantitative, because

block-ciphers are more efficient than PRF in various ways, and methodological,

because block-ciphers usually fit in the substitution-permutation network

paradigm (SPN) which has no counterpart in PRF.

We give several candidate PRF $F_i$ that are inspired by the SPN paradigm.

This paradigm involves a ``substitution function'' (S-box). Our main

candidates are:

$F_1 : \zo^n \to \zo^n$ is an SPN whose S-box is a random function on $b=O(\lg

n)$ bits, given as part of the seed. We prove unconditionally that $F_1$

resists attacks that run in time $\le 2^{\eps b}$. Setting $b = \omega(\lg n)$

we obtain an inefficient PRF, which however seems to be the first such

construction using the SPN paradigm.

$F_2 : \zo^n \to \zo^n$ is an SPN where the S-box is (patched) field

inversion, a common choice in block ciphers. $F_2$ is computable with Boolean

circuits of size $n \cdot \log^{O(1)} n$, and in particular with seed length

$n \cdot \log^{O(1)} n$. We prove that this candidate has exponential security

$2^{\Omega(n)}$ against linear and differential cryptanalysis.

$F_3 : \zo^n \to \zo$ is a non-standard variant on the SPN paradigm, where

``states'' grow in length. $F_3$ is computable with size $n^{1+\eps}$, for any

$\eps > 0$, in the restricted circuit class $\tcz$ of unbounded fan-in

majority circuits of constant-depth. We prove that $F_3$ is almost $3$-wise

independent.

$F_4 : \zo^n \to \zo$ uses an extreme setting of the SPN parameters (one

round, one S-box, no diffusion matrix). The S-box is again (patched) field

inversion. We prove that this candidate is a small-bias generator (for tests

of weight up to $2^{0.9 n}$).

Assuming the security of our candidates, our work also narrows the gap between

the``Natural Proofs barrier'' [Razborov \& Rudich; JCSS '97] and existing

lower bounds, in three models: unbounded-depth circuits, TC$^0$ circuits, and

Turing machines. In particular, the efficiency of the circuits computing $F_3$

is related to a result by Allender and Koucky [JACM '10] who show that a lower

bound for such circuits would imply a lower bound for TC$^0$.

TR11-076 Authors: Eric Miles, Emanuele Viola

Publication: 7th May 2011 19:08

Downloads: 3822

Keywords:

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 have candidates computable by

(1) circuits of size n polylog n (thus using a seed of length |k| < n polylog n);

(2) TC^0 circuits of size n^{1+e}, for any e > 0, using a seed of length |k| = O(n);

(3) for each fixed seed k of length |k| = O(n^2), a single-tape Turing machine with O(n^2) states running in time O(n^2).

Candidates (1) and (3) are natural asymptotic generalizations of AES with a specific setting of parameters; (2) deviates somewhat from AES, by relaxing a certain state permutation in AES to have larger range. We argue that the hardness of the candidates relies on similar considerations as those

available for AES.

Assuming our candidates are secure, their improved efficiency brings the "Natural Proofs Barrier" by Razborov and Rudich (JCSS '97) closer to the frontier of circuit lower bounds. For example, the fact that standard pseudorandom function candidates could not be computed as efficiently as the one in (2) had given rise to a plan for TC^0 circuit lower bounds (Allender and Koucky; J. ACM 2010).

We also study the (asymptotic generalization of the) AES S-box. We exhibit a simple attack for the multi-bit output, while we show that outputting one, Goldreich-Levin bit results in a small-bias generator.