### Substitution-Permutation Networks, Pseudorandom Functions, and Natural ProofsSubstitution-Permutation Networks, Pseudorandom Functions, and Natural Proofs

Access Restriction
Subscribed

 Author Miles, Eric ♦ Viola, Emanuele Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Advanced Encryption Standard ♦ Pseudorandom function ♦ Natural proofs ♦ Substitution-permutation network Abstract 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_{1}$ : ${0,1}^{n}$ → ${0,1}^{n}$ is an SPN whose S-box is a random function on $\textit{b}$ bits given as part of the seed. We prove that $F_{1}$ resists attacks that run in time ≤ $2^{εb}.$ $—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. We show that $F_{2}$ is computable with boolean circuits of size $\textit{n}$ ṡ $log^{O(1)}$ $\textit{n}$ and that it has exponential security $2^{Ω(n)}$ against linear and differential cryptanalysis. $—F_{3}$ : ${0,1}^{n}$ → {0,1} is a nonstandard variant on the SPN paradigm, where “states” grow in length. We show that $F_{3}$ is computable with $TC^{0}$ circuits of size $\textit{n}1$ + ε, for any ε > 0, and that it is almost 3-wise independent. $—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 show that $F_{4}$ is computable by circuits of size $\textit{n}$ ṡ $log^{O(1)}$ $\textit{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^{0}$ circuits, and Turing machines. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-12-10 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 6 Page Count 29 Starting Page 1 Ending Page 29

#### Open content in new tab

Source: ACM Digital Library