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

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

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

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

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

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

История

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

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

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

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

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

Схема идентификации

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

Выбор параметров системы

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

Генерация секретов для участников

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

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

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

Действия протокола в рамках одного раунда

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

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

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

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

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

$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»

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

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

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

Пример

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

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

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

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

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

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

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

Улучшения и модификации схемы идентификации

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

Подпись Фейга — Фиата — Шамира

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

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

Подпись сообщения

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

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

Проверка подписи

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

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