Введение в современную криптографию



Pdf көрінісі
бет221/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   217   218   219   220   221   222   223   224   ...   249
Криптография Катц

ОПРЕДЕЛЕНИЕ 7.30 Два вероятностных ансамбля X= Xn}n∈N и c Y 
={Yn}n∈N являются вычислительно неразличимыми, что обозначается как X 
≡ Y, если для каждого вероятностного полиномиально-временного отличитель-
ного признака D существует пренебрежимо малая функция negl , такая что:
. Pr


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)}nN вычислительно неотличим 
от ансамбля {UA(n)}nN.
Многие из других определений и допущений в этой книге, также можно рас-
сматривать как частные случаи или варианты вычислительной неразличимости.
Несколько примеров. Важная теорема о вычислительной неразличимости 
заключается в том, что полиномиально многие образцы (эффективно отбирае-
мые) вычислительно неразличимых ансамблей, также являются вычислитель-
но неразличимыми.
ТЕОРЕМА 7.32 Пусть X и Y будут эффективно отбираемыми вероятностны-
ми ансамблями, которые являются вычислительно неразличимыми.. Тогда для 
каждого полинома p, ансамбль 
является вычисли-
тельно неотличимым от ансамбля
Например, пусть tt будет псевдослучайным генератором с коэффициентом 
расширения 2n, в этом случае ансамбли {tt(Un)}n∈N и {U2n}n∈N будут вы-
числительно неразличимыми. В доказательстве теоремы 7.22 мы показали, что 
для любого полинома t , ансамбли
также являются вычислительно неразличимыми. Теорема 7.32 доказывается с 
помощью гибридного аргумента, точно тем же способом.


304


Достарыңызбен бөлісу:
1   ...   217   218   219   220   221   222   223   224   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет