136
Это, в
какой-то степени, является сердцем доказательства.
И снова, пусть q = q(n) обозначает количество запросов оракула MAC, выпол-
ненных A, и пусть ri обозначает случайный идентификатор, используемый для
ответа на запрос оракула i A. Если Repeat не возникает, тогда значения r1, . . . ,
rq будут разными. Пусть (m, t = (r, t1, . . .)) будут выходными данными A при m =
m1, . . .. Если r ƒ∉ {r1, . . . , rq }, тогда явно явно NewBlock. Если нет, тогда r = rj
для какого-то уникального j, а блоки r»A»1»m1, . . ., возможно, не будут аутенти-
фицированы в процессе ответа какому-либо запросу Mac, отличному от такого
запроса j. Пусть m(j) будет сообщением, использованным A для своего запроса
оракула j, и пусть Aj будет его длиной. Для рассмотрения имеется два случая:
Случай1: A ƒ≠ Aj . Блоки, аутентифиицированные во время ответа на запрос Mac
j, все имеют Aj ƒ≠ A во второй позиции. Поэтому r»A»1»m1,в частности, никогда
не аутетифицировался во
время ответа на запрос Mac j, и происходит NewBlock.
Case 2: A = Aj . Если Mac-forgeAП(n)= 1, тогда мы должны иметь m ƒ= m(j).
Пусть 1 , . . .. Так как m и m(j) имеют идентичную длину, должен быть по крайней
мере один индекс i, для которого mi =ƒ m(j). Блок r»A»i»mi, таким образом,
никогда не был аутентифицирован в процессе ответа на запрос Mac j. (Потому что
i включено в третью позицию блока, блок r»A»i»mi , возможно, мог бы быть аутен-
тифицирован, если бы r»A»i»mi = rj «Aj «i»m(j), но это неверно, так как mi ƒ≠ m(j).)
Чтобы закончить доказательство теоремы, мы ограничим второй член правой
стороны Уравнения (4.2):
Достарыңызбен бөлісу: