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

Эта статья включает список ссылок , связанных чтений или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Январь 2014 ) ( Узнайте, как и когда удалять это сообщение )

В криптографии схема идентификации Фейге-Фиата-Шамира представляет собой тип параллельного доказательства с нулевым разглашением, разработанный Уриэлем Фейге , Амосом Фиатом и Ади Шамиром в 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 д}$${\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, расширенная схема Фейге–Фиата–Шамира)