**Substitution-permutation networks, pseudorandom functions, and Natural Proofs**

*Eric Miles and Emanuele Viola*

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

**Category / Keywords: **foundations / Advanced encryption standard (AES), circuit, exponential hardness, lower bound, natural proofs, pseudorandom function (PRF), TC^0, Turing machine

**Publication Info: **This is the full version of a paper in CRYPTO 2012

**Date: **received 8 May 2011, last revised 31 May 2012

**Contact author: **enmiles at ccs neu edu

**Available format(s): **PDF | BibTeX Citation

**Note: **This revision contains changes to the structure of Candidate 3, and contains strengthened security proofs for Candidates 2 and 3. Candidate 1 is completely new in this revision. (PDF file corrected from revision 2.)

**Version: **20120531:160246 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]