Список обозначений

Протокол привязки к биту

bit commitment protocol

Говоря неформально, протоколом привязки к биту называется криптографический протокол с двумя участникам (отправителем и получателем), посредством которого отправитель передает произвольный бит $b$ получателю следующим образом. Вначале выполняется этап привязки, на котором отправитель передает получателю (вообще говоря, интерактивно) информацию о $b$, называемую блобом, но не само значение $b$. Затем на этапе раскрытия отправитель передает получателю значение $b$ и доказывает ему, что это значение действительно соответствует блобу, полученному на этапе привязки. Этот процесс называется раскрытием блоба в значение $b$. Протокол привязки к биту должен удовлетворять следующим условиям.

  1. Получатель до этапа раскрытия не может узнать по блобу значение передаваемого бита. Это условие называется условием конфиденциальности.
  2. Отправитель на этапе раскрытия не может успешно доказать отправителю, что один и тот же блоб соответствует как $0$, так и $1$. Другими словами, отправитель не может раскрыть один и тот же блоб как в $0$, так и в $1$. Это условие называется условием однозначности.

Протоколы привязки к битам используются для построения большого числа криптографических протоколов. В частности, к таким относятся протоколы доказательства с вычислительно нулевым разглашением и аргументы с абсолютно нулевым разглашением для языков из класса $\mathrm{NP}$.

Неформальный смысл протоколов привязки к биту можно проиллюстрировать с помощью следующего «протокола» из реальной жизни. На этапе привязки отправитель записывает значение бита $b$ на листе бумаги, помещает этот лист в сейф и передает этот сейф (без ключа от него) получателю. В данном случае роль блоба играет сейф с находящимся в нем значением $b$. На этапе раскрытия отправитель передает получателю значение $b$ и ключ от сейфа. Получатель открывает сейф с помощью полученного ключа и признает полученное значение $b$ соответствующим блобу, если и только если оно совпадает со значением, записанным на листе бумаги из сейфа.

Перейдем к формальным определениям. Моделью протокола привязки к биту является пара $(\mathcal S,\mathcal R)$ интерактивных полиномиальных вероятностных алгоритмов, где $\mathcal S$ моделирует честного отправителя, а $\mathcal R$ — честного получателя. Общим входом $\mathcal S$ и $\mathcal R$ является $1^n$, где $n\in\mathbb N$ — параметр стойкости. Кроме того, алгоритму $\mathcal S$ подается на вход бит $b$.

Не ограничивая общности, можно считать, что на этапе раскрытия отправитель передает получателю значения бита $b$ и случайной двоичной строки $s$, использованной отправителем на этапе привязки. Тогда проверка получателем соответствия бита $b$ блобу заключается в проверке совпадения последовательности сообщений, полученных им на этапе привязки, с $\operatorname{mess}^{\mathcal S(b;s)}_{\mathcal R(;r)}(1^n)$, где $r$ — значение случайной строки, использованной получателем на этапе привязки. Такой этап раскрытия называется каноническим. Приведенное выше соображение показывает, что для задания протокола привязки к биту достаточно описать действия отправителя и получателя лишь на этапе привязки. Руководствуясь этим соображением, мы считаем, что алгоритмы $\mathcal S$ и $\mathcal R$ выполняют только этап привязки протокола привязки к биту.

Неформальные условия конфиденциальности и однозначности могут быть формализованы несколькими способами. Минимальным требованием к протоколу привязки к биту является выполнение для него следующих условий вычислительной конфиденциальности и вычислительной однозначности.

Определение 1 вычислительная конфиденциальность; см. также [1]
Протокол $(\mathcal S,\mathcal R)$ привязки к биту удовлетворяет условию вычислительной конфиденциальности, если для любого интерактивного полиномиального вероятностного алгоритма $\mathcal R’$ семейства случайных величин \[ \left(\left.\operatorname{view}^{\mathcal S(0)}_{\mathcal R'}(1^n)\,\right|\,n\in\mathbb N\right)\quad\text{и}\quad \left(\left.\operatorname{view}^{\mathcal S(1)}_{\mathcal R'}(1^n)\,\right|\,n\in\mathbb N\right) \] вычислительно неотличимы.
Определение 2 вычислительная однозначность; см. также [1]
Протокол $(\mathcal S,\mathcal R)$ привязки к биту удовлетворяет условию вычислительной однозначности, если для любого интерактивного полиномиального вероятностного алгоритма $\mathcal S’$, любого полиномиального вероятностного алгоритма $\mathcal A$ и любого полинома $p$ величина \begin{align*} &\Pr_r\left(\vphantom{\frac1{p(n)}}\Pr\left(\mathcal A\left(1^n,\operatorname{view}^{\mathcal R(;r)}_{\mathcal S’(;s)}(1^n)\right)=(s_0,s_1),\right.\right.\\ &\qquad\qquad\left.\left.\operatorname{mess}^{\mathcal S’(;s)}_{\mathcal R(;r)}(1^n)=\operatorname{mess}^{\mathcal S(0;s_0)}_{\mathcal R(;r)}(1^n)=\operatorname{mess}^{\mathcal S(1;s_1)}_{\mathcal R(;r)}(1^n)\right)\geqslant\frac1{p(n)}\right) \end{align*} пренебрежимо мала как функция от $n\in\mathbb N$. Здесь внешняя вероятность берется по случайной строке $r$ алгоритма $\mathcal R$, а внутренняя — по случайной строке $s$ алгоритма $\mathcal S’$ и случайной строке алгоритма $\mathcal A$ при фиксированном значении $r$.
Определение 3 протокол привязки к биту
Протоколом привязки к биту называется пара $(\mathcal S,\mathcal R)$ алгоритмов вышеуказанного вида, удовлетворяющая условиям вычислительной конфиденциальности и вычислительной однозначности.

В определениях 1 и 2 алгоритмы $\mathcal S’$ и $\mathcal R’$ являются моделями соответственно нечестного отправителя и нечестного получателя, а алгоритм $\mathcal A$ должен по значению $\operatorname{view}^{\mathcal R}_{\mathcal S’}(1^n)$ (при известном параметре стойкости) найти пару строк, позволяющих нечестному отправителю раскрыть блоб как в $0$, так и в $1$.

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

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна