МЕНЮ

Каталог

ПРОТОКОЛ ПОДБРАСЫВАНИЯ МОНЕТЫ С ПОМОЩЬЮ ОДНОНАПРАВЛЕННОЙ ФУНКЦИИ Протокол CFOWF
Примитивный протокол Протокол подбрасывания монеты по телефону

 

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

Пусть A (Alice) и B (Bob) находятся на удалении друг от друга, и они не доверяют друг другу. Они хотят подбросить монетку по телефону.
Описание протокола

Пусть $ A$ (Alice) и $ B$ (Bob) находятся на удалении друг от друга, и они не доверяют друг другу. Они хотят подбросить монетку по телефону. 

1) $ A$ и $ B$ договариваются об однонаправленной функции $ f$, определенной на множестве целых чисел. 

2) $ A$ выбирает большое случайное целое число $ x$, вычисляет $ y=f(x)$ и отправляет $ y$ $ B$ (сообщает его $ B$ по телефону). 

3) $ B$ сообщает $ A$ свое предположение о числе $ x$: четное оно или нечетное. 

4) $ A$ сообщает $ B$ о том, что его предположение правильно или нет, и называет ему число$ x$. 

5) $ B$ проверяет, что $ y=f(x)$.

 

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

 
Ссылки
  1. M.Blum, "Coin flipping by telephone -- A protocol for solving impossible problems," ACM SIGACT News, vol. 15, no. 1, pp. 23-27, Dec. 1983.