Протокол Фейга — Фиата — Шамира

В 1986 году израильские учёные из Института Ваймана Уриэль Фейге, Амос Фиат и Ади Шамир разработали практичную схему идентификации с нулевым разглашением, которая могла быть имплементирована даже на устройствах с маломощными процессорами, таких как смарт-карты, персональные компьютеры, документы идентификации личности[1]. Из коммерческих соображений 9 июля 1986 года авторы подали заявку на получение патента США. Ведомство по патентам и товарным знакам США в течение полугода должно было определиться с решением о вынесении приказа об устранении режима секретности[2][3].

Буквально за несколько дней до истечения определённого срока Ведомство по патентам вынесло приказ, запрещающий всякое раскрытие или публикацию информации о протоколе, объясняя это угрозой причинения ущерба национальной безопасности. Более того, авторы должны были уведомить всех граждан США, располагающих знаниями о схеме Фейга — Фиата — Шамира, о том, что их разглашение могло привести к серьёзным санкциям - двум годам тюремного заключения или штрафу в десять тысяч долларов. Также необходимо было доложить обо всех иностранных государствах, которым была раскрыта информация о проведенном исследовании[2][3].

К этому моменту Фейге, Фиат и Шамир уже успели выступить с многочисленными докладами в университетах Израиля, Европы и США и подали заявку на конференцию Ассоциации вычислительной техники, которая должна была состояться в Нью-Йорке в мае 1987 года[2][3].

Хотя разработчики протокола и надеялись на то, что Институт Вейцмана, где проводилось исследование, будет обжаловать вынесенный приказ, они все же отправили письмо в комитет конференции, в котором объяснили сложившуюся ситуацию. После этого многие организации, такие как «Лаборатории Белла» и The New York Times, быстро подключились к решению возникшей проблемы. Наибольший вклад был внесён Агентством национальной безопасности (АНБ), которому изначально было неизвестно об изданном приказе. После того как АНБ о нём сообщили, в течение двух суток приказ был аннулирован[2][3].

Шамир выступил на конференции Ассоциации вычислительной техники 26 мая[4], а ещё через 5 дней авторы получили патент на разработанный протокол[5].

A доказывает своё знание секрета ${\displaystyle s}$ стороне B в течение ${\displaystyle t}$ раундов, не раскрывая при этом ни одного бита самого секрета[1].

Лемма 1: Если A и B следуют протоколу, то B всегда принимает доказательства A: Доказательство: по определению

${\displaystyle z=y^{2}\cdot \prod _{i=1}^{k}v_{i}^{e_{i}}=r^{2}\cdot \prod _{i=1}^{k}(s_{i}^{2e_{i}}v_{i}^{e_{i}})=\pm r^{2}=\pm x\mod n}$

— Amos Fiat, Adi Shamir «How To Prove Yourself: Practical Solutions to Identification and Signature Problems»

В предположении, что разложение ${\displaystyle n}$ на множители - вычислительно невозможная задача, вероятность успешной атаки на протокол составляет ${\displaystyle 2^{-kt}}$. Злоумышленник может попытаться выдать себя за честного пользователя путём угадывания правильных значений ${\displaystyle e_{i}}$, подготовления ${\displaystyle x=\pm r^{2}\cdot \prod _{i=1}^{k}v_{i}^{e_{i}}\mod n}$ для первого шага и предоставления ${\displaystyle y=r}$ на третьем шаге. Тогда B убедится, что ${\displaystyle z=y^{2}\cdot \prod _{i=1}^{k}v_{i}^{e_{i}}=r^{2}\cdot \prod _{i=1}^{k}v_{i}^{e_{i}}=\pm x}$. Но вероятность правильно выбрать ${\displaystyle k}$ значений ${\displaystyle (e_{1},e_{2},...,e_{k})}$ составляет ${\displaystyle 2^{-k}}$ в одном раунде и, следовательно, ${\displaystyle 2^{-kt}}$ во всем протоколе[1].

Таким образом, для достижения уровня безопасности, например, ${\displaystyle 2^{-20}}$ достаточно выбрать ${\displaystyle k=5}$ и ${\displaystyle t=4}$. Это означает, что только одна из миллиона попыток нечестного пользователя обмануть проверяющего может увенчаться успехом.

Протокол доказывает, что A обладает своим секретным ключом, не раскрывая никакого знания о нём, когда ${\displaystyle k=O(\log \log n)}$ и ${\displaystyle t=O(\log n)}$[1].

1. Пусть доверенный центр T выбрал простые числа ${\displaystyle p=683}$ и ${\displaystyle q=811}$ и опубликовал ${\displaystyle n=pq=553913}$. Параметры безопасности системы: ${\displaystyle k=3}$, ${\displaystyle t=1}$.
2. Для участника A выбираются случайные числа: ${\displaystyle s_{1}=187}$, ${\displaystyle s_{2}=37411}$, ${\displaystyle s_{3}=5204}$ и 3 бита: ${\displaystyle b_{1}=1}$, ${\displaystyle b_{2}=1}$, ${\displaystyle b_{3}=0}$.

   вычисляются значения: ${\displaystyle v_{1}=307124}$, ${\displaystyle v_{2}=115268}$, ${\displaystyle v_{3}=403211}$.

   Публичный ключ A: ${\displaystyle (307124,115268,403211;553913)}$, секретный ключ: ${\displaystyle (187,37411,5204)}$.

