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 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 n ⋅ log O (1) 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 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 n ⋅ log O (1) n and that it fools all parity tests on ≤2 0.9 n 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.

We show that if NC1 ≠ L, then for every element α of the alternating group At, circuits of depth O(log t) cannot distinguish between a uniform vector over (At)t with product = α and one with product = identity. Combined with a recent construction by the author and Viola in the setting of leakage-resilient cryptography [STOC '13], this gives a compiler that produces circuits withstanding leakage from NC1 (assuming NC1 ≠ L). For context, leakage from NC1 breaks nearly all previous constructions, and security against leakage from P is impossible.

We show how to efficiently compile any given circuit C into a leakage-resistant circuit C' such that any function on the wires of C' that leaks information during a computation C'(x) yields advantage in computing the product of |C'|Ω(1) elements of the alternating group Au. In combination with new compression bounds for Au products, also obtained here, C' withstands leakage from virtually any class of functions against which average-case lower bounds are known. This includes communication protocols, and AC0 circuits augmented with few arbitrary symmetric gates. If NC1 ' TC0 then then the construction resists TC0 leakage as well. We also conjecture that our construction resists NC1 leakage. In addition, we extend the construction to the multi-query setting by relying on a simple secure hardware component. We build on Barrington's theorem [JCSS '89] and on the previous leakage-resistant constructions by Ishai et al. [Crypto '03] and Faust et al. [Eurocrypt '10]. Our construction exploits properties of Au beyond what is sufficient for Barrington's theorem.