期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we have candidates computable by
(1) circuits of size n polylog n (thus using a seed of length |k| < n polylog n);
(2) TC^0 circuits of size n^{1+e}, for any e > 0, using a seed of length |k| = O(n);
(3) for each fixed seed k of length |k| = O(n^2), a single-tape Turing machine with O(n^2) states running in time O(n^2).
Candidates (1) and (3) are natural asymptotic generalizations of AES with a specific setting of parameters; (2) deviates somewhat from AES, by relaxing a certain state permutation in AES to have larger range. We argue that the hardness of the candidates relies on similar considerations as those
available for AES.
Assuming our candidates are secure, their improved efficiency brings the "Natural Proofs Barrier" by Razborov and Rudich (JCSS '97) closer to the frontier of circuit lower bounds. For example, the fact that standard pseudorandom function candidates could not be computed as efficiently as the one in (2) had given rise to a plan for TC^0 circuit lower bounds (Allender and Koucky; J. ACM 2010).
We also study the (asymptotic generalization of the) AES S-box. We exhibit a simple attack for the multi-bit output, while we show that outputting one, Goldreich-Levin bit results in a small-bias generator.
关键词：Advanced encryption standard (AES), circuit, Cryptanalysis, exponential hardness, lower bound, natural proofs, pseudorandom function (PRF), TC^0, Turing machine
