Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Следовательно, данные, посланные Алисой в ходе выполнения протокола 18.1, являются равномерно распределенными и не предоставляют Бобу никакой дополнительной информации о ее закрытых данных. Значит, протокол 18.1 является идеальным протоколом с нулевым разглашением. ?
Из этого примера следует, что элементы стенограммы Алисы являются равномерно распределенными независимо от того, как Боб выбирает случайные биты оклика. Иначе говоря, Боб не может повлиять на распределение чисел в стенограмме Алисы. Следовательно, протокол 18.1 является идеальным протоколом с нулевым разглашением, даже если Боб ведет нечестную игру.
В идеальном протоколе с нулевым разглашением для получения стенограммы доказательства необязательно запускать сам протокол. Эту стенограмму, представляющую собой обычную строку, можно создать с помощью жеребьевки, выполняемой в течение времени, полиномиально зависящего от длины стенограммы. Это важное свойство идеальных ZK-протоколов описывается определением 18.2.
Определение 18.2. IP-протокол для языка L называется идеальным протоколом с нулевым разглашением, если для любого предложения xEL стенограмму доказательства (Р, V)(x) можно создать с помощью алгоритма ?Q(x), время работы которого полиномиально зависит от длины предложения х, с одним и тем же распределением вероятностей.
Как правило, эффективный алгоритм ?Q называется имитатором (simulator) ZK-протокола. Однако, если (Р, V) — идеальный протокол с нулевым разглашением, алгоритм ?Q называется не имитатором, а уравнителем (equator).
18.3.1.1 Протокол идентификации Шнорра
В протоколе 18.1 Боб использует биты оклика. Это приводит к большой вероятности противоречивости протокола: 6 = 1/2. Следовательно, для того, чтобы уменьшить ошибку до 2~~т, необходимо повторить протокол т раз. Обычно для
686
Часть VI. Криптографические протоколы
предотвращения жульничества со стороны Алисы достаточно положить т = 100. Необходимость большого количества раундов снижает эффективность протокола.
При некоторых параметрах безопасности вероятность противоречивости протокола можно снизить, что приведет к уменьшению количества необходимых раундов. Для этого Боб должен знать разложение числа п на простые множители. Обоснование этого условия будет приведено в разделе 18.6.1. Особая ситуация возникает, когда число п является простым. Рассмотрим протокол идентификации Шнорра (Schnorr's Identification Protocol), предложенный в работе [256] для идентификации смарт-карт.
Протокол идентификации Шнорра является разновидностью протокола 18.1, в котором функция f(x) реализуется с помощью операции g~x(modp) над конечным полем Fp, где подгруппа {д) имеет простой порядок q \ р — 1. Легко видеть, что функция g~f(modp) является гомоморфной. Более того, вследствие предположения 8.2 из раздела 8.4 для достаточно больших простых чисел р a q, например, \р\ = 1024, \q\ — 160, функция g~x(modp) является однонаправленной.
При таком выборе параметров Боб может использовать слегка увеличенные] оклики, состоящие из log2 log2 р бит.
Примечание 18.2. Поскольку условие q \ р — 1 налагается явно, протокол идентификации Шнорра больше не должен решать задачу о принадлежности элемента определенной подгруппе. Теперь Боб может самостоятельно определить, принадлежит ли элемент у подгруппе (д), не прибегая к помощи Алисы: yq = gq = = l(modp). Следовательно, протокол идентификации Шнорра предназначен для решения более конкретной задачи: знает ли Алиса дискретный логарифм числа у по основанию д, представляющий ее криптографический мандат. ?
18.3.1.2 Стойкость протокола идентификации Шнорра Полнота
Это свойство выполняется тривиальным образом, причем е = 1. Доказательство этого факта читатели могут провести самостоятельно (упражнение 18.7).
Непротиворечивость
Предположим, что Алиса жульничает, т.е. не знает правильное значение диЫ кретного логарифма. Получив число Commit от Алисы, Боб генерирует число Challenge € rj{0, l}lo&2i°s2p и ожидает отзыва.
Это уравнение демонстрирует, что при заданных числах Commit и у существу-^ ют log2p разных значений Response, соответствующих log2p разным значениям Challenge. При небольшой величине log2p наилучшей стратегией вычисления
Response = logfl Commit - yChalleri9e
(modp) (modq)
Протокол 18.2. Протокол идентификации Шнорра
ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:
р, q: два простых числа, удовлетворяющих условию q | р — 1. (* Типичный размер: |р| = 1024, \q\ = 160. *) д : ordpfo) = 9; У • у = g~a(modp).
(* Кортеж (р, 9, <7, у) состоит из параметров открытого ключа Алисы,
сертифицированного органом авторизации. *) ЗАКРЫТЫЕ ВХОДНЫЕ ДАННЫЕ АЛИСЫ:
а < q. ЗАКЛЮЧЕНИЕ БОБА:
Алисе известен некоторый элемент а € Zq, удовлетворяющий условию
У = g~a(modp).
Следующие шаги выполняются log2 log2 р раз.
1. Алиса генерирует число к 6 иЪп, находит число Commit <— gk{xaadp) и посылает его Бобу.
2. Боб генерирует число Challenge € ц{0,1}1о?21об2Р и посылает его Алисе.
3. Алиса вычисляет значение Response <— к + а ¦ Challenge(modp) и посылает его Бобу.
4. Боб проверяет число Commit = gResPonseyChallen3e(modp).
