МЕНЮ

Каталог

ПРОТОКОЛ ИГРЫ В МЫСЛЕННЫЙ ПОКЕР ГОЛДВАССЕР И МИКАЛИ Протокол MPGM
Протокол игры в мысленный покер

 

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

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

$ 52$ карты представляются шестиразрядными двоичными числами. 

1) $ B$ случайным образом выбирает $ 52$ пары больших простых чисел$ (p_1,q_1), (p_2,q_2), ..., (p_{52},q_{52})$ таких, что $ p_i \equiv q_i \equiv 3 \pmod 4$ для $ 1\leq i \leq 52$, и вычисляет $ 52$ больших составных числа, разложение которых $ B$ знает, т.е. $ N_1 = p_1 \cdot q_1$,$ N_2 = p_2 \cdot q_2$, ..., $ N_{52} = p_{52} \cdot q_{52}$. Затем $ B$ перетасовывает колоду и присваивает числа$ N_1, N_2, ..., N_{52}$ картам перетасованной колоды, $ N_i$ присваивается $ i$-ой карте. $ B$оглашает упорядоченный кортеж $ <N_1, N_2, ..., N_{52}>$. 

2) $ A$ делает то же самое. $ A$ случайным образом выбирает $ 52$ пары больших простых чисел $ (s_1,t_1), (s_2,t_2), ..., (s_{52},t_{52})$ таких, что $ s_i \equiv t_i \equiv 3 \pmod 4$ для $ 1\leq i \leq 52$, и вычисляет $ 52$ больших составных числа, разложение которых $ A$ знает, т.е. $ M_1 = s_1 \cdot t_1$,$ M_2 = s_2 \cdot t_2$, ..., $ M_{52} = s_{52} \cdot t_{52}$. Затем $ A$ перетасовывает колоду и присваивает числа$ M_1, M_2, ..., M_{52}$ картам перетасованной колоды, $ M_i$ присваивается $ i$-ой карте. $ A$оглашает упорядоченный кортеж $ <M_1, M_2, ..., M_{52}>$. 

3) $ B$ оглашает свою полную колоду, зашифрованную следующим образом. Для каждой карты $ C_i$ (с открытым ключом $ N_i$) $ B$ оглашает упорядоченный список $ 6$ чисел из $ A_{N_i}^*$$ (q_1, q_2, ..., q_6)$ таких, что для $ 1 \leq j \leq 6$ $ q_j$ является квадратичным вычетом тогда и только тогда, когда $ j$-ый бит $ C_i$ является $ 1$. 

4) $ A$ оглашает свою колоду точно таким же образом. 

5) $ B$ сдает карту $ A$. Предположим, что $ A$ решил выбрать $ K$-ую карту из колоды $ B$. Повторяем следующую процедуру для каждой карты из зашифрованной колоды $ B$. Рассмотрим $ i$-ую карту, которой соответствует $ N_i$. $ A$ получает случайным образом$ x \in Z_{N_i}^*$ от $ B$. $ A$ вычисляет $ x^2 \pmod {N_i}$ и $ (x/N_i)$. Если $ i=K$, то $ A$ отправляет $ B$ $ x^2 \pmod {N_i}$ и $ (x/N_i)$. В противном случае, $ A$ отправляет $ B$ $ x^2 \pmod {N_i}$ и $ -(x/N_i)$. $ B$ вычисляет квадратный корень из $ x^2 \pmod {N_i}$. Обозначим квадратные корни через $ x$, $ n-x$, $ y$ и $ n-y$. Затем $ B$ отправляет квадратный корень, символ Якоби которого получил от $ A$: $ y$, если $ B$ получил $ -(x/N_i)$ от $ A$, и $ x$, в противном случае. 

6) $ A$ узнает разложение числа и расшифровывает карту $ C_K$. Затем $ A$ должен удалить карту $ C_K$ из своей зашифрованной колоды. $ B$ может видеть какой зашифрованный элемент был удален из колоды $ A$, но это не позволяет $ B$ расшифровать его. 

7) $ A$ сдает карту $ B$. Ясно, что проводится такая же процедура как в 5) и 6), только поменяв ролями $ A$ и $ B$. Теперь $ B$ будет находить разложение одного из чисел$ M_1, M_2, ..., M_{52}$. 

8) Аналогичный протокол происходит, если в течение игры необходимо сдавать больше карт. Когда $ A$ необходима карта, $ A$ будет выбирать карту из колоды $ B$ следуя 5) и 6). Аналогично, когда $ B$ необходима карта, $ B$ будет выбирать карту из колоды $ A$. 

9) После окончания игры вся секретная информация раскрывается для проверки, чтобы каждый мог убедиться в отсутствии мошенничества.

 

Основные сведения
Авторы

Shafrira GoldwasserSilvio Micali

 
Ссылки
  1. Goldwasser S., Micali S. Probabilistic Encryption and How To Play Mental Poker Keeping Secret All Partial Information // Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC '82). - 1982. - P. 365-377.