135
ранее. Мы докажем безопасность, фактически показав, что эти атаки являются
единственными из возможных.
Пусть Π будет MAC на основании Конструкции 4.7, и пусть
A будет вероятност-
ным полиноминально-временным злоумышленником. Мы покажем, что Pr[Mac-
forgeAП(n) = 1] является пренебрежимо малым.
Для начала мы представим
определенное обозначение, которое будет использовано в доказательстве. Пусть
Repeat обозначает событие, при котором один и тот же случайный идентификатор
появляется в двух из тегов, возвращенных оракулом MAC в эксперименте Mac-
forgeAП(n). Позволяя (m, t = (r, t1, . . .)) обозначать конечные выходные данные
A, где m = m1, . . . имеет длину A, мы позволяем NewBlock быть событием, когда
по крйней мере один из блоков r||A||i||mi никогда ранее не аутентифицировался
посредством Macr в процессе ответа на A запросы Mac. (Обратие внимание, что
по конструкции Π легко сказать точно, какие блоки аутентифицировались посред-
ством Macr , при вычислении Mack (m).) Неформально, NewBlock - это событие,
когда A пытается вывести действительный тег на блоке, который никогда не был
аутентифицирован соответствующим MAC Πr фиксированной длины.
Мы имеем
Pr[Mac-forgeAП(n) = 1] = Pr[Mac-forgeAП(n) = 1 ^ Repeat]
+ Pr[Mac-forgeAП(n) = 1 ^ eRwepBeloactk^ N ]
+ Pr[Mac-forgeAП(n) = 1 ^ Repeat ^NewBlock] ≤ Pr[Repeat]
(4.3)
+ Pr[Mac-forgeAП(n) = 1 ^ NewBlock]
+ Pr[Mac-forgeAП(n) = 1 ^ Repeat ^ NewBlock].
Мы покажем, что первые два члена Уравнения (4.3) пренебрежимо малы, а
последний член - это 0. Из этого следует, что Pr[Mac-forgeAП(n) = 1] является
пренебрежимо малым, как и планировалось .
Достарыңызбен бөлісу: