Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ПРЕДПОЛОЖЕНИЕ A.14 (граница Чернова)
- Проблема «парадокса дней рождения»
| ПРЕДПОЛОЖЕНИЕ A.13 Зафиксируем ε > 0 и b ∈ {0, 1}, и пусть {Xi} будут
попарно независимыми, 0/1-случайными величинами, для которых Pr[Xi = b] ≥ 1 + ε для всех i. Рассмотрим процесс, в котором m значений X1, . . . , Xm записывают и X задают значение, которое появляется точно в большую часть времени. Тогда ДОКАЗАТЕЛЬСТВО Допустим b = 1; в случае симметрии, это не ведет к потере общности. Тогда Exp[Xi] = 1/2+ ε. Пусть X обозначает точное боль- шинство {Xi} как в предположении, и отметим, что X ƒ= 1 если и только если Таким образом, Поскольку Var[Xi] ≤ 1/4 для всех i, применяя предыдущий вывод, покажем, что как и утверждалось. Более точная граница получается, если {Xi} независимы: 315 ПРЕДПОЛОЖЕНИЕ A.14 (граница Чернова) Зафиксируем ε>0 и b∈{0, 1}, и пусть {Xi} будут независимыми 0/1-случайными величинами Pr[Xi = b] = 1/2 + ε для всех i. Веро- ятность того, что значение большинства из них b составляет не более e−ε m/2. Проблема «парадокса дней рождения» Если выбрать q элементов y1, . . . , yq равномерно из множества размера N , то какова вероятность того, что существуют различные i, j при yi = yj ? Мы на- зываем указанное событие коллизией и обозначаем вероятность этого события как coll(q, N ). Эта проблема относится к, так называемому, парадоксу дней рождения, когда задают вопрос о том, какого размера группа людей нужна, что- бы с вероятностью 1/2 у некой пары людей в группе совпадал день рождения. Чтобы увидеть это отношение, пусть yi обозначает день рождения i-го человека в группе. Если в группе есть q человек, то мы имеем q значений y1, . . . , yq вы- бранных равномерно из {1, . . . , 365}, делая упрощающее предположение, что дни рождения равномерно и независимо распределены среди 365 дней не висо- косного года. Кроме того, совпадающие дни рождения соответствуют коллизии, т.е., отличию i, j при yi = yj. Таким образом, нужное решение для пробле- мы дней рождения задается минимальным (целым) значением q, для которого coll(q, 365) ≥ 1/2. (Ответ может удивить—достаточно q = 23 человек!) В этом разделе мы докажем нижние и верхние границы coll(q, N ). Взятые вместе и обобщенные на высоком уровне, они показывают, что если q <√N, то вероятность коллизии составляет Θ(q2/N ); иначе, для q = Θ(√N) вероятность коллизии является константой. Верхнюю границу для вероятности коллизии легко получить. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|