Paper 2011/226
Substitutionpermutation 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, boundedinputlength 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 substitutionpermutation 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'' (Sbox). Our main candidates are: 1. F_1 : {0,1}^n > {0,1}^n is an SPN whose Sbox 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 Sbox 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 nonstandard 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 fanin majority circuits of constantdepth. 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 Sbox, no diffusion matrix). The Sbox is again (patched) field inversion. We prove that this candidate is a smallbias 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: unboundeddepth 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.
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.)
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. This is the full version of a paper in CRYPTO 2012
 Keywords
 Advanced encryption standard (AES)circuitexponential hardnesslower boundnatural proofspseudorandom function (PRF)TC^0Turing machine
 Contact author(s)
 enmiles @ ccs neu edu
 History
 20120531: last of 2 revisions
 20110512: received
 See all versions
 Short URL
 https://ia.cr/2011/226
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/226, author = {Eric Miles and Emanuele Viola}, title = {Substitutionpermutation networks, pseudorandom functions, and Natural Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2011/226}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/226}}, url = {https://eprint.iacr.org/2011/226} }