Введение в современную криптографию



Pdf көрінісі
бет98/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   94   95   96   97   98   99   100   101   ...   249
Криптография Катц

УТВЕРЖДЕНИЕ 4.9  Pr[Repeat] является незначительным .
ДОКАЗАТЕЛЬСТВО Пусть q(n) будет количеством запросов оракула MAC, 
выполненных A. Чтобы ответить на запрос оракула i от A, оракул единообразно вы-
бирает ri из набора размером 2n/4. Вероятность события Repeat равна вероятности 
того, что ri = rj для некоторых i ƒ= j. Применяя «границу дней рождения» (Лемма А. 
(Lemma A.)15), мы имеем то, что Pr[Repeat]
. Поскольку A выполняет толь-
ко полиномиально много запросов, это значение является пренебрежимо малым.
Далее мы рассмотрим последний член с правой стороны Уравнения (4.3).
Мы утверждаем, что, если Mac-forgeAП(n) = 1, но Repeat не возникает, тогда это 
должно быть тот случай, когда возникает NewBlock. То есть Mac-forgeAП(n) = 
1^ Repeat вызывает NewBlock, и поэтому
Pr[Mac-forgeAП(n) = 1 ^ Repeat ^ =Ne0wBlock].


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): 


Достарыңызбен бөлісу:
1   ...   94   95   96   97   98   99   100   101   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет