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



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

ПРЕДПОЛОЖЕНИЕ 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) вероятность 
коллизии является константой.
Верхнюю границу для вероятности коллизии легко получить.


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




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

    Басты бет