Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Несколько исследователей, например, Грааф (Graaf) и Перальта (Peralta) [291], Камениш (Camenisch) и Мичелс (Michels) [63], а также Женнаро (Gennaro), Мич-чианикио (Miccianicio) и Рабин (Rabin) [120] предложили более эффективные ZK-протоколы с односторонней ошибкой (е = 1) для доказательства того, что число N имеет два простых множителя.
Протокол, описанный нами выше, основан на идеях, изложенных Бергером (Berger), Каштаном (Kannan) и Перальта [32]. Его выбор объясняется двумя причинами. Во-первых, он является наиболее простым. Во-вторых, он имеет двусторонние ошибки, редко встречающиеся у протоколов с нулевым разглашением. Это позволило нам использовать его для демонстрации основных идей.
18.6 Эффективность раунда
Рассмотрим второй вопрос, сформулированный в разделе 18.1: сколько раундов необходимо для того, чтобы доказывающая сторона убедила в своей правоте проверяющую сторону? Это вопрос о так называемой эффективности раунда (round efficiency). Раундом называется полный цикл действий, связанных с отправкой и получением сообщений. Поскольку многие ZK- (и IP-) протоколы состоят из вычислений величин Commit (первый шаг участника Р), Challenge (шаг участника F), Response (второй шаг участника Р), мы будем часто называть раундом именно эти три действия.
Для того чтобы снизить вероятность ошибки в протоколах с нулевым разглашением, обычно используется большое количество раундов. В выражении (18.2.2) величина е представляет собой нижнюю оценку вероятности полноты, а величина 1 — е — ее оценку сверху. Как и оценку непротиворечивости, оценку полноты сверху необходимо минимизировать. Для того чтобы объективно оценивать эффективность раундов в протоколе с нулевым разглашением, необходимо оценивать вероятности ошибок в каждом отдельном раунде. Чем ниже оценка такой вероятности, тем выше эффективность сеанса.
В зависимости от вероятности ошибки в ходе отдельного раунда протоколы разделяются на три категории.
Логарифмические протоколы (logarithmic-round protocol). Эффективность отдельного раунда во всех протоколах с нулевым разглашением, рассмотренных нами ранее, за исключением протокола 18.4, была постоянной величиной, например, 1/2 или log2 log2 п (если в качестве параметра безопасности используется log2n, как в протоколе 18.1 или протоколе идентификации Шнорра, величина log log п считается постоянной). Для того чтобы сделать вероятность ошибки пренебрежимо малой, т.е. ограничить ее величи-
Глава 18. Протоколы с нулевым разглашением
707
ной l/(logn)c для всех констант с, протокол с постоянной вероятностью ошибки необходимо выполнить log п раз. По этой причине такие протоколы называются логарифмическими.
Полиномиальные протоколы. Эффективность раунда в логарифмическом протоколе фактически представляет собой линейный полином, зависящий от параметра безопасности. В некоторых протоколах с нулевым разглашением эффективность раунда оценивается полиномами более высокой степени. Протокол с нулевым разглашением для любого NP-языка, использующий полиномиальную редукцию к NP-полной задаче (см. раздел 18.2.3), называется полиномиальным.
Например, протокол 18.4 является полиномиальным. Во-первых, в нем используется повышенное количество раундов, поскольку он имеет двусторонние ошибки, а во-вторых, в ходе каждого раунда протокол 18.4 вызывает другой логарифмический протокол (протокол 18.3).
Константные (однораундовые) протоколы . Если протокол с нулевым разглашением может снизить вероятность ошибки до пренебрежимо малой величины за небольшое количество раундов (или даже за один раунд), отпадает необходимость повторять логарифмическое количество раундов. Благодаря этому свойству такие протоколы называются константными (однораун-довыми).
Повышению эффективности раундов в протоколах с нулевым разглашением посвящено много работ. В этой области получено много результатов. Рассмотрим два результата, касающихся решения задачи о принадлежности элемента подгруппе и вычисления дискретного логарифма.
• В разделе 18.6.1 получена нижняя оценка эффективности раунда в протоколе аргументации с нулевым разглашением для подгрупп "L*N, где iV — нечетное составное целое число. Этот результат носит негативный характер. Из него следует, что для снижения вероятности ошибки необходимо выполнить логарифмическое количество операций, т.е. константного протокола для доказательства принадлежности элемента подгруппе не сушествует.
• В разделе 18.6.2 изучен константный ZK-протокол доказательства равенства дискретного логарифма для элементов из конечного поля ?р. Этот результат является положительным. Он свидетельствует о значительной эффективности протокола идентификации Шнорра (протокол 18.2).
708
Часть VI. Криптографические протоколы
18.6.1 Нижняя оценка эффективности раунда при решении задачи о принадлежности элемента подгруппе
Рассмотрим снова задачу о доказательстве (аргументации) принадлежности элемента подгруппе, поставленную перед протоколом 18.1. Теперь будем считать, что функция /(ж) реализуется так, как показано в разделе 18.3.3.1, т.е.
