Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОПРЕДЕЛЕНИЕ 3.14
| Формальное определение. Как уже говорилось выше, tt является генерато-
ром псевдослучайных чисел, если ни один эффективный дистинктор не может определить, задана ли ему строка, выданная tt, или строка, равномерно выбранная случайным образом. Как и в определении 3.9, это формализовано требованием того, что каждый эффективный алгоритм выводит 1 практически с той же веро- ятностью, когда задана tt(s) (для равномерного начального числа s) или равно- мерная строка. (За равносильным определением, аналогичным определению 3.8, обратитесь к упражнению 3.5.) Мы получаем определение в асимптотическом окружении, допуская, что параметр безопасности n определяет длину начального числа. Затем мы настаиваем на том, что tt может быть вычислен эффективным алгоритмом. Формально, нам также необходимо, чтобы выходные данные tt были длиннее входных, иначе tt не является полезным или интересным. ОПРЕДЕЛЕНИЕ 3.14 Пусть A - многочлен, и пусть tt - это детерминиро- ванный полиномиально-временной алгоритм, такой что для любого n и любого введенного s ∈ {0, 1}n, результатом tt(s) является строка длиной A(n). Мы гово- рим, что tt – псевдослучайный генератор, если выполняются следующие условия: 1. (Расширение:) Для каждого n справедливо, что A(n) > n. 2. (Псевдослучайность:) Для любого ppt алгоритма D существует пренебре- жимо малая функция negl, такая что 73 где первая вероятность вычисляется над равномерно выбранными s ∈ {0, 1}n и произвольным D, а вторая вероятность вычисляется по равномерно выбран- ным r ∈ {0, 1}A(n) и произвольным D. Мы называем A коэффициентом расширения tt. Приведем пример небезопасного генератора псевдослучайных чисел, чтобы ознакомиться с определением. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|