Упрощенная схема идентификации с нулевой передачей знаний
Схему идентификации с нулевой передачей знаний предложили в 1986 г. У.Фейге, А.Фиат и А.Шамир. Она является наиболее известным доказательством идентичности с нулевой передачей конфиденциальной информации.
Рассмотрим упрощенный вариант схемы идентификации с нулевой передачей знаний для более четкого выявления ее основной концепции. Прежде всего выбирают случайное значение модуля , который является произведением двух больших простых чисел. Модуль
должен иметь длину 512 - 1024 бит. Это значение
может быть представлено группе пользователей, которым придется доказывать свою подлинность. В процессе идентификации участвуют две стороны:
- сторона А, доказывающая свою подлинность,
- сторона В, проверяющая представляемое стороной А доказательство.
Для того чтобы сгенерировать открытый и секретный ключи для стороны А, доверенный арбитр (Центр) выбирает некоторое число , которое является квадратичным вычетом по модулю
. Иначе говоря, выбирается такое число
, что сравнение
имеет решение и существует целое число
.
Выбранное значение является открытым ключом для А. Затем вычисляют наименьшее значение S, для которого
. Это значение S является секретным ключом для А.
Теперь можно приступить к выполнению протокола идентификации.
1. Сторона А выбирает некоторое случайное число , где
. Затем она вычисляет
и отправляет
стороне В.
2. Сторона В посылает А случайный бит .
3. Если , тогда А отправляет
стороне В. Если
, то А отправляет стороне В
.
4. Если , то сторона B проверяет, что
,чтобы убедиться, что А знает
. Если
, сторона В проверяет, что
, чтобы быть уверенной, что А знает
.
Эти шаги образуют один цикл протокола, называемый аккредитацией. Стороны А и В повторяют этот цикл раз при разных случайных значениях
и
до тех пор, пока В не убедится, что А знает значение S.
Если сторона А не знает значения S, она может выбрать такое значение , которое позволит ей обмануть сторону В, если В отправит ей
, либо А может выбрать такое
, которое позволит обмануть В, если В отправит ей
. Но этого невозможно сделать в обоих случаях. Вероятность того, что А обманет В в одном цикле, составляет
. Вероятность обмануть B
циклах равна
.
Для того чтобы этот протокол работал, сторона А никогда не должна повторно использовать значение . Если А поступила бы таким образом, а сторона В отправила бы стороне А на шаге 2 другой случайный бит
, то В имела бы оба ответа А. После этого В может вычислить значение S, и для А все закончено.