Введение в современную криптографию
Простые иллюстрации модели со случайным оракулом
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Случайный оракул как псевдослучайный генератор.
| Простые иллюстрации модели со случайным оракулом
На этом этапе полехзными могут оказаться некоторые примеры. Примеры, приве- денные здесь относительно просты и не используют все возможности, которые дает модель со случайным оракулом. Скорее, эти примеры представлены только, чтобы обеспечить плавное введение в модель. В дальнейшем мы предполагаем случайного оракула, преобразующего Ain-битные входные данные Aout-битные выходные дан- ные, где Ain, Aout > n, параметр защиты (поэтому Ain, Aout являютс функциями n). Случайный оракул как псевдослучайный генератор. Сначала мы пока- жем, что для Aout > Ain случайный оракул может быть использован в качестве псевдослучайного генератора. (Мы не говорим, что случайный оракул является псевдослучайным генератором, так как случайны оракул не является фиксиро- ванной функцией.) Строго говоря, мы утверждаем, что для любого ppt злоу- мышленника A существует пренебрежимо малая функция negl такая, что 196 . где в первом случае вероятность берется из универсального выбора H, универсаль- ного выбора y ∈{0, 1}Aout(n) и произвольности A, и во втором случае вероятность берется из универсального выбора H, универсального выбора x ∈{0, 1}Ain(n) и произвольности A. Мы явно указали, что A имеет доступ оракула к H в каждом из случаев; как только H выбран, A может свободно подавать ему запроcы. Пусть S обозначает набор точек, по которым A опросил H; конечно же, |S| яв- ляется полиномиальным в n. Заметьте, что во втором случае вероятность того, что x ∈ S - пренебрежимо мала. Это справедливо, если A начинает без инфор- мации об x (обратите внимание, что H(x) сама по себе ничего не показывает об x, потому что H является случайно функцией), и потмоу что S - экспоненциаль- но меньше, чем {0, 1}Ain. Кроме того, зависящий от x ƒ∉ S во втором случае входной элемент A в каждом случае является универсальной строкой, которая независима от ответов на запросы от A. Случайный оркул вкачестве стойкой к коллизиям хэш-функции. Если Aout< Ain, случайный оракул является стойким к коллизиям. То есть вероятность успеха любого ppt злоумышленника A в следующем эксперименте - пренебрежимо мала: 1. Выбрана случайная функция H . 2. A достигает успеха, если он выводит различные x, xr при H(x) = H(xr). Чтобы это увидеть предположим без потери обобщенности, что A выводит только значения x, xr , которые он ранее запрашивал у оракула, и что A не делает один и тот же запрос оракулу дважды. Разрешив запросам оракулу от A быть x1, . . . , xq при q = poly(n), становится ясно, что вероятность того, что A достигнет успеха ограничивается вероятностью того, что H(xi) = H(xj ) для некоторых i ƒ= j. Но эта вероятность ровно такая же, как и вероятность того, что, если мы возь- мем q строк y1, . . . , yq ∈ {0, 1}Aout назависимо и единообразно случайным об- разом, у нас будет yi = yj для некоторых i ƒ= j. Это точь в точь проблема «дней рождений», и поэтому, используя результаты Дополнения A.4, мы имеем то, что A достиг успеха с пренебрежимо малой вероятностью O(q2/2Aout ). жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|