Substitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs

This article takes a new step towards closing the 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. Most of our candidates are more efficient than previous ones. Our main candidates are as follows.

—F₁ : {0,1}ⁿ → {0,1}ⁿ is an SPN whose S-box is a random function on b bits given as part of the seed. We prove that F₁ resists attacks that run in time ≤ 2^ϵb.

—F₂ : {0,1}ⁿ → {0,1}ⁿ is an SPN where the S-box is (patched) field inversion, a common choice in practical constructions. We show that F₂ is computable with boolean circuits of size n ⋅ log^O(1) n and that it has exponential security 2^Ω(n) against linear and differential cryptanalysis.

—F₃ : {0,1}ⁿ → {0,1} is a nonstandard variant on the SPN paradigm, where “states” grow in length. We show that F₃ is computable with TC⁰ circuits of size n^{1 + ϵ}, for any ϵ > 0, and that it is almost 3-wise independent.

—F₄ : {0,1}ⁿ → {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 show that F₄ is computable by circuits of size n ⋅ log^O(1) n and that it fools all parity tests on ≤2^0.9n outputs.

Assuming the security of our candidates, our work narrows the gap between the Natural Proofs barrier and existing lower bounds in three models: circuits, TC⁰ circuits, and Turing machines.