Access Restriction

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

   Open content in new tab
Source: ACM Digital Library