Let $F_x : \{0;1\}^n \rightarrow \{0;1\}$ be a family of polyomially sized DNF (with respect to $n$). The key $x$ lives in $\{0;1\}^{\lambda(n)}$, $\lambda(n)$ is polynomially bounded in $n$.

Can such a family constitute a weak pseudo random function family ? It would be in a way the smallest possible family function capable of being a weak PRF. I'm interested in knowing if there was any research on this topic.


1 Answer 1


I believe the answer is no, due to "algebraic attacks". That is, take the lowest width (say at most d) term T from the DNF which we denote C.

then T(1+C) = 0, where T has low degree < w

this implies that there exists polynomials p,q of deg < w s.t.


Hence an adversary can distinguish C by guessing the low degree polys p,q.

Paper below proposed an OR-AND-XOR candidate (TRIBES-XOR in fact) https://www.alonrosen.net/PAPERS/AC0MOD/ac0mod.pdf

But its refuted by section 7.5 below https://eprint.iacr.org/2017/652.pdf

A recent work proposes an AND-OR-AND-XOR candidate https://link.springer.com/chapter/10.1007/978-3-030-84259-8_17

They show no such T as above exists (but its an open question to prove their candidate does not correlate with any such T, in which case the same attack would go through).

And I believe you can rule out general AC0 circuits (without XOR layer) by the Linial Mansour Nisan Fourier decomposition of AC0 circuits, which says the Fourier spectrum is concentrated on small known set of coefficients.

  • $\begingroup$ I may be missing something but here goes : why couldn't the width $w$ be of order for instance $\sqrt(n)$, then guessing such polynomials would take superpolynomial time ? $\endgroup$
    – ULechine
    Jun 24 at 12:39
  • $\begingroup$ good question, we can assume the minimum width w = O(logn). If say every term has width sqrt(n), then the support of the DNF < poly(n)*2^(n-sqrt(n) <<< 2^(n-1). In other words the DNF will be very biased to 0, so its not a good PRF already. $\endgroup$
    – AnonTCS
    Jun 24 at 19:49
  • $\begingroup$ Let's go back to guessing the term T and forget p and q, if I'm not mistaken your approach would yield an attack in $n^w$ (n choose w), so $n^{log(n)}$ in our case, because you have to decide which $log(n)$ literal you're gonna choose amongst $x_1,...,x_n$. Now if we actually do the technique with p and q it's even worse i think, because yes the degree of each monome is small but how many monomes are there ? Are there any bound on that. I'm interested in knowing. Actually your remark even if factually wrong helped me construct an attack. $\endgroup$
    – ULechine
    Jun 27 at 14:17
  • $\begingroup$ we are working with polynomials over F_2 (since inputs are over 0,1 then x1^2=x1 aka they are multilinear). Hence there are n choose d polys of degree d $\endgroup$
    – AnonTCS
    Jun 27 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.