bit commitment protocol
Говорячи неформально, протоколом прив'язки до біту називається криптографічний протокол з двома учасникам (відправником і отримувачем), за допомогою якого відправник передає довільний біт $ b $ одержувачу наступним чином. Спочатку виконується етап прив'язки. на якому відправник передає одержувачу (взагалі кажучи, інтерактивно) інформацію про $ b $, звану БЛОБ. але не саме значення $ b $. Потім на етапі розкриття відправник передає одержувачу значення $ b $ і доводить йому, що це значення дійсно відповідає БЛОБ, отриманого на етапі прив'язки. Цей процес називається розкриттям БЛОБ в значення $ b $. Протокол прив'язки до біту повинен відповідати таким вимогам.
Протоколи прив'язки до бітам використовуються для побудови великого числа криптографічних протоколів. Зокрема, до таких відносяться протоколи докази з обчислювально нульовим розголошенням і аргументи з абсолютно нульовим розголошенням для мов з класу $ \ mathrm $.
Неформальний сенс протоколів прив'язки до біту можна проілюструвати за допомогою наступного «протоколу» з реального життя. На етапі прив'язки відправник записує значення біта $ 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 ^ _ (1 ^ n) $, де $ r $ - значення випадкової рядки, використаної отримувачем на етапі прив'язки. Такий етап розкриття називається канонічним. Наведене вище міркування показує, що для завдання протоколу прив'язки до біту достатньо описати дії відправника і одержувача лише на етапі прив'язки. Керуючись цим міркуванням, ми вважаємо, що алгоритми $ \ mathcal S $ і $ \ mathcal R $ виконують тільки етап прив'язки протоколу прив'язки до біту.
Неформальні умови конфіденційності та однозначності можуть бути формалізовані декількома способами. Мінімальною вимогою до протоколу прив'язки до біту є виконання для нього таких умов обчислювальної конфіденційності та обчислювальної однозначності.
Визначення 1 обчислювальна конфіденційність; см. також [1]
Протокол $ (\ mathcal S, \ mathcal R) $ прив'язки до біту задовольняє умові обчислювальної конфіденційності. якщо для будь-якого інтерактивного полиномиального імовірнісного алгоритму $ \ mathcal R '$ сімейства випадкових величин \ [\ left (\ left. \ operatorname ^ _ (1 ^ n) \, \ right | \, n \ in \ mathbb N \ right) \ quad \ text \ quad \ left (\ left. \ operatorname ^ _ (1 ^ n) \, \ right | \, n \ in \ mathbb N \ right) \] обчислювально неможливо відрізнити.
Визначення 2 обчислювальна однозначність; см. також [1]
Протокол $ (\ mathcal S, \ mathcal R) $ прив'язки до біту задовольняє умові обчислювальної однозначності. якщо для будь-якого інтерактивного полиномиального імовірнісного алгоритму $ \ mathcal S '$, будь-якого полиномиального імовірнісного алгоритму $ \ mathcal A $ і будь-якого полінома $ p $ величина \ begin \ Pr_r \ left (\ vphantom> \ Pr \ left (\ mathcal A \ left (1 ^ n, \ operatorname ^ _ (1 ^ n) \ right) = (s_0, s_1), \ right. \ Right. \\ \ Qquad \ qquad \ left. \ Left. \ Operatorname ^ _ (1 ^ n) = \ operatorname ^ _ (1 ^ n) = \ operatorname ^ _ (1 ^ n) \ right) \ geqslant \ frac1 \ right) \ end нехтує мала як функція від $ 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 ^ _ (1 ^ n) $ ( при відомому параметрі стійкості) знайти пару рядків, що дозволяють нечесного відправнику розкрити блоб як в $ 0 $, так і в $ 1 $.