Revision #1 Authors: Chin Ho Lee, Emanuele Viola

Accepted on: 10th March 2016 16:12

Downloads: 727

Keywords:

We exhibit $\epsilon$-biased distributions $D$

on $n$ bits and functions $f\colon \{0,1\}^n

\to \{0,1\}$ such that the xor of two independent

copies ($D+D$) does not fool $f$, for any of the

following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is in NC$^2$;

3. $\epsilon = n^{-\log^{\Omega(1)} n}$ and $f$ is in AC$^0$;

4. $\epsilon = n^{-c}$ and $f$ is a one-way space $O(c \log n)$ algorithm, for any $c$;

5. $\epsilon = n^{-0.029}$ and $f$ is a mod $3$ linear function.

All the results give one-sided distinguishers, and extend to the xor of

more copies for suitable $\epsilon$.

Meka and Zuckerman (RANDOM 2009) prove 5 with $\epsilon =

O(1)$. Bogdanov, Dvir, Verbin, and Yehudayoff (Theory Of

Computing 2013) prove 2 with $\epsilon = 2^{-O(\sqrt{n})}$. Chen

and Zuckerman (personal communication) give an alternative

proof of 4.

1-4 are obtained via a new and simple connection

between small-bias distributions and error-correcting

codes. We also give a conditional result for DNF

formulas, and show that $5$-wise independence

does not hit mod $3$ linear functions.

The previous version made an unconditional claim about AC^0. But the proof had a gap. We do not know that the claim is false. But this version does not make it.

TR15-005 Authors: Chin Ho Lee, Emanuele Viola

Publication: 5th January 2015 14:46

Downloads: 1453

Keywords:

We exhibit $\epsilon$-biased distributions $D$

on $n$ bits and functions $f\colon \{0,1\}^n

\to \{0,1\}$ such that the xor of two independent

copies ($D+D$) does not fool $f$, for any of the

following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is in NC$^2$;

3. $\epsilon = n^{-\log^{\Omega(1)} n}$ and $f$ is in AC$^0$;

4. $\epsilon = n^{-c}$ and $f$ is a one-way space $O(c \log n)$ algorithm, for any $c$;

5. $\epsilon = n^{-0.029}$ and $f$ is a mod $3$ linear function.

All the results give one-sided distinguishers, and extend to the xor of

more copies for suitable $\epsilon$.

Meka and Zuckerman (RANDOM 2009) prove 5 with $\epsilon =

O(1)$. Bogdanov, Dvir, Verbin, and Yehudayoff (Theory Of

Computing 2013) prove 2 with $\epsilon = 2^{-O(\sqrt{n})}$. Chen

and Zuckerman (personal communication) give an alternative

proof of 4.

1-4 are obtained via a new and simple connection

between small-bias distributions and error-correcting

codes. We also give a conditional result for DNF

formulas, and show that $5$-wise independence

does not hit mod $3$ linear functions.