Тест следующего бита

В криптографии и теории вычислений тест следующего бита это тест на генераторы псевдослучайных чисел . Мы говорим, что последовательность битов проходит следующий битовый тест в любой позиции. $i$ в последовательности, если какой-либо злоумышленник, знающий $i$ первые биты (но не начальное число) не могут предсказать $(i+1)$st с разумной вычислительной мощностью.

Точное утверждение(я)

Позволять $P$ быть полиномом, и $S=\{S_{k}\}$ быть совокупностью множеств таких, что $S_{k}$ содержит $P(k)$-битные длинные последовательности. Более того, пусть $\mu _{k}$ быть распределением вероятностей строк в $S_{k}$.

Теперь мы определяем проверку следующего бита двумя разными способами.

Формулировка логической схемы

Коллекция прогнозов $C=\{C_{k}^{i}\}$ представляет собой совокупность логических схем , каждая из которых $C_{k}^{i}$ имеет меньше чем $P_{C}(k)$ ворота и именно $i$ входы. Позволять $p_{k,i}^{C}$ — вероятность того, что на входе $i$ первые кусочки $s$, строка, случайно выбранная в $S_{k}$ с вероятностью $\mu _{k}(s)$, схема правильно предсказывает $s_{i+1}$, то есть:

$p_{k,i}^{C}={\mathcal {P}}\left[C_{k}(s_{1}\ldots s_{i})=s_{i+1}\right|s\in S_{k}{\text{ with probability }}\mu _{k}(s)]$

Теперь мы говорим, что $\{S_{k}\}_{k}$ проходит проверку следующего бита, если для любой коллекции прогнозов $C$, любой полином $Q$ :

$p_{k,i}^{C}<{\frac {1}{2}}+{\frac {1}{Q(k)}}$

Вероятностные машины Тьюринга

Мы также можем определить тест следующего бита в терминах вероятностных машин Тьюринга , хотя это определение несколько более сильное (см. теорему Адлемана ). Позволять ${\mathcal {M}}$ быть вероятностной машиной Тьюринга, работающей за полиномиальное время. Позволять $p_{k,i}^{\mathcal {M}}$ быть вероятностью того, что ${\mathcal {M}}$ предсказывает $(i+1)$st немного правильно, т.е.

$p_{k,i}^{\mathcal {M}}={\mathcal {P}}[M(s_{1}\ldots s_{i})=s_{i+1}|s\in S_{k}{\text{ with probability }}\mu _{k}(s)]$

Мы говорим, что коллекция $S=\{S_{k}\}$ проходит проверку следующего бита, если для всех полиномов $Q$, для всех, кроме конечного числа $k$, для всех $0<i<k$:

$p_{k,i}^{\mathcal {M}}<{\frac {1}{2}}+{\frac {1}{Q(k)}}$

Полнота теста Яо

Тест следующего бита — это частный случай теста Яо для случайных последовательностей, и поэтому его прохождение является необходимым условием для прохождения теста Яо . также показал это условие Однако Яо достаточное .

Мы докажем это сейчас на примере вероятностной машины Тьюринга, поскольку Адлеман уже проделал работу по замене рандомизации неоднородностью в своей теореме . Случай булевых схем не может быть выведен из этого случая (поскольку он предполагает решение потенциально неразрешимых задач), но доказательство теоремы Адлемана можно легко адаптировать к случаю неоднородных семейств булевых схем.

Позволять ${\mathcal {M}}$ быть отличительным признаком вероятностной версии теста Яо, т.е. вероятностной машины Тьюринга, работающей за полиномиальное время, такой, что существует полиномиальный $Q$ такой, что для бесконечно многих $k$

$|p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}$

Позволять $R_{k,i}=\{s_{1}\ldots s_{i}u_{i+1}\ldots u_{P(k)}|s\in S_{k},u\in \{0,1\}^{P(k)}\}$. У нас есть: $R_{k,0}=\{0,1\}^{P(k)}$ и $R_{k,P(k)}=S_{k}$. Затем мы замечаем, что $\sum _{i=0}^{P(k)}|p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|\geq |p_{k,R_{k,P(k)}}^{\mathcal {M}}-p_{k,R_{k,0}}^{\mathcal {M}}|=|p_{k,S}^{\mathcal {M}}-p_{k,U}^{\mathcal {M}}|\geq {\frac {1}{Q(k)}}$. Следовательно, хотя бы один из $|p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|$ должно быть не меньше ${\frac {1}{Q(k)P(k)}}$.

Далее рассмотрим распределения вероятностей $\mu _{k,i}$ и ${\overline {\mu _{k,i}}}$ на $R_{k,i}$. Распределение $\mu _{k,i}$ — распределение вероятностей выбора $i$ первые кусочки в $S_{k}$ с вероятностью, определяемой выражением $\mu _{k}$и $P(k)-i$ остальные биты равномерно случайным образом. Мы имеем таким образом:

$\mu _{k,i}(w_{1}\ldots w_{P(k)})=\left(\sum _{s\in S_{k},s_{1}\ldots s_{i}=w_{1}\ldots w_{i}}\mu _{k}(s)\right)\left({\frac {1}{2}}\right)^{P(k)-i}$

${\overline {\mu _{k,i}}}(w_{1}\ldots w_{P(k)})=\left(\sum _{s\in S_{k},s_{1}\ldots s_{i-1}(1-s_{i})=w_{1}\ldots w_{i}}\mu _{k}(s)\right)\left({\frac {1}{2}}\right)^{P(k)-i}$

Таким образом, мы имеем $\mu _{k,i}={\frac {1}{2}}(\mu _{k,i+1}+{\overline {\mu _{k,i+1}}})$ (это показывает простой математический трюк), таким образом, распределения $\mu _{k,i+1}$ и ${\overline {\mu _{k,i+1}}}$ можно отличить по ${\mathcal {M}}$. Не ограничивая общности, можно считать, что $p_{\mu _{k,i+1}}^{\mathcal {M}}-p_{\overline {\mu _{k,i+1}}}^{\mathcal {M}}\geq {\frac {1}{2}}+{\frac {1}{R(k)}}$, с $R$ полином.

Это дает нам возможную конструкцию машины Тьюринга, решающей тест следующего бита: после получения $i$ первые биты последовательности, ${\mathcal {N}}$ дополняет этот ввод предполагаемым битом $l$ а потом $P(k)-i-1$ случайные биты, выбранные с равномерной вероятностью. Затем он запускается ${\mathcal {M}}$и выходные данные $l$ если результат $1$, и $1-l$ еще.