Candidate Weak Pseudorandom Functions in AC0 o MOD2
- LecturerProf. Andrej Bogdanov (Department of Computer Science and Engineering, The Chinese University of Hong Kong)
Host: Kai-Min Chung - Time2014-11-21 (Fri.) 10:00 ~ 12:00
- LocationAuditorium 106 at new IIS Building
Abstract
Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However they are inherently sequential: Razborov and Rudich showed that PRFs cannot be implemented in the class AC0(MOD2). Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications.
We study the minimal complexity requirements for constructing weak PRFs. To this end, we present a candidate construction of a weak PRF in the class AC0 o MOD2. We show that our PRF is not approximable by GF(2) polynomials of low degree and has negligible correlation with any fixed Boolean function family of sub-exponential size.
We also initiate a study of the class AC0 o MOD2 that captures the complexity of our construction. We conjecture that all functions in this class have a Fourier coefficient of magnitude exp(−polylogn) and prove this conjecture in two cases: (1) when the AC0 function is a DNF and (2) when the MOD2 function is typical.