3. (a) A выбирает случайное число ${\displaystyle r=1337}$, случайный бит ${\displaystyle b=1}$, вычисляет: ${\displaystyle x=428083}$ и пересылает его B.

(b) B посылает A 3-битный вектор: ${\displaystyle (0,1,0)}$.

(c) A вычисляет и отправляет B: ${\displaystyle y=r\cdot s_{2}\mod n=166337}$.

(d) B вычисляет: ${\displaystyle z=y^{2}\cdot v_{2}\mod n=428083}$ и принимает доказательство A, так как ${\displaystyle z=\pm x\mod n}$ и ${\displaystyle z\neq 0}$.

1. Можно отказаться от выбора общего для всех участников числа ${\displaystyle n}$ и позволить каждому из них выбирать своё собственное. Однако существование доверенного центра T по-прежнему будет необходимо для того, чтобы ассоциировать каждого участника с его модулем[6].
2. Для того чтобы снизить сложность взаимодействия между A и B, можно заменить первое посылаемое от A к B сообщение ${\displaystyle x}$ на значение хеш-функции ${\displaystyle h(x)}$. Соответственно, на последней итерации протокола B должен будет оперировать ${\displaystyle h(z)}$ вместо самого ${\displaystyle z}$[6].
3. Схему можно изменить так, чтобы она основывалась на идентичности каждого участника. Для этого каждому пользователю A доверенный центр T назначает уникальную идентифицирующую строку ${\displaystyle I_{A}}$ с информацией об участнике (например, имя, адрес, номер паспорта и т. д.). Затем центр вычисляет значения ${\displaystyle v_{i}=f(I_{A},i),1\leqslant i\leqslant k}$, где ${\displaystyle f}$ должна быть неотличима от случайной функции за полиномиальное время. Потом, зная факторизацию ${\displaystyle n}$, доверенный центр вычисляет ${\displaystyle s_{i}={\sqrt {v_{i}^{-1}}}\mod n}$ и выдает их значения A. Значения ${\displaystyle v_{i}}$ и ${\displaystyle s_{i}}$ становятся, соответственно, открытым и секретным ключами участника A, и дальнейшие действия выполняются по схеме, описанной выше[7][6][3].
4. Описанный протокол можно выполнять параллельно. В таком случае сообщения, передаваемые от A к B и обратно, должны содержать данные для всех ${\displaystyle t}$ раундов одновременно. Плюс данного подхода в том, что он позволяет снизить сложность выполнения за счёт уменьшения количества производимых итераций. Такая схема является безопасной, но в силу технических причин теряет своё свойство нулевого разглашения. Дело в том, что параллельное выполнение может позволить нечестному проверяющему B определять ${\displaystyle e_{it}}$ не случайным образом, а как функции от всего набора ${\displaystyle x_{t}}$, присылаемого ему от A на первом шаге. Если B будет делать это, используя одностороннюю хеш-функцию, то он сможет получить информацию, которую иначе мог бы вычислить только при условии знания секрета A. Однако считается, что эта информация не является «полезной» (зная её, B не сможет выдать себя за A какому-то другому участнику), что позволяет считать схему по-прежнему надёжной[1][8].

В интерактивной схеме идентификации сторона B играет крайне важную роль — она генерирует случайные значения ${\displaystyle e_{i}}$, которые препятствуют мошенничеству участника A.

Для того чтобы переделать схему идентификации в схему подписи, достаточно изменить это действие B на использование секретной хеш-функции ${\displaystyle h}$ для вычисления ${\displaystyle e_{i}}$[7][6][3].

• Fiat A., Shamir A. How to Prove Yourself: Practical Solutions to Identification and Signature Problems (англ.) // Advances in Cryptology — CRYPTO ’86: 6th Annual International Cryptology Conference, Santa Barbara, California, USA, 1986, Proceedings / A. M. Odlyzko — Berlin, Heidelberg, New York, NY, London [etc.]: Springer Berlin Heidelberg, 1987. — P. 186—194. — 490 p. — (Lecture Notes in Computer Science; Vol. 263) — ISBN 978-3-540-18047-0 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-47721-7_12
• Landau S. Zero Knowledge and the Department of Defense (англ.) // Notices Amer. Math. Soc. / F. Morgan — AMS, 1988. — Vol. 35, Iss. 1. — P. 5—12. — ISSN 0002-9920; 1088-9477
• Feige U., Fiat A., Shamir A. Zero-Knowledge Proofs of Identity (англ.) // Journal of Cryptology / I. Damgård — Springer Science+Business Media, International Association for Cryptologic Research, 1988. — Vol. 1, Iss. 2. — P. 77–94. — ISSN 0933-2790; 1432-1378 — doi:10.1007/BF02351717
• Menezes A. J., Oorschot P. v., Vanstone S. A. Handbook of Applied Cryptography (англ.) — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.