132
дывает, что его оракул является псевдослучайной функцией. В противном случае, D
угадывает, что его оракул является случайной функцией. Более подробно:
Дистинктор D:
D получает вход 1n и доступ к оракулу O : {0, 1}n → {0, 1}n, и работает сле-
дующим образом:
1. Запустить A(1n). Каждый раз, когда A посылает запрос его оракулу КАСа
для сообщения m (т.е. когда A запрашивает тэг для сообщения m), ответить на
запрос следующим образом:
Послать запрос
O с m и получить ответ t; вернуть A ответ t .
2. Когда A выдает (m, t) в конце своей работы, делать следующее:
(a) Послать запрос O с m и получить ответ tˆ.
(b) Если (1) tˆ = t и (2) A никогда не посылал своему оракулу КАСа запрос для m,
то выдать
1; в противном случае выдать 0. Очевидно, что D работает в полиномиальном времени.
Заметим, что если оракул дистинктора Dявляется псевдослучайной функци-
ей, то вид A , когда он запускается дистинктором D как субрутина, распределен
идентично виду A в эксперименте Mac-forgeA,Π(n). Кроме того, D выдает 1,
именно когда Mac-forgeA,Π(n) = 1.
Следовательно,
где k ∈ {0, 1}n выбирается равномерно. Если оракул D — это случайная
функция, то вид A , когда он запускается дистинктором D как субрутина, рас-
пределен идентично виду в эксперименте Mac-forgeA,Π(n) и сноваD выдает 1
именно тогда, когда Mac-forgeA,Π(n)=1A,Π˜.
Таким образом,
где f ∈Funcn выбирается равномерно.
Так как F — псевдослучайная функция, и D работает в полиномиальном
времени, то существует пренебрежимо малая функция negl , такая что:
Из этого следует Уравнение (4.2), что и требовалось доказать.
___________________________________________________________
³Если использовать псевдослучайную функцию, которая принимает на входе данные произ-
вольной длины, Конструкция 4.5 может быть использована для построения КАС для сообщений
произвольной длины. Таким же образом,
псевдослучайная функция