Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
713
Из этой спецификации следует, что протокол содержит четыре обмена сообщениями и выполняется только один раз. Ниже будет показано, что вероятность его непротиворечивости равна 5 = l/q. Таким образом, протокол ZK Dis-Log-EQ доказательства Чаума весьма эффективен.
18.6.2.1 Стойкость протокола ZK Dis-Log-EQ доказательства Чаума Полнота
Из описания протокола непосредственно следует, что вероятность его полноты равна е = 1. Иначе говоря, если Алиса обладает элементом z и следует инструкциям протокола, Боб всегда принимает ее доказательство.
Непротиворечивость
Покажем, что протокол ZK Dis-Log-EQ действительно является протоколом доказательства, т.е. Алиса может обладать неограниченной вычислительной мощью. Для этого мы не будем налагать на объем ее вычислительных ресурсов никаких ограничений.
Предположим, что Алиса жульничает. Тогда ее общие входные данные (р, q, д, h, X, Y) удовлетворяют следующим условиям.
X = gz(modp) и Y = hz (modp) при некотором z ф z'(modg). (18.6.1)
Для того чтобы Боб принял доказательство Алисы, выполняя верификацию на ге 5, А условию
шаге 5, Алиса должна послать ему на шаге 2 число Commit^, удовлетворяющее
Commit^ = XcXaYb{modp). (18.6.2)
Другими словами, получив от Боба числа а и 6, Алиса должна раскрыть число с G Z9, удовлетворяющее условию (18.6.2). Поскольку значения а и Ь зафиксированы Бобом на этапе 1, а числа Commit^ и Commit^ зафиксированы на этапе 2, формула (18.6.2) означает, что число ceZg также фиксируется на этапе 2. Иначе говоря, Алиса не может изменить значение с после того, как она послала на этапе 2 свои передачи.
При фиксированном числе с € Ъя получаем:
Commit^ , ,
С^1оёЭ gahb (m0d<Z)- О8"6"3)
С учетом формулы (18.6.2) отсюда следует, что
Commit^
cloggX = logg °^!ybA (niodg). (18.6.4)
714
Часть VI. Криптографические протоколы
Поскольку h 6 (д) (равенство oidp(h) = q позволяет Бобу подтвердить это, проверив условия h ф 1 и hq — l(modp)), h = gd(modp) при некотором d € Ъя, d ф 0(mod<7). Следовательно, формулу (18.6.3) можно переписать так.
с — logs Commit^ = —а — bd(mod q). (18.6.5)
Аналогично, используя формулу (18.6.1), можно переписать формулу (18.6.4) в следующем виде.
clogs X — logs Commit^ = — az — bdz'(modq). (18.6.6)
Для z ф z,(raodq) формулы (18.6.5) и (18.6.6) образуют следующую систему линейных уравнений.
(
с-log, Commit V \ = -d \ АЛ
с logff X - \oEh Commit?7 \-z -dz'J \bj
Матрица этой системы имеет полный ранг (rank = 2). Отсюда следует, что существует единственная пара чисел (a, b) G Z9 х Z9. Эта пара удовлетворяет условиям, при которых вычисляется значение Commit^ на этапе 1, и выполняется верификация на этапе 5.
Однако на этапе 2, фиксируя число с G 7Lq, Алиса получает только одно из уравнений (18.6.5), которое позволяет ей вычислить ровно q разных пар (а, Ь). Все они удовлетворяют системе (18.6.5), но только одна из них удовлетворяет условию (18.6.6), проверяемому на этапе 5. Таким образом, обладая неограниченными вычислительными ресурсами, Алиса может угадать правильную пару (а, Ь) с вероятностью 1 fq.
Итак, мы не только доказали, что вероятность противоречивости однораун-дового протокола Чаума равна l/q, но и показали, что он является протоколом доказательства (а не аргументации) равенства дискретного логарифма.
Идеальное нулевое разглашение
Протокол Чаума является идеальным протоколом доказательства с нулевым разглашением. Построим алгоритм уравнивания ("eguator") ? Q, позволяющий создать стенограмму, распределение которой идентично распределению подлинной стенограммы. Для общего входа (p,q,g,h,X,Y) алгоритм ?Q выполняет следующие шаги.
1. Алгоритм ?Q генерирует числа а, ЬЕ иЪч и вычисляет значение Commita «— gahb(modp).
2. Алгоритм ?Q генерирует число с €Е \j7Lq и вычисляет значения Commit^ = CommitBffc(modp),
Commit^ = XcX°Yb(modp).
Глава 18. Протоколы с нулевым разглашением
715
3. Алгоритм ?Q выдает результат Transcript = Commits, Commit^ , Commit^, a, b, c.
Очевидно, что полученная строка Transcript имеет распределение, идентичное распределению подлинной стенограммы.
Существует и другой, более убедительный способ доказательства идеального нулевого разглашения в протоколе Чаума. Во-первых, если Боб придерживается нечестной стратегии, создавая оклик, т.е. число Commits сконструировано неверно, он не получит никакого ответа. Во-вторых, если Боб правильно создает оклик, используя пару чисел (а, о) е Zg х Zg, значит, ему уже с первого этапа известно число XaYb(modp), "раскрываемое" Алисой. В обеих ситуациях Боб не получает никакой новой информации о закрытом числе Алисы!
18.6.2.2 Выводы
• Протокол ZK Dis-Log EQ можно использовать для идентификации. В этом случае пара (д, X) может считаться компонентом открытого ключа пользователя, сертифицированного соответствующим органом (см. раздел 13.2).
• Для вычисления значений gahb(modp) и XcXaYb(modp) можно применять алгоритм 15.2, эффективность которого сравнима с однократным возведением в степень по модулю. Таким образом, Алиса и Боб должны будут выполнить примерно по три возведения в степень. В этом случае, если Алиса жульничает, вероятность принятия доказательства пренебрежимо мала. Для сравнения, чтобы достичь столь же малой вероятности ошибки в протоколе идентификации Шнорра, Алиса и Боб должны выполнить log2 р « 10 (если ри 21024) операций возведения в степень.
