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

Протокол Фейга — Фиата — Шамира — протокол идентификации с нулевым разглашением, обобщение более раннего протокола Фиата — Шамира, разработанный Уриэлем Фейге (англ. Uriel Feige), Амосом Фиатом^[англ.] (англ. Amos Fiat) и Ади Шамиром (англ. Adi Shamir) в 1986 году. Эта простая для реализации и коммерчески значимая схема была запатентована авторами через год после её разработки.

Протокол позволяет одному участнику (доказывающему A) доказать другому участнику (проверяющему B), что он обладает секретной информацией, не раскрывая ни единого бита этой информации.

Безопасность протокола основана на сложности извлечения квадратного корня по модулю достаточно большого составного числа n, факторизация которого неизвестна.

Существуют некоторые улучшения основной версии протокола, позволяющие уменьшить сложность взаимодействий между участниками или встроить в схему идентификационные данные.

Кроме того, схему идентификации Фейга-Фиата-Шамира можно легко преобразовать в схему подписи.

В 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].

Доверенный центр T публикует большое число ${\displaystyle n=pq}$, где ${\displaystyle p}$ и ${\displaystyle q}$ — простые числа, которые держатся в секрете. Также выбираются целые числа ${\displaystyle k}$ и ${\displaystyle t}$ - параметры безопасности^[6].

Каждый участник выбирает ${\displaystyle k}$ случайных целых чисел ${\displaystyle s_{1},s_{2},...,s_{k},1\leqslant s_{i}\leqslant n-1}$ и ${\displaystyle k}$ случайных бит ${\displaystyle b_{1},b_{2},...,b_{k}}$.

Затем вычисляет ${\displaystyle v_{i}=(-1)^{b_{i}}\cdot (s_{i}^{2})^{-1}\mod n,1\leqslant i\leqslant k}$.

Участник идентифицирует себя окружающим с помощью значений ${\displaystyle (v_{1},v_{2},...,v_{k};n)}$, которые выступают в качестве его открытого ключа, в то время как секретный ключ ${\displaystyle s=(s_{1},s_{2},...,s_{k})}$ известен только самому участнику^[6].

1. A выбирает случайное целое число ${\displaystyle r,1\leqslant r\leqslant n-1}$

   вычисляет: ${\displaystyle x=r^{2}\mod n}$ и отправляет ${\displaystyle x}$ стороне B.

2. B отправляет A случайный ${\displaystyle k}$-битный вектор ${\displaystyle (e_{1},e_{2},...,e_{k})}$, где ${\displaystyle e_{i}=0}$ или ${\displaystyle e_{i}=1}$.
3. A вычисляет и отправляет B: ${\displaystyle y=r\cdot \prod _{i=1}^{k}s_{i}^{e_{i}}\mod n}$.
4. B вычисляет: ${\displaystyle z=y^{2}\cdot \prod _{i=1}^{k}v_{i}^{e_{i}}\mod n}$ и проверяет, что ${\displaystyle z=\pm x\mod n}$ и ${\displaystyle z\neq 0}$^[7][6].

Лемма 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].

Пусть A хочет подписать сообщение ${\displaystyle m}$.

1. A выбирает случайное целое число ${\displaystyle r,1\leqslant r\leqslant n-1}$ и вычисляет: ${\displaystyle x=r^{2}\mod n}$.
2. A вычисляет: ${\displaystyle e_{i}=h(x||m),1\leqslant i\leqslant k}$.
3. A вычисляет: ${\displaystyle y=r\cdot \prod _{i=1}^{k}s_{i}^{e_{i}}\mod n}$.
4. A отправляет B сообщение ${\displaystyle m}$, подпись ${\displaystyle (e_{1},e_{2},...,e_{k})}$ и ${\displaystyle y}$.

Пусть B хочет проверить подпись под сообщением ${\displaystyle m}$.

1. B вычисляет: ${\displaystyle x'=y^{2}\cdot \prod _{i=1}^{k}v_{i}^{e_{i}}\mod n}$.
2. B использует ${\displaystyle x'}$ для вычисления ${\displaystyle e'_{i}}$: ${\displaystyle e'_{i}=h(x'||m),1\leqslant i\leqslant k}$.
3. Если вычисленные значения ${\displaystyle (e'_{1},e'_{2},...,e'_{k})}$ совпадают с полученной от A подписью ${\displaystyle (e_{1},e_{2},...,e_{k})}$, то B принимает подпись ${\displaystyle m}$.

• 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 City, London: 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 of the American Mathematical Society / 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 (англ.) — Boca Raton: CRC Press, 1997. — 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.