В рамках очередного занятия профессор MIT подробно разбирает вторую часть протокола Килиана — Микали, акцентируя внимание на повышении эффективности криптографических доказательств. В центре дискуссии находятся концепция универсальных аргументов Барака — Голдрейха и пошаговое построение надежной хеш-функции. Материал объясняет, как перейти от теоретических допущений теории сложности к практическим инструментам защиты данных, таким как деревья Меркла.
🔄 Повторение аргументов и загадки теории сложности 0:12
Во время перерыва лектору задали важный вопрос, касающийся терминологии и внутренней логики интерактивных доказательств. В теории интерактивных доказательств (interactive proofs) стандартная ошибка достоверности (soundness) принимается равной 1/2, и если требуется уменьшить её, применяется параллельное повторение. Однако при переходе к интерактивным аргументам (interactive arguments) лектор сразу ввела понятие пренебрежимо малой (negligible) ошибки.
Причина такого изменения терминологии кроется в специфических свойствах криптографического мира. Для интерактивных доказательств параллельное повторение $\lambda$ раз снижает ошибку достоверности экспоненциально — до уровня $1/2^\lambda$. В случае же с криптографическими аргументами это правило работает не всегда. Существуют искусственные, хотя и крайне надуманные примеры протоколов, где параллельное повторение не уменьшает ошибку достоверности.
По мнению профессора, для любого «естественного» аргумента параллельное повторение все же снизит ошибку экспоненциально. Тем не менее, поскольку в общем виде это не доказано, криптографы используют два решения:
- Последовательное повторение (sequential repetition): Оно гарантированно снижает ошибку экспоненциально, но увеличивает раундовую сложность протокола в $\lambda$ раз.
- Использование пренебрежимо малой величины: Её вводят непосредственно в определение стойкости аргумента, чтобы избежать изменения раундовой сложности и не выполнять повторение «бесплатно», как в обычных доказательствах.
Именно поэтому в криптографических аргументах константы вроде $1/2$ или $2/3$ не так удобны, как в классических доказательствах, и исследователи сразу требуют достижения пренебрежимо малых вероятностей успеха для злоумышленника.
🚀 Универсальные аргументы Барака — Голдрейха 3:17
Основная часть лекции началась с обзора работы Боаза Барака и Одеда Голдрейха, предложивших концепцию «универсальных аргументов». Профессор пообещала добавить ссылку на их статью на сайт курса, отметив, что вводная часть публикации исключительно удачно объясняет логику доказательства.
Главная идея Барака и Голдрейха состояла в оптимизации проверки вероятностно проверяемых доказательств (PCP). В протоколе Килиана — Микали для выявления обмана со стороны доказывающего анализируется все PCP целиком, что заставляет алгоритм работать пропорционально его размеру $N$. Подход Барака — Голдрейха предлагает проверять каждый запрос к PCP изолированно.
Анализ протокола строится на разделении индексов доказательства на категории:
- «Хороший» индекс: При повторных запусках сгенерированный верификатором обманывающий доказывающий почти всегда дает один и тот же согласованный ответ (бит).
- «Плохой» индекс: Доказывающий с некоторой нежелательной нелинейной вероятностью $\epsilon^3$ выдает противоречивые ответы (то 0, то 1).
Если доказывающий часто дает разные ответы на один и тот же запрос, то это позволяет мгновенно обнаружить коллизию в хеш-функции. Математический анализ Барака — Голдрейха показывает, что значительная часть индексов обязана быть «плохими». Если бы почти все индексы были «хорошими», верификатор принял бы доказательство с высокой вероятностью, что позволило бы полностью реконструировать корректное PCP.
Для взлома хеш-функции злоумышленнику достаточно выбрать случайный индекс $i$ и запустить верификатор дважды с разным набором случайных чисел, включающих этот индекс. Протокол опирается на естественное свойство всех известных PCP: зная индекс $i$, легко найти случайную строку $r$, которая заставит верификатор обратиться именно к этому индексу.
Благодаря такому подходу время работы алгоритма взлома коллизий зависит только от параметра безопасности и величины $\epsilon$, оставаясь полностью независимым от размера PCP или времени работы машины Тьюринга $T$. Именно эта независимость от параметров вычислений, передаваемых в бинарном виде, и дала аргументам название «универсальные».
🔐 Строительный блок: хеш-функция на основе дискретного логарифма 11:55
Для реализации описанных протоколов необходима коллизионно-стойкая хеш-функция. Профессор предложила начать с простого строительного блока, который уменьшает входные данные всего в два раза и не поддерживает локальное открытие.
Данная конструкция базируется на классической задаче дискретного логарифмирования. Предполагается существование конечной группы $G$ порядка $2^\lambda$ элементов с генератором $g$. Суть допущения заключается в том, что по заданному значению $g^x$ для случайного $x$ вычислительно крайне сложно найти сам показатель $x$. Вероятность того, что любой полиномиальный по времени алгоритм сможет решить эту задачу, является пренебрежимо малой.
Отвечая на вопрос аудитории о квантовой угрозе, лектор признала, что ученые верят в сложность этой задачи главным образом потому, что до сих пор не смогли найти эффективный классический алгоритм ее решения. При этом известно, что квантовые компьютеры способны взломать дискретный логарифм за полиномиальное время (алгоритм Шора), а для классических машин лучшие методы имеют субэкспоненциальную сложность порядка $2^{n^{1/3}}$.
Конкретный алгоритм построения функции выглядит следующим образом:
- Выбирается безопасное простое число $p = 2q + 1$, где $q$ также является простым.
- В качестве группы $G$ берется подгруппа квадратичных вычетов по модулю $p$ (все числа вида $x^2 \pmod p$). Она содержит ровно $(p-1)/2 = q$ элементов.
- Алгоритм генерации ключа
Genвыбирает случайный элемент $h \in G$, который становится открытым ключом хеша. В этом ключе нет секретов, злоумышленнику можно без опасений передавать даже случайные числа, использованные при генерации. - Функция вычисления
Evalпринимает на вход пару чисел $(x_0, x_1) \in \mathbb{Z}_q \times \mathbb{Z}_q$ и возвращает элемент группы по формуле $g^{x_0} \cdot h^{x_1}$.
Для доказательства коллиционной стойкости (известного в криптографии как схема обязательств Педерсена) предполагается, что нашелся алгоритм, способный выдать два разных входа $(x_0, x_1)$ и $(x_0', x_1')$, дающих одинаковый хеш. Из равенства $g^{x_0} h^{x_1} = g^{x_0'} h^{x_1'}$ путем преобразований получаем:
$$g^{x_0 - x_0'} = h^{x_1' - x_1}$$
Поскольку $G$ — группа простого порядка $q$, любой её элемент (кроме единицы) является генератором. Если $x_1' \neq x_1$, мы можем разделить показатели степени по модулю $q$ и найти дискретный логарифм:
$$h = g^{\frac{x_0 - x_0'}{x_1' - x_1}}$$
Это полностью взламывает исходное допущение. Если же $x_1' = x_1$, то и $x_0$ обязано быть равным $x_0'$, что противоречит условию коллизии. Профессор подчеркнула, что изоморфизм криптографических групп циклической группе — это теоретико-информационное свойство, но эффективный переход между ними вычислительно невозможно осуществить, что и гарантирует безопасность.
🌳 Дерево Меркла: переход к произвольной длине и локальному открытию 32:54
Чтобы превратить ограниченный базовый хеш в полноценную функцию, способную обрабатывать строки произвольной длины и поддерживать локальное открытие, применяется универсальная конструкция дерева Меркла (Merkle Hash). По словам лектора, эта идея Ральфа Меркла поразительно красива, умна и проста.
Процедура вычисления хеша (Eval) для длинного сообщения $x$ разбивается на этапы:
- Дополнение (Padding): К исходному сообщению $x$ принудительно добавляется бит
1и минимально необходимое количество нулей, чтобы общая длина стала ближайшей степенью двойки $2^L$. Добавление единицы критически важно, иначе верификатор не сможет отличить полезные данные от технического дополнения. - Построение дерева: Полученные данные делятся на блоки размером по $\lambda$ бит. Соседние блоки попарно хешируются с помощью базовой функции
Eval. Этот процесс повторяется иерархически уровень за уровнем, формируя бинарное дерево, пока не останется одно финальное значение — корень дерева (root).
Профессор обратила особое внимание на то, что результатом работы функции является не только сам корень root, но и зафиксированная глубина дерева (depth).
Выдача глубины дерева обязательна. Если этого не делать, злоумышленник сможет тривиально находить коллизии для сообщений разной длины.
Атака без учета глубины выглядит просто: атакующий берет длинную строку, честно вычисляет дерево, а затем может заявить в качестве открытых данных блоки с любого промежуточного уровня дерева, ведь все они в итоге сворачиваются в один и тот же корень. Включение глубины в состав хеш-значения полностью блокирует эту уязвимость. Профессор уточнила, что для строгого соблюдения ограничений размера можно принять максимальную длину входа равной $2^\lambda$ бит, чего с избытком хватает для любых практических нужд.
🔍 Локальное открытие и защита от обмана 50:30
Главным преимуществом дерева Меркла является возможность подтвердить значение отдельного бита (или блока данных), не раскрывая все сообщение целиком.
Процесс локального открытия устроен следующим образом:
- Определяется целевой блок данных размером в $\lambda$ бит, содержащий нужный бит.
- Доказывающий формирует доказательство, куда включает сам блок и «соседние» блоки (siblings) с каждого уровня дерева, необходимые для последовательного перевычисления хешей на пути к корню.
- Для дерева глубиной $L$ объем переданных данных составляет порядка $L \cdot \lambda$ бит (например, $\lambda^2$), что укладывается в полиномиальные ограничения сложности.
Верификатор, получив целевой блок и набор соседних блоков, поочередно восстанавливает значения родительских узлов снизу вверх. Финальный вычисленный хеш сверяется с ранее опубликованным корнем дерева root. Если они совпадают, верификатор принимает доказательство с вероятностью 1.
Студенты выразили обоснованное сомнение: что если нечестный доказывающий при разных запросах верификатора начнет подменять соседние блоки, пытаясь скомбинировать их так, чтобы каждый раз успешно приходить к корню?
Профессор успокоила аудиторию, пояснив, что злоумышленник может действовать как угодно изощренно, однако единственное, что требуется доказать — это коллизионная стойкость конструкции. Если бы обманщик мог предоставить два разных корректных пути локального открытия для одного и того же корня (с разными значениями целевого блока), это неизбежно означало бы существование коллизии на каком-то из промежуточных уровней дерева. А поскольку базовое хеширование из $2\lambda$ в $\lambda$ бит математически защищено от коллизий через задачу дискретного логарифма, такой обман вычислительно невозможно реализовать. Подробное математическое доказательство этого тезиса лектор пообещала разобрать на следующем занятии.
