Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Псевдослучайность и псевдослучайные генераторы.
- ОПРЕДЕЛЕНИЕ 7.31
- (Расширение:)
- ТЕОРЕМА 7.32
| ОПРЕДЕЛЕНИЕ 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)}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 доказывается с помощью гибридного аргумента, точно тем же способом. |