Протокол Fiat-Shamir

Протокол Fiat-Shamir — это криптографический метод преобразования интерактивных протоколов доказательства с нулевым разглашением (zero-knowledge proof) в неинтерактивные, то есть в доказательства, которые могут быть проверены без участия доказывающей стороны в реальном времени. Разработан в 1986 году израильскими учёными Амосом Фиатом и Ади Шамиром. Протокол лёг в основу многих современных систем аутентификации, цифровых подписей и децентрализованных технологий, включая блокчейн.

История

Протокол был предложен в 1986 году Амосом Фиатом и Ади Шамиром в статье «How to prove yourself: practical solutions to identification and signature problems». Изначально он был создан как схема идентификации, основанная на задаче дискретного логарифмирования. В 1988 году Фиат и Шамир опубликовали расширение, которое позволяло преобразовывать любые интерактивные протоколы доказательства с нулевым разглашением в неинтерактивные, используя хеш-функцию в качестве «оракула» (модель случайного оракула). Это преобразование стало известно как «эвристика Фиата-Шамира» (Fiat-Shamir heuristic).

В 1990-е годы протокол активно применялся в системах электронной аутентификации, таких как стандарты ISO/IEC 9798. С развитием блокчейна и криптовалют в 2010-х годах протокол Fiat-Shamir стал ключевым компонентом для создания доказательств с нулевым разглашением (ZK-SNARKs, ZK-STARKs), используемых в сетях Zcash, Ethereum (после обновления Byzantium) и других.

Принцип работы

Протокол Fiat-Shamir основан на идее замены случайных запросов (challenges) верификатора в интерактивном протоколе на значения, вычисляемые с помощью криптографической хеш-функции от данных, доступных доказывающей стороне. Это позволяет доказывающему самостоятельно генерировать «вызовы», не взаимодействуя с верификатором, что делает протокол неинтерактивным.

Интерактивная версия (схема идентификации Фиата-Шамира)

В оригинальной интерактивной схеме участвуют две стороны: доказывающий (Prover) и верификатор (Verifier). Доказывающий знает секретный ключ \( s \), а верификатор знает открытый ключ \( v = s^2 \mod n \), где \( n \) — произведение двух больших простых чисел (задача факторизации). Протокол состоит из трёх шагов:

1. Commitment (обязательство): Доказывающий выбирает случайное число \( r \), вычисляет \( x = r^2 \mod n \) и отправляет \( x \) верификатору.
2. Challenge (вызов): Верификатор случайным образом выбирает бит \( e \in \{0, 1\} \) и отправляет его доказывающему.
3. Response (ответ): Доказывающий вычисляет \( y = r \cdot s^e \mod n \) и отправляет \( y \) верификатору.

Верификатор проверяет, что \( y^2 \equiv x \cdot v^e \pmod{n} \). Если равенство выполняется, доказательство считается принятым. Протокол повторяется \( k \) раз для достижения требуемого уровня безопасности (например, \( k = 20 \) даёт вероятность обмана \( 2^{-20} \)).

Неинтерактивная версия (эвристика Фиата-Шамира)

В неинтерактивной версии доказывающий сам генерирует вызов \( e \) как хеш от всех предыдущих данных: \( e = H(x) \), где \( H \) — криптографическая хеш-функция (например, SHA-256). Затем он вычисляет ответ \( y \) и отправляет верификатору пару \( (x, y) \). Верификатор, получив доказательство, вычисляет \( e = H(x) \) и проверяет равенство \( y^2 \equiv x \cdot v^e \pmod{n} \). Поскольку хеш-функция детерминирована, верификатор может воспроизвести вызов без участия доказывающего.

Математическая основа

Безопасность протокола Fiat-Shamir опирается на две криптографические задачи:

• Задача факторизации: Вычисление квадратного корня по модулю составного числа \( n \) (нахождение \( s \) по \( v \)) эквивалентно факторизации \( n \). Если факторизация невозможна за полиномиальное время, то злоумышленник не может вычислить секретный ключ.
• Модель случайного оракула: Считается, что хеш-функция ведёт себя как идеальный случайный оракул, то есть её выходы непредсказуемы для любого ограниченного вычислителя. Это позволяет гарантировать, что злоумышленник не может предсказать вызов \( e \) до того, как выберет \( x \).

Свойства

