论文标题
为了区分Goldreich PRG安全性的分布和应用程序的时空权衡
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
论文作者
论文摘要
在这项工作中，我们建立了针对内存有限算法的较低限制，以区分相关分布的自然对与到达流中的样品的自然对。 在我们的第一个结果中，我们表明，任何算法都区分$ \ {0,1 \}^n $上的均匀分布以及$ \ {0,1 \}^n $的$ n/2 $二维线性子空间上的均匀分布，而不是不可能的优势需要$ 2^{n）$ n或$ n^$ n $ n或$ n^$ n.或$ n^$ n^$ n或$ n. 我们的第二个结果适用于区分Goldreich的本地伪和发电机的输出和输出域上的均匀分布。具体而言，Goldreich的pseudorandom Generator $ g $修复了谓词$ p：\ {0,1 \}^k \ rightarrow \ {0,1 \} $和subsets $ s_1，s_2，s_2，\ ldots，s_mm \ s_m \ subseteq [n] $ k $ k $。对于任何种子$ x \ in \ {0,1 \}^n $，它输出$ p（x_ {s_1}），p（x__ {s_2}），\ ldots，p（x_ {s_m}）$其中$ x_ {s_i} $是$ x $ x_ $ s_ $ s_ in $ x $的投资。我们证明，每当$ p $为$ t $ riSIRINIT（所有非零的傅里叶系数为$（-1）^p $都是$ t $或更高的$ t $或更高的），则没有算法，具有$ <n^ε$内存，可以将$ g $的输出与$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ floty n y invore n y ryvevelly的均匀分配区分开\ left（\ frac {n} {t} \ right）^{\ frac {（1-ε）} {36} {36} \ cdot t} $（除非在$ k $上受到一些限制）。下边界在流型模型中保持，其中每个时间步骤$ i $，$ s_i \ subseteq [n] $是一个随机选择的（有序）尺寸$ k $的子集，而dickitisher则可以看到$ p（x_ {s_i}）$或均匀的随机位，以及$ s_i $。 我们的证明是建立在最近开发的用于证明时间间隔权衡的机械（RAZ 2016和后续行动）的基础上，用于搜索/学习问题。
In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. In our first result, we show that any algorithm that distinguishes between uniform distribution on $\{0,1\}^n$ and uniform distribution on an $n/2$-dimensional linear subspace of $\{0,1\}^n$ with non-negligible advantage needs $2^{Ω(n)}$ samples or $Ω(n^2)$ memory. Our second result applies to distinguishing outputs of Goldreich's local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich's pseudorandom generator $G$ fixes a predicate $P:\{0,1\}^k \rightarrow \{0,1\}$ and a collection of subsets $S_1, S_2, \ldots, S_m \subseteq [n]$ of size $k$. For any seed $x \in \{0,1\}^n$, it outputs $P(x_{S_1}), P(x_{S_2}), \ldots, P(x_{S_m})$ where $x_{S_i}$ is the projection of $x$ to the coordinates in $S_i$. We prove that whenever $P$ is $t$-resilient (all non-zero Fourier coefficients of $(-1)^P$ are of degree $t$ or higher), then no algorithm, with $<n^ε$ memory, can distinguish the output of $G$ from the uniform distribution on $\{0,1\}^m$ with a large inverse polynomial advantage, for stretch $m \le \left(\frac{n}{t}\right)^{\frac{(1-ε)}{36}\cdot t}$ (barring some restrictions on $k$). The lower bound holds in the streaming model where at each time step $i$, $S_i\subseteq [n]$ is a randomly chosen (ordered) subset of size $k$ and the distinguisher sees either $P(x_{S_i})$ or a uniformly random bit along with $S_i$. Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups) for search/learning problems.
