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



Pdf көрінісі
бет66/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   62   63   64   65   66   67   68   69   ...   249
Криптография Катц

ОПРЕДЕЛЕНИЕ 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|, то есть она не пренебредимо мала. 



Достарыңызбен бөлісу:
1   ...   62   63   64   65   66   67   68   69   ...   249




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

    Басты бет