Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Некоторые протоколы с нулевым разглашением допускают также возможность ошибки со стороны верификатора (Боба). Иначе говоря, в оценке вероятности полноты (18.2.2) е < 1. Такие протоколы называются протоколами с двусторонними ошибками (two-sided errors) и принадлежат подклассу Атлантик-Сити (т.е. "вероятно, высокочувствительные и, вероятно, точные", см. раздел 4.4.5). Рассмотрим один из таких протоколов.
18.5.1 Доказательство с нулевым разглашением для разложения на два простых множителя
Протоколы доказательства с нулевым разглашением оказываются очень полезными при обосновании того, что нечетное составное целое число N имеет только два простых множителя, т.е. N € ?,2_Рпгае и является корректным RSA-модулем.
Как сказано в разделе 4.7, язык Е2_рпте называется ансамблем (ensemble). Любой элемент этого языка представляет собой нечетное составное целое число, имеющее два разных простых множителя. Такой язык невозможно отличить от другого ансамбля, языка Ездите* состоящего из нечетных составных чисел, имеющих три простых множителя.
Предположим, что Алиса создает большое число N €. Е2 prime, зная его разложение на простые множители (т.е. просто перемножает два разных простых нечетных числа). С помощью идеального протокола с нулевым разглашением она может доказать Бобу, что N ? Е2 рпте- Это доказательство использует все три факта из теории чисел, приведенных ранее, и два новых. Факт 4. Если N € -E^prime. то ровно половина элементов из множества
Jjv(1) - {х | х g ZTN, (|) = l}
702
Часть VI. Криптографические протоколы
являются квадратичными вычетами, т.е. #QRN = #J/v(l)/2. Это объясняется тем, что только половина элементов этого множества имеет положительный символ Лежандра по обоим простым модулям. В то же время, чтобы символ Якоби остальных элементов был положительным, их символ Лежандра по обоим простым модулям должен быть отрицательным.
Факт 5. Если N $ Е2 Рпте и число TV не является ни простым, ни степенью простого числа, то не больше одной четверти элементов множества J/v(l) являются квадратичными вычетами, т.е. #QRN < #J/v(l)/4. Этот факт обобщает факт 4 на ситуации, когда число TV имеет три и больше простых множителя. Напомним, что для того, чтобы число х принадлежало множеству QR/v, необходимо, чтобы для каждого простого числа р | TV выполнялось условие a;(modp) €Е QRp. При формулировке факта 5 мы потребовали, чтобы число N не было степенью простого числа. В противном случае, когда TV = р\ где г — целое число, все элементы множества J/v(l) являются квадратичными вычетами. К счастью, степень простого числа легко разложить на множители (см. подсказки к упражнениям 8.7 и 8.8).
Протокол 18.4 позволяет Алисе провести доказательство с нулевым разглашением принадлежности числа множеству ?;2_Рпте-Исследуем стойкость протокола 18.4.
18.5.1.1 Стойкость
Во-первых, очевидно, что свойство идеального нулевого разглашения непосредственно наследуется от протокола 18.3. Итак, достаточно проанализировать полноту и непротиворечивость.
Полнота
Предположим, что Алиса честно сконструировала число N €Е -E^Prime- Однако после выполнения протокола Боб отказался принять ее доказательство. Он мотивирует это тем, что в случайном множестве Challenge оказалось меньше 3/8 квадратов (Алисе не повезло!). Это может произойти, только если е < 1.
В протоколах, рассмотренных ранее, верификатор не прощал никаких ошибок, даже если они происходили только один раз в ходе многократных раундов. Эти протоколы являются протоколами с односторонней ошибкой: если доказывающая сторона не жульничает, вероятность полноты равна е = 1, а значит, верификатор не должен прощать ни одной ошибки. Поскольку в протоколе 18.4 ? = \ (если Алиса не жульничает, см. факт 4), Боб может выбрать больше половины невычетов и должен прощать некоторое количество ошибок. Однако, если количество ошибок превышает определенную величину, Боб должен понять, что Алиса жульничает, и отвергнуть ее доказательство.
Глава 18. Протоколы с нулевым разглашением
703
Протокол 18.4. Протокол доказательства с нулевым разглашением того, что число N имеет два простых множителя ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:
составное целое число N. ЗАКРЫТАЯ ИНФОРМАЦИЯ АЛИСЫ:
разложение числа N. ЗАКЛЮЧЕНИЕ БОБА:
N Е ?<2_prime-
1. Боб удостоверяется, что N не является ни простым числом, ни степенью простого числа (например, применяя алгоритм Prime_Test и подсказку к упражнению 8.7).
2. Боб генерирует множество Challenge, состоящее из тп случайных чисел, принадлежащих множеству Jw(l), и отсылает его Алисе.
3. Обозначим через х\,х2,...,Хк все квадраты, принадлежащие множеству Challenge. Используя протокол 18.3, Алиса доказывает Бобу, что эти к элементов принадлежат множеству QR^.
4. Если к > L§mJ > Боб принимает доказательство, в противном случае он его отвергает.
(* Здесь условие к > [§тп] представляет собой "практический критерий выбора меньшинством голосов". Сравните его с "критерием выборов большинством голосов", в котором к > \тп. В рассматриваемом протоколе выбор большинством голосов применить просто невозможно, поскольку квадратичные вычеты числа N не образуют большинства в множестве Jn(1). Выбор критерия голосования обосновывается в разделе 18.5.1.2. *)
