Почему Фейге-Фиат-Шамир не является Нулевым Знанием без знаковых битов?

12

В главе 10 HAC (10.4.2) мы видим хорошо известный протокол идентификации Фейге-Фиат-Шамира, основанный на доказательстве с нулевым знанием, использующем (предполагаемую) сложность извлечения квадратных корней по модулю композита, который трудно проанализировать. Я дам схему своими словами (и, надеюсь, сделаю все правильно).

Давайте начнем с более простой схемы: пусть n будет целым числом Блюма (так что n=pq и каждый из p и q равен 3 mod 4) достаточно большого размера, чтобы факторинг был интраабильным. Поскольку n - целое число Блюма, половина элементов Zn имеет символ Якоби +1, а другая половина - -1. Для элементов +1 половина из них имеет квадратные корни, а каждый элемент, имеющий квадратный корень, имеет четыре из них, ровно один сам является квадратом.

Теперь Пегги выбирает случайный элемент s из Zn и устанавливает v=s2 . Затем она отправляет v к Виктору. Далее следует протокол: Виктор хочет убедиться, что Пегги знает квадратный корень из v и Пегги хочет доказать это ему, не раскрывая ничего о s кроме факта, что она знает такие s .

  1. Пегги выбирает случайное значение r в Zn и отправляет r2 Виктору.
  2. Виктор равновероятно отправляет b=0 или b=1 обратно Пегги.
  3. Пегги посылает rsb Виктору.

Виктор может проверить, что Пегги отправила правильный ответ, возведя в квадрат то, что он получил, и сравнив с правильным результатом. Конечно, мы повторяем это взаимодействие, чтобы уменьшить вероятность того, что Пегги просто удачливая догадка. Этот протокол называется ZK; доказательства могут быть найдены в разных местах (например, конспекты лекций Вооза Барака ).

ks1skt1=±1,tk=±1v1=t1s12,,vk=tksk2vi, Сейчас

  1. Пегги выбирает случайный в и отправляет Виктору.Z n r 2rZnr2
  2. Виктор равновероятно отправляет значений из обратно в Пегги.b i { 0 , 1 }kbi{0,1}
  3. Пегги отправляет Виктору .rΠi=1ksibi

Мой вопрос: зачем биты знака ? В скобках HAC отмечает, что они присутствуют в качестве технического требования, необходимого для доказательства того, что секретная информация не пропущена. Страница Википедии для Feige-Fiat-Shamir (которая неправильно использует протокол) подразумевает, что без этого немного утечек.ti

Я не могу найти атаку, которая извлекает что-либо из Пегги, если она пропускает знаки.

Fixee
источник

Ответы:

8

Протокол идентификации Feige-Fiat-Shamir (FFS) является доказательством знания (PoK), в котором доказатель (Peggy) подтверждает свои знания квадратными корнями данного ввода для верификатора (Victor).

FFS хочет отличить PoK от доказательств принадлежности к языку , в которых Пегги доказывает, что вход обладает некоторым свойством (более формально вход принадлежит определенному языку).

Если мы не используем отрицательные знаки, возможно, что входные данные не имеют квадратного корня. Например, число 20 не имеет никаких квадратных корней по модулю 21. Поскольку различение квадратов и неквадратов является известной сложной проблемой , FFS избегает ее, позволяя вводить значение плюс или минус некоторого квадрата числа. В своих собственных словах (немного изменился):

vivi +1modnsivi

Под неограниченным вводом доказательств знания с нулевым знанием они подразумевают ZK PoK, соответствующее доказательство принадлежности к языку которого тривиально; т.е. V может сам решить, что вход является плюсом или минусом некоторого квадрата (просто проверяя символ Якоби).

М.С. Дусти
источник
Спасибо за ответ, но я все еще не следую: без знаков символ Якоби равен +1. Со знаками символ Якоби +1. Вы говорите выше: «Если мы не используем отрицательные знаки, возможно, что входные данные не имеют квадратного корня». Как это возможно? Входными данными для верификатора является список квадратов, которые (при условии честного прувера) всегда имеют квадратные корни.
Fixee
Второй вопрос: вы говорите, что знаки присутствуют только для доказательства, чтобы пройти? Или есть фактическая атака, если они опущены?
Fixee
@Fixee: Предположим, что обманщик доказывает, что выбирает свои открытые ключи ( ) не в соответствии с протоколом; скажем случайное значение, чей символ Якоби равен +1. (Плохой) верификатор не может сказать, есть ли у квадратные корни или нет. Единственный способ - запустить протокол и получить помощь от проверяющего. То есть, доказывающее это и доказывают ее знание «s, и дают доказательство членства языка (т.е. » S принадлежит lanuage QR квадратичных вычетов.) По какой - то причине, FFS любил отделить этот тип доказательства из "неограниченного ввода" доказательств. Я вижу это как простую техническую vivisivi
MS Dousti