Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Пример 3.26
| ОПРЕДЕЛЕНИЕ 3.25 Пусть F :{0, 1}*×{0, 1}*→{0, 1}* будет эффек-
тивной, сохраняющей длину функцией с ключом. F является псевдослучайной функцией если для всех вероятностных полиномиальных дистинкторов D, су- ществует пренебрежимо малая функция negl, такая что: где первая вероятность вычисляется над равномерно выбранными k∈ {0, 1} n и произвольным D, а вторая вероятность вычисляется над равномерно вы- бранными f ∈Funcn и и произвольным D. Важно отметить, что дистинктору D не дается ключ k. Требование о псевдос- лучайности Fk не имеет смысла, если нам исвестна k , так как при известной k задача отличить оракул для Fk от оракула для f является тривиальной. (Все, что требуется от дистинктора, это послать запрос оракулу в любой точке x , чтобы полу- чить ответ y, и сранить полученное с результатом yr := Fk (x), который он вычисляет сам с помощью известного значения k. Оракул для Fk вернет y = yr, тогда как ора- кул для произвольной функции будет иметь y = yr с вероятностью лишь 2−n.) Это означает, что если k известна, никакие утверждения о псевдослучайности Fk не имеют силу. Рассмотрим конкретный пример. Если F — произвольная функция, то при оракульном доступе к функции Fk (для единообразной k) должно быть сложно найти такой входной параметр x , для которого Fk (x) = 0n (так как было бы сложно найти такой входной параметр для действительно произвольной функции f ). Но если k известна, найти такой параметр может быть просто. Пример 3.26 Как полагается, мы можем лучше ознакомиться с определением, рассмотрев нестойкий пример. Определим сохраняющей длину функцию с ключом F как F (k, x) = k⊕x. Для любого входного x, значение Fk (x) равномерно распределено 92 (когда k единообразна). Несмотря на это, F не является псевдослучайной, так как ее значения в любых двух точках не взаимосвязаны. Конкретнее, рассмо- трим дистинктор D, который дает запросы оракулу O в произвольных, различ- ных точках x1, x2 , и получет значения y1 = O(x1) и y2 = O(x2), и выдает 1 тогда и только тогда, когда y1⊕y2 = x1⊕x2. Если O = Fk для любой k, то D выдает 1. С другой стороны, если O = f для f равномерно выбранной из Funcn, то вероят- ность того, что f (x1)⊕f (x2) = x1⊕x2 равна вероятности того, что f (x2) = x1⊕ x2⊕f (x1), или 2−n, а D выдает 1 с этой же самой вероятностью. Разность равна |1 − 2−n|, то есть она не пренебредимо мала. ♦ жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|