Схема идентификации Фейге – Фиат – Шамира - Feige–Fiat–Shamir identification scheme

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

Настраивать

После общее соглашение Позовите испытателя Пегги и проверяющего Виктор.

Выберите два больших простых целых числа п и q и вычислим произведение п = pq. Создать секретные числа ${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 sin {-1,1}}$ и вычисляет ${displaystyle xequiv scdot r^{2}{pmod {n}}}$. Пегги отправляет ${displaystyle x}$ Виктору.
2. Виктор выбирает числа ${displaystyle a_{1},cdots ,a_{k}}$ куда ${displaystyle a_{i}}$ равно 0 или 1. Виктор отправляет эти числа Пегги.
3. Пегги вычисляет ${displaystyle yequiv rs_{1}^{a_{1}}s_{2}^{a_{2}}cdots s_{k}^{a_{k}}{pmod {n}}}$. Пегги отправляет этот номер Виктору.
4. Виктор проверяет это ${displaystyle y^{2}equiv pm ,xv_{1}^{a_{1}}v_{2}^{a_{2}}cdots v_{k}^{a_{k}}{pmod {n}}}$ и это ${displaystyle xeq 0.}$

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

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

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

Предположим, Ева перехватила ${displaystyle v_{i}}$ числа, но не знает, что Пегги ${displaystyle s_{i}}$ числа есть. Если Ева хочет попытаться убедить Виктора, что она Пегги, ей придется правильно угадать, что такое Виктор. ${displaystyle a_{i}}$ числа будут. Затем она выбирает случайный ${displaystyle y}$, вычисляет ${displaystyle xequiv 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}}$ будет 1 в ${displaystyle 2^{k}}$. Повторяя процедуру ${displaystyle t}$ раз вероятность падает до 1 в ${displaystyle 2^{kt}}$ . За ${displaystyle k=5}$ и ${displaystyle t=4}$ вероятность успешно выдать себя за Пегги составляет менее 1 из 1 миллиона.

Рекомендации

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