Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| УТВЕРЖДЕНИЕ 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): жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|