В лекции Массачусетского технологического института (MIT OpenCourseWare) профессор Яэль Т. Калай подробно разбирает фундаментальные концепции современной криптографии — хэш-деревья Меркла, парадигму Фиата — Шамира и доказательства с нулевым разглашением. Лектор объясняет, как превратить интерактивные протоколы в неинтерактивные аргументы, пригодные для всеобщей проверки. В центре внимания оказываются не только теоретические конструкции, но и неожиданные уязвимости, возникающие при переносе идеальных моделей в реальную практику.
🌲 Хэш-функции Меркла и локальное открытие данных 1:29
В начале занятия Яэль Т. Калай кратко напоминает содержание предыдущей лекции, посвященной протоколу Килиана — Микали. Этот протокол представляет собой лаконичный (succinct) интерактивный аргумент, позволяющий доказать принадлежность слова любому языку из класса NP. Основная идея криптографического подхода заключается в сжатии гигантского доказательства PCP (Probabilistically Checkable Proof) до короткого дайджеста с помощью хэш-функций.
Для реализации этого механизма требуется не просто стандартная хэш-функция, сжимающая строку из $2\lambda$ бит в $\lambda$ бит. По словам лектора, для протокола Килиана — Микали необходима коллизионно-стойкая функция с возможностью локального открытия (local opening). Она должна эффективно сжимать экспоненциально большие строки размером $2^\lambda$ до размера параметра безопасности $\lambda$.
Конструкция хэша Меркла решает эту задачу путем построения бинарного дерева. Процесс вычисления выглядит следующим образом:
- Входная строка $x$ разбивается на блоки длиной $\lambda$ бит.
- Каждая пара соседних блоков хэшируется базовой функцией, уменьшая число блоков в два раза на каждом уровне дерева.
- Процесс повторяется иерархически, пока не останется один финальный блок, называемый корнем (root).
Результатом работы алгоритма являются корень дерева и значение его глубины $d$. Калай подчеркивает, что включение глубины $d$ в выходные данные критически важно для обеспечения стойкости к коллизиям. Без этого параметра злоумышленник мог бы скомпрометировать систему, представив поддельное открытие для дерева меньшей глубины, выдавая его за легитимное.
🛠️ Доказательство стойкости дерева Меркла к коллизиям 24:08
Для завершения анализа протокола Килиана — Микали профессор Калай приводит строгое доказательство того, что конструкция хэша Меркла сохраняет коллизионную стойкость базовой функции. Доказательство строится методом криптографического сведения (reduction). Предположим, что существует полиномиальный по времени алгоритм-противник $A$, способный найти коллизию для хэша Меркла с некоторой неперенебрежимой вероятностью $\epsilon$.
В таком сценарии противник возвращает корень дерева, индекс элемента $i$ и два различных валидных локальных открытия для этого индекса — одно для бита «0» и другое для бита «1». Схема локального открытия в дереве Меркла устроена очень изящно:
- Проверщику достаточно предоставить верификатору сам целевой блок данных.
- Вместе с ним передаются хэш-значения всех «соседних» блоков (siblings) на каждом уровне пути от листа к корню.
- Верификатор последовательно пересчитывает хэши снизу вверх и сверяет финальный результат с корнем.
Если верификатор успешно принимает оба варианта открытия, алгоритм сведения $B$ может использовать их для поиска коллизии в базовой хэш-функции $h$. Поскольку одно открытие заявляет в листе «0», а второе — «1», значения на самом нижнем уровне дерева гарантированно различаются. При этом корни обоих путей одинаковы, так как они представляют один и тот же исходный корень.
Из этого лектор делает логический вывод: в дереве обязательно должен существовать такой уровень $j$, на котором дочерние блоки в двух открытиях различаются, но их родительские блоки (результаты хэширования) совпадают. Обнаружение этой точки эквивалентно нахождению коллизии в базовой функции $h$ с той же вероятностью $\epsilon$. Поскольку базовая функция по условию коллизионно-стойкая, вероятность успешной атаки противника должна быть пренеближимо малой.
🔄 Парадигма Фиата — Шамира: устранение интерактивности 36:47
Несмотря на лаконичность протокола Килиана — Микали, его интерактивная природа серьезно ограничивает практическое применение. Интерактивные доказательства страдают от задержек сети (latency) и, что еще важнее, они привязаны к конкретному верификатору. Проверяющий не может просто опубликовать доказательство для всего мира — ему пришлось бы проводить сессию взаимодействия с каждым человеком отдельно. Для решения этой проблемы Калай вводит парадигму Фиата — Шамира, предложенную Амосом Фиатом и Ади Шамиром в 1986 году.
Изначально эта концепция создавалась для схем идентификации с целью их преобразования в схемы цифровой подписи. Однако впоследствии парадигму стали применять для устранения интерактивности из любых протоколов типа «открытая монета» (public coin). В таких протоколах все сообщения верификатора представляют собой исключительно случайные биты.
Идея устранения интерактивности по Фиату — Шамиру поразительно проста и элегантна:
- Вместо того чтобы ждать случайный вызов $\beta$ от верификатора, проверяющий вычисляет его самостоятельно.
- Для этого применяется фиксированная хэш-функция ко всему накопленному к данному моменту протоколу (транскрипту).
- В трехраундовом протоколе $(\alpha, \beta, \gamma)$ вызов вычисляется как $\beta = \text{eval}(hk, x, \alpha)$, где $x$ — утверждение, а $\alpha$ — первое сообщение.
- Если раундов больше, следующий вызов $\delta$ вычисляется как хэш от всей предыдущей цепочки: $(x, \alpha, \beta, \gamma)$.
В этой схеме ключ хэш-функции $hk$ генерируется один раз и становится публично известен всем участникам. В результате весь интерактивный процесс сжимается до отправки одного-единственного неинтерактивного сообщения, размер которого жестко ограничен полиномом от параметра безопасности $\lambda$ (например, 256 бит).
⚠️ Контрпримеры и границы безопасности парадигмы 52:46
Парадигма Фиата — Шамира де-факто стала стандартом в инженерной криптографии и используется повсеместно, включая SHA-256 и другие оптимизированные функции. Тем не менее, отвечающая на вопросы аудитории Яэль Калай озвучает обескураживающий факт: парадигма Фиата — Шамира не является абсолютно безопасной. В теоретической криптографии существуют строгие контрпримеры, доказывающие, что для некоторых протоколов применение Фиата — Шамира полностью разрушает надежность (soundness), вне зависимости от выбора семейства хэш-функций.
Лектор на верхнем уровне объясняет логику построения таких искусственных (contrived) контрпримеров:
- За основу берется любой надежный интерактивный протокол.
- В него вносится небольшое изменение: верификатор соглашается досрочно принять доказательство, если проверяющий сможет заранее угадать его случайный вызов $\beta$.
- В интерактивном режиме вероятность угадать случайную строку длиной $\lambda$ ничтожно мала и равна $1/2^\lambda$.
- Однако при переходе к неинтерактивной схеме Фиата — Шамира проверяющий видит алгоритм хэширования и может легко подобрать такое первое сообщение $\alpha$, которое в результате хэширования даст в точности предсказанный вызов.
По мнению профессора Калай, эти контрпримеры носят сугубо академический характер, и на практике их никто не использует. Тем не менее, они наглядно демонстрируют криптографам, что применять парадигму Фиата — Шамира «вслепую» категорически нельзя. Создать универсальное математическое доказательство ее безопасности для всех публичных протоколов невозможно именно из-за существования подобных аномалий.
🔮 Модель случайного оракула и введение в нулевое разглашение 1:02:32
Чтобы найти теоретический компромисс и строго обосновать безопасность неинтерактивных систем, в 1993 году исследователи Михир Белларе и Филлип Рогавей предложили концепцию модели случайного оракула (Random Oracle Model, ROM). В рамках этой идеализированной модели предполагается, что используемая хэш-функция заменяется абсолютно случайным оракулом, к которому обе стороны имеют равный доступ. Для проверяющего получение ответов от такого оракула математически неотличимо от взаимодействия с честным верификатором, генерирующим истинно случайные биты.
Последующая часть лекции посвящена переходу к теме доказательств с нулевым разглашением (Zero-Knowledge Proofs). Калай напоминает, что изначально интерактивные доказательства разрабатывались Шафи Гольдвассер, Сильвио Микали и Чарльзом Ракоффом в середине 1980-х годов именно ради свойства нулевого разглашения, а вовсе не ради лаконичности. Позже Одед Голдрейх, Сильвио Микали и Ави Вигдерсон доказали фундаментальную теорему о том, что абсолютно любой язык из класса NP обладает доказательством с нулевым разглашением.
Суть концепции ZK заключается в том, что доказывающий может убедить проверяющего в истинности утверждения (например, наличии секретного свидетельства), не раскрывая при этом абсолютно никакой посторонней информации. Проверяющий удостоверяется в факте, но не получает никаких математических зацепок, позволяющих ему самому реконструировать секрет.
🕹️ Протокол Блума для гамильтонова цикла и доказательство знания 1:07:02
В качестве классической и наглядной иллюстрации нулевого разглашения Яэль Калай подробно разбирает протокол Мануэля Блума для NP-полной задачи поиска гамильтонова цикла в графе $G$. Проверяющий хочет доказать, что знает замкнутый цикл, проходящий через все вершины графа ровно по одному разу, не раскрывая сам этот цикл.
Протокол состоит из трех последовательных шагов:
- Генерация и обязательство: Проверяющий выбирает случайную перестановку вершин $\pi$ и строит изолированный граф $\pi(G)$. Затем он помещает информацию о ребрах графа в условные «сейфы» (криптографические обязательства, commitment scheme) и передает их верификатору, сохраняя ключи у себя. Верификатор видит лишь закрытые коробки.
- Случайный вызов: Верификатор отправляет случайный бит вызова $B \in {0, 1}$.
- Раскрытие: Если $B=0$, проверяющий открывает абсолютно все сейфы, демонстрируя случайный гамильтонов цикл (благодаря перестановке $\pi$ этот цикл никак не выдает структуру исходного графа). Если $B=1$, проверяющий раскрывает саму перестановку $\pi$ и открывает только те сейфы, которые соответствуют отсутствующим ребрам в графе $\pi(G)$, доказывая, что в цикле не использовались недопустимые ребра.
По словам профессора Калай, данный протокол гарантирует надежность с ошибкой $1/2$: если графа не существует или проверяющий лжет, он сможет успешно ответить только на один из двух возможных вопросов верификатора. Чтобы снизить вероятность успешного обмана до пренебрежимо малой величины, сессии протокола необходимо повторять последовательно.
Строгое определение нулевого разглашения требует существования эффективного симулятора, способного воспроизвести вид транскрипта без участия реального проверяющего. Калай отмечает важный исторический рубеж: в 2001 году Боаз Барак совершил прорыв, впервые построив не-черноящичные (non-black-box) доказательства с нулевым разглашением. В заключение лектор подчеркивает, что протокол Блума фактически является доказательством знания (proof of knowledge): из алгоритма проверяющего можно математически «экстрагировать» сам гамильтонов цикл, если он способен отвечать на оба вызова верификатора.
