<p>I believe the answer is no, due to &quot;algebraic attacks&quot;. That is, take the lowest width (say at most d) term T from the DNF which we denote C.</p>
<p>then T(1+C) = 0, where T has low degree &lt; w</p>
<p>this implies that there exists polynomials p,q of deg &lt; w s.t.</p>
<p>p*C=q</p>
<p>Hence an adversary can distinguish C by guessing the low degree polys p,q.</p>
<p>Paper below proposed an OR-AND-XOR candidate (TRIBES-XOR in fact)
<a href="https://www.alonrosen.net/PAPERS/AC0MOD/ac0mod.pdf" rel="nofollow noreferrer">https://www.alonrosen.net/PAPERS/AC0MOD/ac0mod.pdf</a></p>
<p>But its refuted by section 7.5 below
<a href="https://eprint.iacr.org/2017/652.pdf" rel="nofollow noreferrer">https://eprint.iacr.org/2017/652.pdf</a></p>
<p>A recent work proposes an AND-OR-AND-XOR candidate
<a href="https://link.springer.com/chapter/10.1007/978-3-030-84259-8_17" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007/978-3-030-84259-8_17</a></p>
<p>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).</p>
<p>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.</p>

CC BY-SA 4.0
2022-06-24T12:39:19.707Z
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 ?
ULechine
CC BY-SA 4.0
2022-06-24T19:49:00.507Z
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.
AnonTCS
CC BY-SA 4.0
2022-06-27T14:17:21.907Z
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.
ULechine
CC BY-SA 4.0
2022-06-27T15:25:26.400Z
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
AnonTCS
CC BY-SA 4.0
2022-06-23T18:37:26.087Z
2022-06-23T18:37:26.087Z
AnonTCS
<p>Let <span class="math-container">$F_x : \{0;1\}^n \rightarrow \{0;1\}$</span> be a family of polyomially sized DNF (with respect to <span class="math-container">$n$</span>). The key <span class="math-container">$x$</span> lives in <span class="math-container">$\{0;1\}^{\lambda(n)}$</span>, <span class="math-container">$\lambda(n)$</span> is polynomially bounded in <span class="math-container">$n$</span>.</p>
<p>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.</p>

<pseudorandomness><cryptography>
Can polynomial sized DNF be used to construct weak PRF
ULechine
# Can polynomial sized DNF be used to construct weak PRF

(Asked by: username_0 on 2022-06-23)

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.

**Tags:** pseudorandomness, cryptography

---

## 1 answers

### Answer by username_1 on 2022-06-23. Score: 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.

p\*C=q

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.

> **Comments:**
> **username_0**: 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 ?  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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  

---

