Substitution-Permutation
Networks, Pseudorandom Functions, and Natural Proofs
Eric
Miles (Northeastern University)
Emanuele Viola
(Northeastern University)
Abstract:
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 F_i
that are inspired by the SPN paradigm. This paradigm involves a “substitution
function” (S-box). Our main candidates are:
1. F_1 : {0,1}^n -> {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 F_1 resists attacks that run in time at most 2^{Omega(b)}. Setting b = omega(log
n) we obtain an inefficient PRF, which however seems to be the first such
construction using the SPN paradigm.
2. F_2 : {0,1}^n -> {0,1}^n is an SPN where the
S-box is (patched) field inversion, a common choice in practical constructions.
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^{Omega(n)}
against linear and differential cryptanalysis.
3. F_3 : {0,1}^n -> {0,1} 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 TC0 of
unbounded fan-in majority circuits of constant-depth. We prove that F_3 is
almost $3$-wise independent.
4. F_4 : {0,1}^n -> {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 is a
small-bias generator (for tests of weight up to 2^{0.9n}).
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, TC0 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 TC0.