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

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.