176
ведите (m* , mi).
Очевидно, что C работает в полиномиальном времени. Давайте проанализи-
руем его поведение. Если входные данные для C генерируются работающим
GenH (1n) для получения s, видимость Ar при работе в качестве подпрограммы
C распространяется идентично видимости Ar в эксперименте Mac-forge A ,Π t
t (n). В
частности, теги, полученные Ar от C
имеют такое же распространение,
как и теги, которые Ar получает отMac-forge A ,Π. Поскольку C выводит колли-
зию сразу же,
как случается coll, мы
имеем
Pr[Hash-collC,ΠH (n) = 1] = Pr[coll].
Так как ΠH
является стойкой к коллизии, сделаем вывод, что Pr[coll] прене-
брежимо мала.
Теперь продолжим доказывать, что второй член в Уравнении (5.1) пренебре-
жимо малым. Рассмотрите следующего злоумышленника A, атакующего Π в
Mac-forge A ,Π(n):
Достарыңызбен бөлісу: