Candidate Weak Pseudorandom Functions in AC0 o MOD2
- 講者Andrej Bogdanov 教授 (Department of Computer Science and Engineering, The Chinese University of Hong Kong)
邀請人：鐘楷閔 - 時間2014-11-21 (Fri.) 10:00 ~ 12:00
- 地點資訊所新館106演講廳
摘要
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.