Рейтинг:1

Являются ли они оба вероятностью столкновения в атаке дня рождения?

флаг in
Tim

О нападении на день рождения, книга Криптографическая инженерия говорит:

В общем случае, если элемент может принимать N различных значений, вы можете ожидать первого столкновения после выбора примерно $\sqrt{N}$ случайный элементы. Мы опускаем здесь точные детали, но $\sqrt{N}$ является довольно близко. Для парадокса дня рождения мы имеем N = 365 и $\sqrt{N} \примерно 19$. Количество людей, необходимое для получения возможности Двойной день рождения превышает 50% на самом деле 23, но $\sqrt{N}$ закрыто достаточно для наших целей, и это приближение, которое криптографы часто пользуюсь.

Один из способов взглянуть на это так: если вы выберете $к$ элементы, то Есть $к(к - 1)/2$ пары элементов, каждый из которых имеет $1/N$ шанс быть парой равных значений. Так что шанс найти столкновение близко к $к(к - 1)/2N$. Когда $k = \sqrt{N}$, этот шанс близка к 50%.

и википедия говорит:

В качестве примера рассмотрим сценарий, в котором учитель с классом из 30 учеников (n = 30) спрашивает дни рождения всех (для простоты игнорируя високосные годы), чтобы определить, совпадают ли дни рождения любых двух учеников (соответствует коллизии хэшей). как описано далее). Интуитивно этот шанс может показаться небольшим. Вопреки здравому смыслу, вероятность того, что хотя бы у одного учащегося день рождения совпадает с днем ​​рождения любого другого учащегося в любой день, составляет около 70% (для n = 30), по формуле $ {\ displaystyle 1 - {\ frac {365!} {(365-n)! \ cdot 365 ^ {n}}}} $.

которое можно перефразировать с точки зрения языка в Криптографическая инженерия:

$$1 - \frac{N!}{(N-k)! * Н^к}$$

Предполагается ли, что он равен следующему из Криптографическая инженерия:

$$ (к(к-1))/(2N) $$

Почему?

kelalaka avatar
флаг in
То есть о приближении, которое вы не заметили на странице Википедии. и возможные дубликаты [Каковы шансы коллизий для хеш-функции с 256-битным выходом?] (https://crypto.stackexchange.com/q/39641/18298) и [Вероятность столкновения в день рождения во Введении в современный Криптография](https://crypto.stackexchange.com/a/72791/18298) и [О нижней границе проблемы дня рождения](https://crypto.stackexchange.com/q/64584/18298) и [Что ошибка в этом приближении вероятности столкновения?] (https://crypto.stackexchange.com/q/66328/18298) и некоторые другие, не перечисленные...
kelalaka avatar
флаг in
Wiki-страница: [Проблема дня рождения - Приближения] (https://en.wikipedia.org/wiki/Birthday_problem#Approximations)
Tim avatar
флаг in
Tim
Спасибо. @келалака. Я не нахожу (k(kâ1))/(2N) в ссылках. Я скучаю по этому?
kelalaka avatar
флаг in
См. «Это нормально для низкого уровня» в ответе первой ссылки 101...
Tim avatar
флаг in
Tim
@kelalaka Спасибо. Книга в моем посте, похоже, объясняет (k(kâ1))/(2N) по-другому. Являются ли пары, каждая из которых имеет два одинаковых значения, непересекающимися событиями?
kelalaka avatar
флаг in
Сначала он выбирает равномерные случайные значения $k$, а затем формирует пару, где каждое имеет вероятность столкновения $1/N$....
fgrieu avatar
флаг ng
Вывод аппроксимации описан в моей [_День рождения задачи криптографического хеширования, 101_](https://crypto.stackexchange.com/a/39644/555). Остерегайтесь использования $(k,n)$ там, где в настоящем вопросе используется $(N,k)$.
Tim avatar
флаг in
Tim
@fgrieu Спасибо. У меня все тот же вопрос. Книга в моем посте, кажется, объясняет (k(kâ1))/(2N) иначе, чем ваш ответ. Как это понять из 1/N для каждой пары? Являются ли пары, каждая из которых имеет два одинаковых значения, непересекающимися событиями? Какая часть в его выводе является приближением?
Рейтинг:2
флаг ng

Вопрос спрашивает, как мы идем от $\displaystyle p=1 - \frac{N!}{(Nk)!\,N^k}$ для вероятности столкновения $к$ равномерно случайные значения среди $N$, в приближении $\displaystyle p\приблизительно\frac{k(k-1)}{2N}$ (что предполагает $к$ мал по сравнению с $\квт N$ ).

Сначала мы возвращаемся к $\displaystyle1-p=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, вот как $р$ было определено в первую очередь. Затем мы логарифмируем обе стороны и используем это $u>0,v>0\имплицитно\ln(u\,v)=\ln(u)+\ln(v)$ получить $$\displaystyle\ln(1-p)=\sum_{j=0}^{k-1}{\ln\left(1-\frac j N\right)}$$

Для маленьких $|х|$, он держит $\ln(1+x)\приблизительно x$. Применив это к $х=р$ с левой стороны и $\displaystyle x=\frac j N$ с правой стороны получаем $ \ Displaystyle p \ приблизительно \ sum_ {j = 0} ^ {k-1} \ frac j N $. Мы перепишем это как $\displaystyle p\приблизительно\frac 1 N\sum_{j=0}^{k-1}j$.

Теперь мы используем, что сумма неотрицательных целых чисел меньше, чем $к$ является $\displaystyle\frac{k\,(k-1)}2$ и получить желаемое $\displaystyle p\приблизительно\frac{k(k-1)}{2N}$.

Без доказательства: это приближение $р$ всегда в избытке. Это меньше, чем $+28\%$ когда $k\le\sqrt N$, меньше, чем $+14\%$ когда $k\le\sqrt{2N}$, меньше, чем $+7\%$ когда $k\le2\sqrt N$.


Большая часть ошибки связана с аппроксимацией $\ln(1-p)\приблизительно-p$. Гораздо лучшее приближение: $$p\приблизительно1-e^{-\frac{k(k-1)}{2N}}$$ который предполагает только $k\ll N$ скорее, чем $k\ll\sqrt N$. Однако имейте в виду, что эта альтернативная формула численно нестабильна для малых $р$.


В комментарии дополнительно спрашивается

Как мне понять (эту формулу) из $1/N$ для каждой пары? Являются ли пары, каждая из которых имеет два одинаковых значения, непересекающимися событиями? Какая часть в его выводе является приближением?

Один простой способ получить вероятность $р$ что происходит столкновение между $к$ единые ценности среди $N$ (за $0\le k\le N$) является дополнением вероятности отсутствия столкновения.

Для фиксированного $N$, определять $q_k$ как вероятность того, что столкновения не будет после $к$ ценности. Очевидно $q_0=q_1=1$. И для $k\ge2$, $q_k$ есть вероятность того, что не было столкновения среди первых $к-1$ ценности (то есть $q_{k-1}$), время вероятность того, что нет столкновения между $к-1$ предыдущие значения и последнее нарисованное, которое $\displaystyle\frac{Nk}N$ (оправдание есть точно $N-k$ ценности среди $N$ которые не приводят к столкновению для последнего нарисованного значения).

Следует $\displaystyle q_k=q_{k-1}\left(1-\frac k N\right)$, таким образом $\displaystyle q_k=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, таким образом $$p=1-\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}=1-\frac{N!}{(Nk)!\,N ^к}$$

Это точно. См. Первые два раздела этого ответа для получения приближений.


Один источник оправдал приближение следующим образом:

Один из способов взглянуть на это так: если вы выберете $к$ элементы, то есть $k(kâ1)/2$ пары элементов, каждый из которых имеет $1/N$ шанс быть парой равных значений.

Этот махающий рукой аргумент не дает математически точного вывода $\displaystyle p=\frac{k(k-1)}{2N}$, так как события не пересекаются. Так долго как $р$ мала, нам это может сойти с рук, но это становится совершенно неправильным, когда $k>\sqrt{2N}$.

Когда $k = \sqrt{N}$, этот шанс близок к 50%.

Это верно, если 39,3% близко к 50%.

Tim avatar
флаг in
Tim
Спасибо. В моем комментарии на https://crypto.stackexchange.com/questions/99160/are-these-both-the-probability-of-collision-in-birthday-attack/99176#comment214408_99160 заданы разные вопросы
Tim avatar
флаг in
Tim
Если вы посмотрите на первую цитату в моем посте, книга не вычисляет вероятность того, как вы добавили ее к своему ответу.
Tim avatar
флаг in
Tim
«поскольку события не являются независимыми». Аддитивность вероятностей нескольких событий зависит от того, что события не пересекаются, а не являются независимыми.
kelalaka avatar
флаг in
Проценты нужны ссылки...
fgrieu avatar
флаг ng
@kelalaka: мое свидетельство +28% только числовое (отсюда и _без доказательства_): я начертил $\frac{\left(1-\frac{{k^2}!}{(k^2-k)!\ ,k^{2k}}\right)\,2k^2}{k(k-1)}-1$; то же самое для +14% +7%.
Tim avatar
флаг in
Tim
Спасибо. (1) Оправдывает ли ваш «Сначала мы вернемся к... получению желаемого p∙k(k∙1)/2N” (k(k∙1))/(2N) как разумное приближение? (2) «Этот аргумент маханием руками не дает математически точного вывода p = k (k 1) / 2N, поскольку события не являются непересекающимися. Пока p мало, мы можем обойтись без него. , но это становится совершенно неверным, когда k>sqrt(2N). Когда k=sqrt(N), этот шанс близок к 50%. /2N - плохое приближение? (3) если вы не имеете в виду противоречие в (1) (2), не могли бы вы объяснить, отредактировать или перефразировать, что вы на самом деле имеете в виду?
fgrieu avatar
флаг ng
(1) Точнее, это означает, что $k(kâ1)/(2N)$ является допустимым приближением _для $k$ или $p$ ниже некоторого порога._ (2) Это означает, что $k(kâ 1)/(2N)$ плохо обосновывается приведенным аргументом, не указывается, когда оно применимо, и является ужасным приближением для $k$ выше некоторого порога. Как объяснено, он уже значительно отличается (на +24%) применительно к $k=\sqrt N$ и $N$, представляющим криптографический интерес. (3) Противоречия нет.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.