Тест следующего бита - Next-bit test

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

Точное заявление (я)

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

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

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

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

${\displaystyle 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)]}$

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

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

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

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

${\displaystyle 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)]}$

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

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

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

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

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

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

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

Позволять ${\displaystyle 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)}\}}$. У нас есть: ${\displaystyle R_{k,0}=\{0,1\}^{P(k)}}$ и ${\displaystyle R_{k,P(k)}=S_{k}}$. Затем мы замечаем, что ${\displaystyle \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)}}}$. Следовательно, хотя бы один из ${\displaystyle |p_{k,R_{k,i+1}}^{\mathcal {M}}-p_{k,R_{k,i}}^{\mathcal {M}}|}$ не должно быть меньше чем ${\displaystyle {\frac {1}{Q(k)P(k)}}}$.

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

${\displaystyle \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}}$

${\displaystyle {\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}}$

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

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

использованная литература

1. Эндрю Чи-Чи Яо. Теория и приложения секретных функций. В материалах 23-го симпозиума IEEE по основам компьютерных наук, 1982 г.
2. Мануэль Блюм и Сильвио Микали, Как генерировать криптографически стойкие последовательности псевдослучайных битов, в SIAM J. COMPUT., Vol. 13, No. 4, ноябрь 1984 г.