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|, то есть она не пренебредимо мала.
♦
Достарыңызбен бөлісу: