Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Если Алиса не жульничала, и все же ее доказательство было отвергнуто, будем говорить, что произошло событие BadLuckAlice. Оценим его вероятность, учитывая критерий принятия решений, которым руководствуется Боб. Если к > I §тп|, т.е. количество квадратичных вычетов в множестве окликов превышает |, Боб принимает доказательство, в противном случае он его отвергает. Выбор такого критерия голосования обосновывается в разделе 18.5.1.2.
Оценим вероятность полноты е{тп) после тп раундов, выразив ее через вероятность события BadLuckAlice.
Prob[BadLuckAlice] =
= Prob [Боб отклонит доказательство | N е -Е,2_Рпте] < < 1 - е(тп).
704
Часть VI. Криптографические протоколы
Если т = ^Challenge < #J/v(l), событие BadLuckAlice представляет собой сумму т испытаний Бернулли (см. раздел 3.5.2), состоящих из к успехов и т — к испытаний, где к < LlmJ ¦ Поскольку Алиса сконструировала число N €Е -Е^Рпте, вероятность успеха и неудачи в множестве Challenge, состоящем из случайных элементов множества Jyv(l), равна 1/2. Оценивая "левый хвост" биномиального распределения (раздел 3.5.2) и учитывая все возможные варианты числа к, получаем
1 - e(m) = Prob[Badl_uckAlice] =
Эта величина представляет собой площадь, ограниченную "левым хвостом" биномиального распределения, поскольку число |т лежит слева от средней точки, равной |т.
Для того чтобы сделать вероятность события BadLuckAlice пренебрежимо малой, следует выбрать число т = 2000 (обоснование приведено в разделе 18.5.1.2). Тогда площадь фигуры, ограниченной "левым хвостом" биномиального распределения, равна следующей величине.
1 - е(2 ООО) « 1,688 - НП29.
Следовательно, е(2 ООО) — огромная вероятность. Итак, если Алиса не жульничает, Боб принимает ее доказательство с огромной вероятностью.
По закону больших чисел (раздел 3.5.3) чем больше окликов сгенерирует Боб, тем выше вероятность полноты протокола. Кстати, если Боб сгенерирует # Jyv(l) окликов (что практически невозможно), вероятность полноты станет равной единице, т.е. он никогда не сделает ошибки (событие BadLuckAlice никогда не произойдет).
Непротиворечивость
Для того чтобы оценить вероятность ошибки с другой стороны, предположим, что Алиса нечестно сконструировала число N $ -Бгрпте» имеющее больше двух простых множителей. Не исключена возможность, что Боб примет "доказательство" Алисы, поскольку он может просто сгенерировать больше | случайных окликов, являющихся квадратичными вычетами (Бобу не повезло!)
Обозначим через BadLuckBob условное событие, состоящее в том, что N ? ?;2_Prime> и. тем не менее, Боб принимает "доказательство". Для случайно
Глава 18. Протоколы с нулевым разглашением
705
выбранного множества Challenge из факта 5 следует, что теперь вероятность успеха в серии испытаний Бернулли не превышает 5 = ^, а вероятность неудачи не меньше 1 — 6 = |. Применяя формулу биномиального распределения и суммируя все варианты к > [f^nj, в которых Боб принимает "доказательство", получаем следующую оценку площади фигуры, ограниченной "правым хвостом".
fc=Lfmj
Для тп = 2 ООО получаем
5(2000) « 1,847 - Ю-35.
Таким образом, со стороны Алисы было бы чрезвычайно наивным жульничать и надеяться, что ее не поймают за руку!
Итак, мы закончили исследование нулевого разглашения, полноты и непротиворечивости протокола 18.4.
18.5.1.2 Обоснование "критерия голосования"
Если Алиса не жульничает, а вероятность полноты в одном раунде равна е = \, то ровно половина элементов множества J^{1) является квадратичными вычетами. Для повышения вероятности полноты протокола 18.4 невозможно применить "критерий голосования большинством", описанный в разделе 4.4.1.1. В качестве критического значения выбрано число |, поскольку оно лежит посередине между величиной е = \ (Алиса не жульничает) и 6 — | (Алиса жульничает). Этот выбор делает оба события, BadLuckAlice и BadLuckBob, приблизительно равновероятными (точнее, одинаково невероятными).
Этот критерий называется "голосование меньшинством". По закону больших чисел (раздел 3.5.3), поскольку 5 < е, в качестве критического значения можно выбрать их среднее и многократно повторять раунды (тп раз), уменьшая вероятность 5(тп) и увеличивая вероятность е(ттг). Это позволит распознавать жульничество с высокой степенью точности.
Для того чтобы вероятности обеих неудач были пренебрежимо малы (например, не превышали 2-100), необходимо выполнить 2 ООО повторений. Если выбрать меньшее количество повторений, вероятности ошибок могут резко возрасти. Например, при тп = 100 (которое обычно считается "достаточным" количеством повторений) вероятность полноты равна е(100) « 0,993 (т.е. событие BadLuckAlice происходит с вероятностью 1 — е(100) « 0,007), а вероятность противоречивости равна 5(100) « 0,0052 (т.е. событие BadLuckBob происходит с вероятностью 0,0052). Эти оценки далеки от желаемых, поскольку вероятности неудач слишком высоки (ошибки будут возникать слишком часто).
5{m) = Prob[BadLuckBob] = (
706
Часть VI. Криптографические протоколы
Как правило, если величины е и <5 близки, протоколы с двусторонними ошибками становятся неэффективными.
