Схема идентификации Фейге–Фиата–Шамира

В криптографии схема идентификации Фейге-Фиата-Шамира представляет собой тип параллельного доказательства с нулевым разглашением, разработанный Уриэлем Фейге , Амосом Фиатом и Ади Шамиром в 1988 году. Как и все доказательства с нулевым разглашением, она позволяет одной стороне, Доказывающей, доказать другой стороне, Проверяющей, что она обладает секретной информацией, не раскрывая Проверяющей, что это за секретная информация. Однако схема идентификации Фейге-Фиата-Шамира использует модульную арифметику и параллельный процесс проверки, который ограничивает количество сообщений между Доказывающей и Проверяющей.

Настраивать

Следуя общепринятому соглашению , назовем доказывающего Пегги, а проверяющего — Виктором.

Выберите два больших простых целых числа p и q и вычислите произведение n = pq . Создайте секретные числа, взаимно простые с n . Вычислите . Пегги и Виктор оба получают while и остаются в секрете. Затем Пегги отправляет числа . Это ее секретные номера входа. Виктору отправляет числа Пегги, когда она хочет идентифицировать себя для Виктора. Виктор не может восстановить числа Пегги из своих чисел из-за сложности определения модульного квадратного корня , когда разложение модуля неизвестно. ${\displaystyle s_{1},\cdots ,s_{k}}$ ${\displaystyle v_{i}\equiv s_{i}^{2}{\pmod {n}}}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle s_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle v_{i}}$

Процедура

1. Пегги выбирает случайное целое число , случайный знак и вычисляет . Пегги отправляет Виктору. ${\displaystyle r}$ ${\displaystyle s\in \{-1,1\}}$ ${\displaystyle s\cdot x\equiv r^{2}{\pmod {n}}}$ ${\displaystyle x}$
2. Виктор выбирает числа , равные 0 или 1. Виктор отправляет эти числа Пегги. ${\displaystyle a_{1},\cdots ,a_{k}}$ ${\displaystyle a_{i}}$
3. Пегги вычисляет . Пегги отправляет это число Виктору. ${\displaystyle y\equiv rs_{1}^{a_{1}}s_{2}^{a_{2}}\cdots s_{k}^{a_{k}}{\pmod {n}}}$
4. Виктор проверяет то и это ${\displaystyle y^{2}{\pmod {n}}\equiv \pm \,xv_{1}^{a_{1}}v_{2}^{a_{2}}\cdots v_{k}^{a_{k}}{\pmod {n}}}$ ${\displaystyle x\neq 0.}$

Эта процедура повторяется с различными значениями и до тех пор, пока Виктор не убедится, что Пегги действительно обладает модульными квадратными корнями ( ) его чисел. ${\displaystyle r}$ ${\displaystyle a_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle v_{i}}$

Безопасность

В ходе процедуры Пегги не дает Виктору никакой полезной информации. Она просто доказывает Виктору, что у нее есть секретные номера, не раскрывая, что это за номера. Любой, кто перехватит связь между Пегги и Виктором, узнает только одну и ту же информацию. Подслушивающий не узнает ничего полезного о секретных номерах Пегги. ^{[ необходима цитата ]}

Предположим, что Ева перехватила числа Виктора, но не знает, какие числа у Пегги. Если Ева хочет убедить Виктора, что она Пегги, ей придется правильно угадать, какие числа у Виктора. Затем она выбирает случайное , вычисляет и отправляет Виктору. Когда Виктор отправляет , Ева просто возвращает ей . Виктор удовлетворен и приходит к выводу, что у Евы есть секретные числа. Однако вероятность того, что Ева правильно угадает, какие числа у Виктора, составляет 1 из . При повторении процедуры раз вероятность падает до 1 из . Для и вероятность успешно выдать себя за Пегги меньше 1 из 1 миллиона. ${\displaystyle v_{i}}$ ${\displaystyle s_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle y}$ ${\displaystyle x\equiv y^{2}v_{1}^{-a_{1}}v_{2}^{-a_{2}}\cdots v_{k}^{-a_{k}}{\pmod {n}}}$ ${\displaystyle x}$ ${\displaystyle a_{i}}$ ${\displaystyle y}$ ${\displaystyle a_{i}}$ ${\displaystyle 2^{k}}$ ${\displaystyle t}$ ${\displaystyle 2^{kt}}$ ${\displaystyle k=5}$ ${\displaystyle t=4}$

Ссылки

• Фейге, Уриэль; Фиат, Амос; Шамир, Ади (1988). «Доказательства идентичности с нулевым разглашением». Журнал криптологии . 1 (2): 77–94. doi : 10.1007/BF02351717 . S2CID  2950602.
• Трапп, Уэйд; Вашингтон, Лоуренс К. (2003). Введение в криптографию с теорией кодирования . Верхняя Сэддл-Ривер: Prentice-Hall. стр. 231–233. ISBN 0-13-061814-4.
• Вонг, Чунг Кей; Лам, Саймон С. (август 1999 г.). «Цифровые подписи для потоков и многоадресной передачи» (PDF) . Труды IEEE/ACM по сетям . 7 (4).(eFFS, расширенная схема Фейге–Фиата–Шамира)