• Полнота: Если доказывающий знает секретный ключ, он всегда может пройти проверку (вероятность ошибки — 0).
• Корректность: Вероятность того, что злоумышленник, не знающий секрета, сможет обмануть верификатора, экспоненциально мала (при достаточном числе раундов).
• Нулевое разглашение: В интерактивной версии верификатор не получает никакой информации о секретном ключе, кроме факта, что доказывающий его знает. В неинтерактивной версии это свойство ослаблено, но сохраняется в модели случайного оракула.
• Неинтерактивность: В неинтерактивной версии доказательство состоит из одного сообщения, что упрощает его передачу и хранение.

Применение

Цифровые подписи

Протокол Fiat-Shamir используется для построения схем цифровой подписи, таких как Schnorr signature (на основе дискретного логарифмирования) и Fiat-Shamir signature (на основе факторизации). В этих схемах подпись сообщения \( m \) вычисляется как \( (x, y) \), где \( x = g^r \), \( e = H(x, m) \), \( y = r + s \cdot e \mod q \). Проверка подписи выполняется по формуле \( g^y \equiv x \cdot v^e \pmod{p} \). Такие подписи компактны и эффективны, что делает их популярными в блокчейне (например, в сети Bitcoin для подписи транзакций используется Schnorr после обновления Taproot в 2021 году).

Доказательства с нулевым разглашением (ZK-Proofs)

Протокол Fiat-Shamir является основой для многих современных ZK-доказательств, включая ZK-SNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge). В ZK-SNARKs, используемых в криптовалюте Zcash (организация Electric Coin Company — признана иноагентом в РФ) и сети Ethereum, протокол Fiat-Shamir применяется для преобразования интерактивных протоколов (например, Groth16) в неинтерактивные, что позволяет проверять транзакции без раскрытия их деталей.

Аутентификация

В системах аутентификации протокол Fiat-Shamir используется для создания одноразовых паролей и схем «доказательства знания» (proof of knowledge). Например, в стандарте ISO/IEC 9798-5 (механизмы аутентификации на основе нулевого разглашения) применяется вариант протокола Fiat-Shamir.

Блокчейн и децентрализованные системы

В блокчейне протокол Fiat-Shamir используется для создания компактных доказательств, которые могут быть проверены смарт-контрактами. Например, в сети Ethereum для проверки ZK-доказательств в контрактах (например, в проекте zkSync) применяется эвристика Фиата-Шамира. В протоколе StarkNet (разработчик StarkWare Industries) используются ZK-STARKs, которые также основаны на неинтерактивных доказательствах, полученных через эвристику Фиата-Шамира.

Критика и ограничения

• Модель случайного оракула: Безопасность протокола Fiat-Shamir доказана только в модели случайного оракула. В реальных системах хеш-функции могут иметь уязвимости, что теоретически может привести к компрометации. Однако на практике атак на основе этой модели не зафиксировано.
• Атаки на основе квантовых вычислений: Протокол Fiat-Shamir, основанный на задачах факторизации и дискретного логарифмирования, уязвим для атак с использованием квантовых компьютеров (алгоритм Шора). В постквантовой криптографии разрабатываются альтернативы, такие как схемы на основе решёток (например, Falcon, Dilithium).
• Размер доказательства: В неинтерактивной версии доказательство может быть большим, если требуется высокая безопасность (много раундов). Однако в современных ZK-доказательствах (например, Groth16) размер доказательства постоянен (несколько сотен байт).

Интересные факты

• Эвристика Фиата-Шамира была предложена до формального доказательства её безопасности в модели случайного оракула. Доказательство было дано в 1993 году Михаэлем Белларе и Филиппом Рогауэем в работе «Random oracles are practical: a paradigm for designing efficient protocols».
• Ади Шамир — один из создателей криптосистемы RSA (Rivest–Shamir–Adleman), а Амос Фиат — израильский криптограф, также известный работами по аутентификации.
• Протокол Fiat-Shamir используется в стандарте ED25519 (Edwards-curve Digital Signature Algorithm), который является вариантом схемы Schnorr и применяется в системах SSH, Tor, Bitcoin.

Источники

• Fiat, A., Shamir, A. (1986). «How to prove yourself: practical solutions to identification and signature problems». Proceedings of CRYPTO.
• Bellare, M., Rogaway, P. (1993). «Random oracles are practical: a paradigm for designing efficient protocols». Proceedings of the 1st ACM Conference on Computer and Communications Security.
• Schnorr, C. P. (1990). «Efficient identification and signatures for smart cards». Advances in Cryptology — CRYPTO'89.
• Goldreich, O. (2001). «Foundations of Cryptography: Volume 1, Basic Tools». Cambridge University Press.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.
• ISO/IEC 9798-5:2004 «Information technology — Security techniques — Entity authentication — Part 5: Mechanisms using zero-knowledge techniques».