Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs

This paper takes a new step towards closing the troubling gap between pseudorandom functions (PRF) and their popular, bounded-input-length counterparts. This gap is both quantitative, because these counterparts are more efficient than PRF in various ways, and methodological, because these counterparts usually fit in the substitution-permutation network paradigm (SPN) which has not been used to construct PRF.

We give several candidate PRF

$\mathcal{F}_i$

that are inspired by the SPN paradigm. This paradigm involves a “substitution function” (S-box). Our main candidates are:

$\mathcal{F}_1 : \{0, 1\}^n \to \{0, 1\}^n$

is an SPN whose S-box is a random function on

b

bits given as part of the seed. We prove unconditionally that

$\mathcal{F}_1$

resists attacks that run in time ≤ 2

εb

. Setting

$b = \omega(\lg n)$

we obtain an inefficient PRF, which however seems to be the first such construction using the SPN paradigm.

$\mathcal{F}_2 : \{0, 1\}^n \to \{0, 1\}^n$

is an SPN where the S-box is (patched) field inversion, a common choice in practical constructions.

$\mathcal{F}_2$

is computable with Boolean circuits of size

n

·log

O

(1)

n

, and in particular with seed length

n

·log

O

(1)

n

. We prove that this candidate has exponential security 2

Ω(

n

)

against linear and differential cryptanalysis.

$\mathcal{F}_3 : \{0, 1\}^n \to \{0, 1\}$

is a non-standard variant on the SPN paradigm, where “states” grow in length.

$\mathcal{F}_3$

is computable with size

n

1 + 

ε

, for any

ε

 > 0, in the restricted circuit class TC

0

of unbounded fan-in majority circuits of constant-depth. We prove that

$\mathcal{F}_3$

is almost 3-wise independent.

$\mathcal{F}_4 : \{0, 1\}^n \to \{0, 1\}$

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 fools all parity tests that look at ≤ 2

0.9

n

outputs.

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

$\mathcal{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

.