В главе 10 HAC (10.4.2) мы видим хорошо известный протокол идентификации Фейге-Фиат-Шамира, основанный на доказательстве с нулевым знанием, использующем (предполагаемую) сложность извлечения квадратных корней по модулю композита, который трудно проанализировать. Я дам схему своими словами (и, надеюсь, сделаю все правильно).
Давайте начнем с более простой схемы: пусть будет целым числом Блюма (так что и каждый из и равен 3 mod 4) достаточно большого размера, чтобы факторинг был интраабильным. Поскольку - целое число Блюма, половина элементов имеет символ Якоби +1, а другая половина - -1. Для элементов +1 половина из них имеет квадратные корни, а каждый элемент, имеющий квадратный корень, имеет четыре из них, ровно один сам является квадратом.
Теперь Пегги выбирает случайный элемент из и устанавливает . Затем она отправляет к Виктору. Далее следует протокол: Виктор хочет убедиться, что Пегги знает квадратный корень из и Пегги хочет доказать это ему, не раскрывая ничего о кроме факта, что она знает такие .
- Пегги выбирает случайное значение в и отправляет Виктору.
- Виктор равновероятно отправляет или обратно Пегги.
- Пегги посылает Виктору.
Виктор может проверить, что Пегги отправила правильный ответ, возведя в квадрат то, что он получил, и сравнив с правильным результатом. Конечно, мы повторяем это взаимодействие, чтобы уменьшить вероятность того, что Пегги просто удачливая догадка. Этот протокол называется ZK; доказательства могут быть найдены в разных местах (например, конспекты лекций Вооза Барака ).
, Сейчас
- Пегги выбирает случайный в и отправляет Виктору.Z ∗ n r 2
- Виктор равновероятно отправляет значений из обратно в Пегги.b i { 0 , 1 }
- Пегги отправляет Виктору .
Мой вопрос: зачем биты знака ? В скобках HAC отмечает, что они присутствуют в качестве технического требования, необходимого для доказательства того, что секретная информация не пропущена. Страница Википедии для Feige-Fiat-Shamir (которая неправильно использует протокол) подразумевает, что без этого немного утечек.
Я не могу найти атаку, которая извлекает что-либо из Пегги, если она пропускает знаки.