Список обозначений
Условие абсолютной однозначности для протокола привязки к биту
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$ — бит, к которому должен «привязаться» отправитель).
- Получатель выбирает $r\in_{\mathfrak U}\{0,1\}^{3n}$ и посылает строку $r$ отправителю.
- Получив строку $r\in\{0,1\}^{3n}$ от получателя, отправитель выбирает $s\in_{\mathfrak U}\{0,1\}^n$, вычисляет $g(s)$ и посылает получателю строку $g(s)$, если $b=0$, и строку $g(s)\oplus r$, если $b=1$.
Литература
- [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