Каталог

ПРОТОКОЛ ПРИВЯЗКИ К БИТУ НА ОСНОВЕ ПСЕВДОСЛУЧАЙНОГО ГЕНЕРАТОРА Протокол BCPRG
Примитивный протокол Протокол привязки к биту

 

Постановка задачи

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

Описание протокола

Пусть $ :\{0,1\}^*\rightarrow\{0,1\}^*$ - псевдослучайный генератор такой, что для всех . 

Общий вход: целое число $ n$ в унарном представлении, т.е. $ 1^n$, служащее параметром стойкости. 

Дополнительный вход отправителя: $ \upsilon \in \{0,1\}$ 

1) Этап привязки. 
a) Получатель $ R$ наугад равномерно выбирает $ r\in\{0,1\}^3n$ и отправляет $ r$ отправителю $ S$
b) Отправитель $ S$ наугад равномерно выбирает $ s\in\{0,1\}^n$ и отправляет $ G(s)$, если$ \upsilon=0$, и $ G(s)\oplus r$ в противном случае. 

2) Этап раскрытия. Отправитель $ S$ раскрывает строку $ s$. Получатель $ R$ принимает значение 0, если $ G(s)=\alpha$, и принимает значение $ 1$, если $ G(s)\oplus r=\alpha$, где $ (r,\alpha)$ - представление получателя $ R$ этапа привязки.

 

Основные сведения

 

Ссылки
  • M.Naor Bit Commitment Using Pseudo-Randomness (Extended Abstract). Advances in Cryptology - CRYPT0‘89, LNCS 435, pp. 128-136, 1990.
  • O.Goldreich Foundations of cryptography. Basic tools. Cambridge University Press, 2004. - P.226-227.
  • Bruse Schneier, Applied Cryptography, Second edition: Protocols, Algorthms and Source Code in C, Wiley Computer Publishing, John Wiley & Sons, Inc.,1996,666p.