303
В определении D задан одинарный вход 1n , поэтому он может работать в
течение полиномиального времени n. Это важно, когда выходы Xn и Yn могут
иметь длину менее n. В качестве условного обозначения в вероятностных вы-
ражениях,
мы будем иногда записывать X, в качестве заполнителя для случай-
ного образца из расределения X. То есть, будем записывать Pr[D(1n, Xn) = 1]
вместо Prx← X [D(1n, x) = 1].
Отношение вычислительной неразличимости, транзитивно: if X ≡ Y и Y ≡
Z, то X ≡ Z.
Псевдослучайность и псевдослучайные генераторы. Псевдослучайность
– это просто частный случай, вычислительной неразличимости. Пусть для лю-
бого целого A, UA обозначает равномерное распределение по {0, 1}A. Мы
можем определить псевдослучайный генератор следующим образом:
ОПРЕДЕЛЕНИЕ 7.31 Пусть A(•) будет полиномом, а tt – (детерминирован-
ным) полиномиально-временным алгоритмом, где для всех s справедливо, что
|tt(s)| = A(|s|). Мы говорим, что tt – псевдослучайный генератор, если выполня-
ются два следующих условия:
1.
(Расширение:) Для каждого n справедливо, что A(n) > n.
2.
(Псевдослучайность:) Ансамбль {tt(Un)}n∈
N вычислительно неотличим
от ансамбля {UA(n)}n∈
N.
Многие из других определений и допущений в этой книге,
также можно рас-
сматривать как частные случаи или варианты вычислительной неразличимости.
Несколько примеров. Важная теорема о вычислительной неразличимости
заключается в том, что полиномиально многие образцы (эффективно отбирае-
мые) вычислительно неразличимых ансамблей,
также являются вычислитель-
но неразличимыми.
ТЕОРЕМА 7.32 Пусть X и Y будут эффективно отбираемыми вероятностны-
ми ансамблями, которые являются вычислительно неразличимыми.. Тогда для
каждого полинома p, ансамбль
является вычисли-
тельно неотличимым от ансамбля
Например, пусть tt будет псевдослучайным генератором с коэффициентом
расширения 2n, в этом случае ансамбли {tt(Un)}n∈N и {U2n}n∈N
будут вы-
числительно неразличимыми. В доказательстве теоремы 7.22 мы показали, что
для любого полинома t ,
ансамбли
также являются вычислительно неразличимыми. Теорема 7.32 доказывается с
помощью гибридного аргумента, точно тем же способом.