Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ДОКАЗАТЕЛЬСТВО
- *Конечные поля
| ЛЕММА 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 *Конечные поля Мы используем конечные поля в книге только эпизодически, но включили их определение и некоторые основные факты для полноты картины. Более под- робную информацию можно найти в любом учебнике по абстрактной алгебре. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|