Тест Яоса - Википедия - Yaos test

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

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

Булевы схемы

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

Кроме того, пусть быть вероятностью того, что на входе а выбрана длинная -битная последовательность равномерно случайно в . Мы говорим что проходит тест Яо, если для всех предсказаний коллекции , для всех, кроме конечного числа , для всех полиномов  :

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

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

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

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