Яосский тест - Yaos test

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

Официальное заявление

Булевы схемы

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

${\displaystyle p_{k,S}^{C}={\mathcal {P}}[C_{k}(s)=1|s\in S_{k}{\text{ with probability }}\mu _{k}(s)]}$

Кроме того, пусть ${\displaystyle p_{k,U}^{C}}$ быть вероятностью того, что ${\displaystyle C_{k}(s)=1}$ на входе ${\displaystyle s}$ а ${\displaystyle P(k)}$выбрана длинная -битная последовательность равномерно случайно в ${\displaystyle \{0,1\}^{P(k)}}$. Мы говорим что ${\displaystyle S}$ проходит тест Яо, если для всех предсказаний коллекции ${\displaystyle C}$, для всех, кроме конечного числа ${\displaystyle k}$, для всех полиномов ${\displaystyle Q}$ :

${\displaystyle |p_{k,S}^{C}-p_{k,U}^{C}|<{\frac {1}{Q(k)}}}$

Вероятностная формулировка

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

Рекомендации

1. Эндрю Чи-Чи Яо. Теория и приложения секретных функций. В материалах 23-го симпозиума IEEE по основам компьютерных наук, 1982 г.