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



Pdf көрінісі
бет231/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   227   228   229   230   231   232   233   234   ...   249
Криптография Катц

ЛЕММА A.15 Для положительного целого N и, некоторого q, элементы y1, 
. . . , yq выбраны равномерно и независимо на случайной основе из множества 
размера N . Тогда вероятность того, что существуют различные i, j при yi = 
yj не превышает q2/2N. То есть,
ДОКАЗАТЕЛЬСТВО Доказательство – это простое применение границы 
объединения (предположение A.7). Напомним, что коллизия означает, что су-
ществует различные i, j при yi = yj . Пусть Coll обозначает событие коллизии а
Colli,j обозначает событие, что yi = yj . Из этого прямо следует, что Pr[Colli,j]
= /N для любых различных i, j. Кроме того, Coll = Wƒ Colli,j и, таким образом, 
повторное применение границы объединения подразумевает, что


316
ЛЕММА A.16 Зафиксируем положительное целов N и допустим, что q 
≤√2N элементов y1, . . . , yq выбираются случайно равномерно и независимо, из 
множества, размера N . Тогда вероятность того, что существуют различ-
ные i, j при yi = yj составляет не менее 
ДОКАЗАТЕЛЬСТВО Напомним, что коллизия означает, что существуют 
различные i, j при yi = yj . Пусть Coll обозначает это событие. Пусть NoColli
будет событием, которое не является коллизией между y1, . . . , yi; то есть, yj
ƒ= yk для всех j < k ≤ i. Тогда NoCollq = tChoell является событием, когда 
никакой коллизии вообще нет.
Если NoCollq происходит, то NoColli также должно происходить для всех i 
≤ q. Таким образом,
Pr[NoCollq]=Pr[NoColl1]•Pr[NoColl2|NoColl1]• • •Pr[NoCollq| NoCollq−1].
Теперь, Pr[NoColl1] = 1, поскольку y1 не может иметь коллизии с собой. Кро-
ме того, если событие NoColli происходит, то {y1, . . . , yi} содержит i различные 
значения; таким образом, вероятность того, что yi+1 имеет коллизию с одним из 
этих значений равна i и, следовательно, вероятность того, что yi+1 не имеет кол-
лизии с каким-либо из этих значений, равна1 −i/N. Это означает i Pr[NoColli+1 | 
NoColli] = 1 − N , и, таким образом,
Поскольку i/N < 1 для всех i мы имеем 1 − i/N ≤ e−i/N (согласно неравенству 
A.3) и, таким образом,
Мы приходим к выводу, что
используя неравенство A.4 на последнем шаге (обратите внимание, что q(q − 
1)/2N < 1).


317
*Конечные поля
Мы используем конечные поля в книге только эпизодически, но включили их 
определение и некоторые основные факты для полноты картины. Более под-
робную информацию можно найти в любом учебнике по абстрактной алгебре.


Достарыңызбен бөлісу:
1   ...   227   228   229   230   231   232   233   234   ...   249




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

    Басты бет