Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
^Response ^ gkgz(2u+l) =. ^^ду^+1) _ Commjt. у Challenge^ N)
Следовательно, Боб снова должен принять доказательство.
Таким образом, независимо от длины оклика, как и в протоколе 18.5, вероят-1 ность противоречивости равна всего лишь 6 = 1/2. По этой причине мы назвали этот протокол "непригодным". о
Поскольку Бобу неизвестна факторизация числа N, он не может самостоятель-| но решить задачу о принадлежности элемента подгруппе (см. замечание 18.1М Итак, в примере 18.4 Боб может предотвратить жульничество Алисы только с вероятностью 1/2. Увеличение длины оклика ничего не дает!
Задача, описанная в примере 18.4, не возникала в вычислительном ZK-прото-коле, приведенном в разделе 18.3.3.2, в котором функция f(x) реализовываласи аналогично: f(x) = ei^mod N), где N — нечетное составное целое число. Напома ним, что в этом протоколе используются битовые оклики, а значит, вероятности его противоречивости равна 6=1/2. Протокол идентификации Шнорра также не страдает этим недостатком, поскольку группа (д) в этом протоколе имеет простое
Глава 18. Протоколы с нулевым разглашением
711
порядок q и не содержит ни одного элемента, порядок которого был бы меньше q, за исключением единицы.
Используя нетривиальный квадратный корень единицы по модулю iV, Алиса достигает максимальной вероятности угадывания, равной 5 = 1/2. В тривиальном случае ? = — 1 (другой тривиальный случай, ? = 1, в атаке не используется) Боб может достичь большей убедительности: либо У, либо —Y принадлежит подгруппе (д). Однако, поскольку Алиса знает факторизацию числа N, а Боб — нет, используя китайскую теорему об остатках, она также может скрыть число дк, используя другой множитель малого порядка, например, третьего. (С помощью теоремы 6.7 из раздела 6.2.3 Алиса может вычислять элементы любого порядка d | <fr(N).) Таким образом, вероятность противоречивости не может быть пренебрежимо малой величиной. Протокол 18.1 остается всего лишь демонстрационной версией решения задачи о принадлежности элемента подгруппе при обычном выборе параметров безопасности, в который входят подгруппы Z*N.
Итак, доказательство принадлежности подгруппе с нулевым разглашением состоит из логарифмического количества раундов.
В приложениях ZK-протоколов, описанных в следующей главе, мы рассмотрим доказательство принадлежности элемента группе Щ^. Однако сократить затраты, связанные с выполнением логарифмических протоколов, нам не удастся, поскольку для этого необходимо особым образом выбирать число N.
18.6.2 Доказательство знания дискретного логарифма с постоянным количеством раундов
Протокол идентификации Шнорра (протокол 18.2) позволяет аргументировать с нулевым разглашением знание дискретного логарифма элемента из конечного поля ?р. Выше было продемонстрировано, что этот протокол является логарифмическим.
Теперь покажем, что с помощью протокола идентификации Шнорра можно провести аналогичное доказательство с постоянным количеством раундов. Эта модификация называется протоколом Чаума (Chaum) [72]. Ее полное название — протокол ZK Dis-Log-EQ доказательства Чаума (Chaum's ZK Dis-Log-EQ Proof Protocol). Этот протокол позволяет провести доказательство с нулевым разглашением того, что два элемента имеют одно и то же значение дискретного логарифма.
Рассмотрим протокол ZK Dis-Log-EQ доказательства Чаума с параметрами безопасности, выбранными в протоколе идентификации Шнорра. Иначе говоря, пусть элемент д € Fp, где р — нечетное простое число, и ordp(g) = q, где q — также нечетное простое число (следовательно, q \ р — 1). Введем обозначение G = (д).
В протоколе ZK Dis-Log-EQ доказательства Чаума используется дополнительный элемент h € (д), где h ф д и h ф 1.
712
Часть VI. Криптографические протоколы
Протокол 18.6. Протокол ZK Dis-Log-EQ доказательства Чаума
ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:
р, q: два простых числа, удовлетворяющих условию q \ р — 1. (* Как правило, |р| = 1024, \q\ = 160. *) д, h : ordpfo) = ordp(/i) = q,g^h.
(* Боб проверяет условия: д ф 1, h ф 1, д ф h, дя = h4 ~ l(modp). *) X,Y : X = g2(modp),X = fi*(modp). ЗАКРЫТАЯ ИНФОРМАЦИЯ АЛИСЫ:
zezq.
ЗАКЛЮЧЕНИЕ БОБА:
Алиса знает некий элемент z €Е Z9, такой что
X = gz(modp) и Y = hz(modp), т.е. Iogs X = \ogh X(modg).
1. Боб генерирует число а, Ь G r/Z9, вычисляет значение Commitв *i gahb(modN) и отсылает его Бобу.
(* Число Commitв является окликом Боба. *)
2. Алиса генерирует число с G i/Z9, вычисляет значения
и посылает их Бобу.
3. Боб сообщает Алисе числа а и Ь.
(* Боб раскрывает содержание передачи, чтобы продемонстрировать npa-J вилыюсть своего оклика. *)
4. Алиса проверяет условие Commite = gahb(modp).
(* Если условие выполняется, она раскрывает Бобу число с, если нет — прекращает выполнение протокола. Если оклик Боба сконструирован пра* вильно, значит, он заранее знал число X°Y*(modp), предназначенное для Алисы. *)
5. Боб проверяет условия
Если оба равенства выполняются, доказательство принимается, в противном случае оно отклоняется.
Commit^' = CommitBffc(modp), Commit^ = XcX°yb(modp).
Глава 18. Протоколы с нулевым разглашением
