Введение

Криптографическая схема, позволяющая зафиксировать выбранное значение

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

этап фиксации, в течение которого выбирается и фиксируется значение;
этап раскрытия, в течение которого отправитель раскрывает значение, а затем получатель проверяет его подлинность.

В вышеупомянутой метафоре этап фиксации – это помещение сообщения отправителем в ящик и его запирание. Этап раскрытия – это передача ключа отправителем получателю, который использует его для открытия ящика и проверки содержимого. Запертый ящик – это фиксация (коммитмент), а ключ – доказательство. В простых протоколах этап фиксации состоит из одного сообщения от отправителя к получателю. Это сообщение называется фиксацией (коммитментом). Важно, чтобы конкретное выбранное значение не могло быть извлечено из сообщения получателем на данном этапе (это называется свойством скрытности). Простой этап раскрытия состоит из одного сообщения – открытия – от отправителя к получателю, за которым следует проверка, выполняемая получателем. Значение, выбранное на этапе фиксации, должно быть единственным, которое отправитель может вычислить и которое будет подтверждено на этапе раскрытия (это называется свойством обязываемости). Концепция схем фиксации, возможно, была впервые формализована Жилем Брассаром, Дэвидом Шомом и Клодом Крепо в 1988 году в рамках различных протоколов доказательства с нулевым разглашением для NP, основанных на различных типах схем фиксации. Однако эта концепция использовалась и ранее, без формального описания. Понятие фиксации впервые появилось в работах Мануэля Блума, Шимона Эвена и Ади Шамира и др. Терминология, по-видимому, была предложена Блюмом. Во-вторых, фиксации также используются в доказательствах с нулевым разглашением проверяющим, который часто заранее фиксирует свой выбор. Это позволяет составлять доказательства с нулевым разглашением параллельно, не раскрывая дополнительной информации проверяемому.

Системы подписей

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

Поддающиеся проверке секреты

Еще одно важное применение обязательств – в проверяемом разделении секрета, критически важном элементе безопасных многосторонних вычислений. В схеме разделения секрета каждый из нескольких участников получает "доли" значения, которое должно быть скрыто от всех. Если достаточное количество участников объединится, их доли можно использовать для восстановления секрета, но даже злоумышленнический сговор недостаточного размера не должен узнать ничего. Разделение секрета лежит в основе многих протоколов для безопасных вычислений: для безопасного вычисления функции от общего входного значения манипулируют секретными долями. Однако, если доли должны генерироваться злоумышленниками, может быть важно проверять их корректность. В схеме проверяемого разделения секрета распространение секрета сопровождается обязательствами по отдельным долям. Эти обязательства не раскрывают никакой информации, которая могла бы помочь нечестному сговору, но доли позволяют каждому участнику проверить, верна ли его доля.

Определение ценной бумаги

Формальные определения схем коммитов сильно различаются по обозначениям и подходу. Один из аспектов различий заключается в том, обеспечивает ли схема коммитов идеальную или вычислительную безопасность в отношении свойств скрытности или связности. Другой аспект – интерактивность коммита, то есть рассматриваются ли фазы коммита и раскрытия как выполняемые криптографическим протоколом, или они неинтерактивны и состоят из двух алгоритмов: Commit и CheckReveal. В последнем случае CheckReveal часто можно рассматривать как дерандомизированную версию Commit, где случайность, используемая Commit, является информацией для раскрытия. Если коммит C к значению x вычисляется как C:=Commit(x, open), где open – это случайность, используемая для вычисления коммита, то CheckReveal(C, x, open) сводится к простой проверке уравнения C=Commit(x, open). Используя эти обозначения и знания о математических функциях и теории вероятностей, мы формализуем различные версии свойств связности и скрытности коммитов. Две наиболее важные комбинации этих свойств – схемы коммитов с идеальной связностью и вычислительной скрытностью, а также схемы коммитов с вычислительной связностью и идеальной скрытностью. Важно отметить, что ни одна схема коммитов не может одновременно быть идеально связной и идеально скрытной: вычислительно неограниченный противник может просто генерировать Commit(x, open) для каждого значения x и open, пока не найдет пару, которая выдаст C, и в идеально связной схеме это однозначно определит x.

Вычислительная связь

Пусть open выбирается из множества размера , то есть может быть представлено как k-битная строка, и пусть — соответствующая схема коммитов. Поскольку размер k определяет безопасность схемы коммитов, он называется параметром безопасности. Тогда для всех неравномерных вероятностных полиномиальных алгоритмов, выводящих и возрастающей длины k, вероятность того, что и является пренебрежимо малой функцией от k. Это форма асимптотического анализа. Также возможно сформулировать то же требование, используя конкретный уровень безопасности: схема коммитов Commit является безопасной, если для всех алгоритмов, работающих за время t и выводящих , вероятность того, что и не превышает .

Совершенное, статистическое и вычислительное сокрытие

Пусть $\mathcal{U}$ будет равномерным распределением по множеству начальных значений для параметра безопасности $k$. Схема коммитов является абсолютно скрывающей, статистически скрывающей или вычислительно скрывающей, если для всех ансамблей вероятностей $\mathcal{P}$ и $\mathcal{Q}$ вероятности этих ансамблей равны, статистически близки или вычислительно неотличимы.

Строительство

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

Битовое обязательство в модели случайного оракула

Схемы фиксации битов тривиально построить в модели случайного оракула. При наличии хеш-функции H с 3k-битным выходом, для фиксации k-битного сообщения m, Алиса генерирует случайную k-битную строку R и отправляет Бобу H(R||m). Вероятность того, что существуют R′, m′, где m′ ≠ m, такие что H(R′||m′) = H(R||m) составляет ≈ 2−k, но для проверки любой гипотезы о сообщении m Бобу потребуется сделать 2k (для неверной гипотезы) или 2k+1 (в среднем, для верной гипотезы) запросов к случайному оракулу. Отмечаем, что более ранние схемы, основанные на хеш-функциях, по сути, можно рассматривать как схемы, основанные на идеализации этих хеш-функций как случайных оракулов.

Битовое обязательство от любой односторонней пермутации

Можно создать схему фиксации бита на основе любой инъективной односторонней функции. Схема опирается на тот факт, что любую одностороннюю функцию можно модифицировать (с помощью теоремы Голдрейха — Левина) так, чтобы она обладала вычислительно сложным ядром (сохраняя при этом инъективность). Пусть f — инъективная односторонняя функция, а h — ядро со сложной вычислительной задачей. Тогда, чтобы зафиксировать бит b, Алиса выбирает случайный вход x и отправляет Бобу тройку

, где обозначает XOR, то есть побитовое сложение по модулю 2. Чтобы раскрыть фиксацию, Алиса просто отправляет x Бобу. Боб проверяет, вычисляя f(x) и сравнивая результат с зафиксированным значением. Эта схема скрывающая, поскольку для восстановления b Бобу необходимо восстановить h(x). Поскольку h является вычислительно сложным ядром, восстановление h(x) из f(x) с вероятностью, превышающей половину, столь же сложно, как и инверсия f. Идеальная связываемость следует из того факта, что f инъективна и, следовательно, f(x) имеет ровно один прообраз.

Обязательства, основанные на физических не клонируемых функциях

Физические неклонируемые функции (PUF) основаны на использовании физического ключа с внутренней случайностью, который сложно клонировать или имитировать. Электронные, оптические и другие типы ППУ широко обсуждались в литературе в связи с их потенциальными криптографическими приложениями, включая протоколы фиксации обязательств.