МЕНЮ

Определения

Протоколы привязки к биту Протоколы BCP
Примитивные протоколы
Термин

Протокол привязки к биту (bit commitment protocol) – криптографический протокол с двумя участниками (отправителем (sender) и получателем (receiver)), посредством которого отправитель передает получателю бит информации (битовое обязательство) таким образом, что выполняются два условия: 1) после передачи бита получателю (так называемого этапа привязки (commit phase)) отправитель уже не может изменить его значение; 2) получатель не может самостоятельно определить значение бита и узнает его только после выполнения отправителем так называемого этапа раскрытия (reveal phase).
Определение

Протоколом (схемой) привязки к биту называется пара вероятностных полиномиальных интерактивных машин, обозначаемая $ (S,R)$ (отправитель и получатель), удовлетворяющих следующим условиям:

- Входные требования: Общим входом является целое число $ n$ в унарном представлении, т.е. $ 1^n$, служащее параметром стойкости. Конфиденциальным входом отправителя является бит, обозначаемый $ \upsilon$.

- Конфиденциальность (secrecy) или сокрытие (hiding): Получатель (даже при произвольном отклонении от протокола) не может отличить привязку к 0 от привязки к $ 1$. Т.е для любой вероятностной полиномиальной машины $ R^*$, взаимодействующей с $ S$, ансамбли, описывающие выходы $ R^*$ в двух случаях $ \{\langle S(0),R^* \rangle (1^n)\}_{n\in N}$ и$ \{\langle S(1),R^* \rangle (1^n)\}_{n\in N}$ вычислительно неотличимы.

- Однозначность (unambiguity) или привязка (binding): Предварительные требования:

1) Представление получателя взаимодействия с отправителем, обозначаемое $ (r,\overline{m})$, состоит из случайного бита $ r$, использованного получателем, и последовательности сообщений $ \overline{m}$, полученных от отправителеля.

2) Пусть $ \sigma\in\{0,1\}$. Мы говорим, что представление получателя (такого взаимодействия)$ (r,\overline{m})$ является возможной $ \sigma$-привязкой, если существует строка $ s$ такая, что $ \overline{m}$описывает сообщения, полученные $ R$, когда $ R$ использует локальный бит $ r$ и взаимодействует с машиной $ S$, которая использует локальный бит $ s$ и имеет вход $ (\sigma,1^n)$.

3) Мы говорим, что что представление получателя $ (r,\overline{m})$ является неоднозначным, если оно является возможной 0-привязкой и возможной $ 1$-привязкой.

Требование однозначности утверждает, что для всех, кроме незначительной доли, случайных битов получателя не сущесвует последовательности сообщений от отправителя которая бы вместе с этими случайными битами формировала неоднозачное представление получателя. Т.е. для всех, кроме незначительной доли, $ r \in \{0,1\}^{poly(n)}$ не существует $ \overline{m}$такой, что $ (r,\overline{m})$ неоднозначно.
Ссылки
  • Погорелов Б.А., Сачков В.Н.(ред.) Словарь криптографических терминов. - М.: Издательство МЦНМО, 2006. - 94c.
  • O.Goldreich Foundations of cryptography. Basic tools. Cambridge University Press, 2004 - P.223-225.
  • Варновский Н.П. Курс лекций по математической криптографии. - 2009 - С.71-72.
  • Bruse Schneier, Applied Cryptography, Second edition: Protocols, Algorthms and Source Code in C, Wiley Computer Publishing, John Wiley & Sons, Inc.,1996,666p.
  • M.Naor Bit Commitment Using Pseudo-Randomness (Extended Abstract). Advances in Cryptology - CRYPT0‘89, LNCS 435, pp. 128-136, 1990.