Пример 3.15
Определим tt(s) выводить s вместе с
, таким образом, коэффициент
расширения tt составляет A(n) = n + 1. Выходные данные tt можно легко от-
личить от однородных.
Рассмотрим следующий эффективный дистинктор D: на входе строка w, на
выходе 1 тогда и только тогда, когда конечный бит w равносилен операции
исключающего ИЛИ всех предшествующих битов w. Поскольку эта харак-
теристика верна для всех строк, выведенных tt, имеем Pr[D(tt(s)) = 1] = 1. С
другой стороны, если w является равномерной, последний бит w является рав-
номерным, и тогда Pr[D(w)=1]=1/2. Количество |1/2 − 1| является постоянным,
не пренебрежимо малым, и, таким образом, данный tt не является генератором
псевдослучайных чисел. (Обратите внимание, что D не всегда «корректен», по-
скольку иногда выводит 1 даже когда задана равномерная строка. Это не меняет
того факта, что D является хорошим дистинктором.)
♦
Обсуждение. Распределение выходных данных генератора псевдослучайных чи-
сел tt далеко от равномерного. Рассмотрим для наглядности случай, когда A(n)=2n
и тогда tt удваивает длин входных данных. При равномерном распределении по {0,
1}2n, каждая из 22n возможных строк выбирается с вероятностью ровно 2−2n. Для
сравнения рассмотрим распределение вывода tt (когда tt запущен по начальному чис-
лу). Когда tt получает входные данные длиной n, число различных строк в диапазоне
tt составляет максимум 2n. Относительное количество строк длиной 2n, находящихся
в диапазоне tt, таким образом, составляет максимум 2n/22n = 2−n, и мы видим, что по-
давляющая часть строк длиной 2n не встречаются в виде выходных данных tt.
В частности, это означает, что легко отличить случайные строки от псев-
дослучайных, заданных неограниченное число раз. Пусть tt останется тем,
что указано выше, и рассмотрим экспоненциально-временной дистинктор D,
работающий следующим образом: D(w) выводит 1 тогда и только тогда, когда
существует s ∈ {0, 1}n, такое что tt(s) = w. (Это вычисление осуществляется в
экспоненциальном времени путем тщательной обработки tt(s) для каждого s ∈
{0, 1}n. Напомним, что по принципу Керкгоффса характеристика tt известна D.)
Теперь, если w была выведена tt, тогда D выводит 1 с вероятностью 1. Напро-
тив, если w равномерно распределена по {0, 1}2n, тогда вероятность существо-
74
вания s при tt(s) = w составляет максимум 2−n, и тогда D выводит в этом случае
1 с вероятностью максимум 2−n. Таким образом,
Pr[D(r) = 1] − Pr[D(tt(s)) = 1]. ≥ 1 − 2−n,
являющееся большим. Это еще один пример атаки методом перебора, кото-
рый не противоречит псевдослучайности tt, поскольку атака не эффективна.
Достарыңызбен бөлісу: |