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

Условие абсолютной однозначности для протокола привязки к биту

perfect unambiguity condition for bit commitment protocol
Определение 1 абсолютная однозначность; см. также [1]
Протокол $(\mathcal S,\mathcal R)$ привязки к биту удовлетворяет условию абсолютной однозначности, если величина \[ \Pr_r\left(\exists\,s_0,s_1 \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) \] пренебрежимо мала как функция от $n\in\mathbb N$. Вероятность здесь берется по случайной строке $r$ алгоритма $\mathcal R$.
Пример 2 см. [2], [3], [1], [4]
Пусть $g$ — псевдослучайный генератор, отображающий $\{0,1\}^n$ в $\{0,1\}^{3n}$ для всех $n\in\mathbb N$. Такие псевдослучайные генераторы существуют тогда и только тогда, когда существуют односторонние функции (см. генератор псевдослучайный). Определим этап привязки протокола привязки к биту следующим образом (через $n$ обозначается параметр стойкости, а через $b$ — бит, к которому должен «привязаться» отправитель).
  1. Получатель выбирает $r\in_{\mathfrak U}\{0,1\}^{3n}$ и посылает строку $r$ отправителю.
  2. Получив строку $r\in\{0,1\}^{3n}$ от получателя, отправитель выбирает $s\in_{\mathfrak U}\{0,1\}^n$, вычисляет $g(s)$ и посылает получателю строку $g(s)$, если $b=0$, и строку $g(s)\oplus r$, если $b=1$.
Условие вычислительной конфиденциальности для этого протокола следует из того, что $g$ — псевдослучайный генератор. Кроме того, вероятность из определения 1 в данном случае равна \[ \Pr_{r\in_{\mathfrak U}\{0,1\}^{3n}}(\exists\,s_0,s_1\in\{0,1\}^n g(s_0)\oplus g(s_1)=r) \] и не превосходит $2^{-n}$, так как $\#\{g(s_0)\oplus g(s_1)\,|\, s_0,s_1\in\{0,1\}^n\}\leqslant2^{2n}$. Таким образом, построенный протокол является протоколом привязки к биту, удовлетворяющим условию абсолютной однозначности. В частности, протоколы привязки к биту, удовлетворяющие условию абсолютной однозначности, существуют в предположении существования произвольных односторонних функций.

Литература

  • [1] Goldreich, O. «Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications)» 2001 (v. 1), 2004 (v. 2)
  • [2] Naor, M. «Bit commitment using pseudo-randomness» 1989
  • [3] Naor, M. «Bit commitment using pseudorandomness» 1991
  • [4] Luby, M. «Pseudorandomness and cryptographic applications» 1996

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