МЕНЮ

Определения

Протоколы подбрасывания монеты по телефону Протоколы CFP
Примитивные протоколы
Термин

Протокол подбрасывания монеты (по телефону) (coin flipping (by telephone) protocol) – криптографический протокол, позволяющий двум не доверяющим друг другу участникам сгенерировать общий случайный равновероятный бит.
Определение

Протоколом подбрасывания монеты называется пара вероятностных полиномиальных интерактивных машин $ (A,B)$, называемых участниками, с входным параметром стойкости $ 1^n$, удовлетворяющих следующим условиям. Участники обмениваются сообщениями за последовательность раундов, где в каждом раунде каждый участник отправляет и получает сообщение. В конце протокола $ A$ и $ B$ вырабатывают выходные биты $ c_1$ и $ c_2$соответственно. Обозначим через $ (c_1 \vert c_2)\leftarrow \langle A(1^n), B(1^n)\rangle$ опыт, при котором $ A$ и $ B$взаимодействуют (используя равномерно выбранные случайные биты), и затем $ A$ выводит $ c_1$, и $ B$ выводит $ c_2$. Требуется, чтобы для любого достаточно большого $ n$ и любой возможной пары $ (c_1,c_2)$, которая может быть выработана $ \langle A(1^n), B(1^n)\rangle$ выполнялось $ c_1 = c_2$ (т.е $ A$ и $ B$ договариваются об общем значении).
Ссылки
  • Погорелов Б.А., Сачков В.Н.(ред.) Словарь криптографических терминов. - М.: Издательство МЦНМО, 2006. - 94c.
  • Tal Moran, Moni Naor, Gil Segev, An Optimally Fair Coin Toss, Cryptology ePrint Archive: Report 2009/214. - 21p. - P.3-4
  • M.Blum, "Coin Flipping by Telephone: A Protocol for Solving Impossible Problems", Proceedings of the 24th IEEE Computer Conference (CompCon), 1982, pp. 133-137.
  • M.Blum, "Coin flipping by telephone -- A protocol for solving impossible problems," ACM SIGACT News, vol. 15, no. 1, pp. 23-27, Dec. 1983.
  • Ященко В.В. (ред.) Введение в криптографию. М.: МЦНМО: «ЧеРо», 1999. - 272 с. 2-е изд., испр.
  • Саломаа А. Криптография с открытым ключом: Пер. с англ. - М.: Мир, 1995. - 318с.,ил. - С.237-238