Ментальный покер

Ментальный покер — система криптографических задач, касающихся честных игр на расстоянии (через телефонную связь или Интернет). Термин происходит от названия карточной игры покер. С аналогичной проблемой связана задача подбрасывания монеты на расстоянии.

История

Поскольку с середины XX века многие сделки, денежные операции стали совершаться в удалённом режиме, появилась необходимость в создании криптографического протокола, способного решать такие задачи. Такой протокол должен был обеспечить не только удобство для пользователя, но и надёжность. Подобную задачу можно сформулировать в игровой форме, опуская некоторые технические детали — таким образом появился термин «ментальный покер».

Впервые в покер без карт пытались сыграть Нильс Бор, его сын и друзья в 1933 году, но попытка оказалась безуспешной. Позже проблемой занялся Роберт Флойд. Его исследования подтолкнули создателей протокола RSA-шифрования Ади Шамира, Рона Ривеста и Лена Адлемана к публикации научного доклада, в котором были предложены протоколы, позволяющие решить проблему ментального покера.

Формулировка задачи

Шамир, Ривест и Адлеман сформулировали задачу так: «Могут ли два нечестных друг к другу игрока сыграть в честный покер без использования карт, а, например, по телефону?»

В покере это звучит так: «Как мы можем убедиться, что ни один игрок не подглядывает в карты других игроков, пока мы перетасовываем колоду?». В реальной карточной игре ответить на такой вопрос просто, так как игроки сидят напротив и наблюдают друг за другом (рассматриваем случай, когда исключена возможность обычного мошенничества). Однако если игроки сидят не рядом, а в отдельных комнатах, и могут передавать колоду друг другу целиком (например, с помощью почты), задача становится весьма трудной. Для электронных карточных игр, таких как онлайн-покер, где сам процесс игры скрыт от пользователя, решить проблему и вовсе невозможно, если используемый метод позволяет одному игроку обманывать другого.

Игра должна удовлетворять определенным требованиям:

1. Игрок не знает даже частичной информации о картах своего противника.
2. Все возможные исходы равновероятны для обоих игроков.
3. В конце игры игрок может удостовериться, что игра была честной и обмана не произошло.

Перетасовки карт, использующие коммутативное шифрование

Одним из возможных алгоритмов перетасовки карт является использование коммутативной схемы шифрования. Коммутативная схема означает, что если некоторые данные зашифровывают более чем один раз, порядок, в котором их расшифровывают, не имеет значения.

Пример: Алиса шифрует открытый текст, создавая искаженный шифротекст, который она передает Бобу. Боб шифрует шифротекст снова, используя ту же схему, что и Алиса, но с другим ключом. Если схема шифрования является коммутативной, при расшифровке сообщения не будет иметь значения, кто расшифровывает первым.

Функция шифрования, как и в RSA, должна быть односторонней — зная x, легко можно вычислить f(x), но в обратном направлении для вычисления необходимо знать «секрет». Криптостойкость протокола основана на сложности обращения таких функций. Однако это не исключает возможность частичного вычисления x из f(x).

Алгоритм

Алгоритм перетасовки карт с использованием коммутативного шифрования выглядит следующим образом:

1. Алиса и Боб соглашаются использовать определенную «колоду» карт. На практике это означает, что они согласны использовать множество чисел или других данных таких, что каждый элемент множества представляет собой карту.
2. Алиса шифрует каждую карту колоды, используя ключ А.
3. Алиса тасует карты.
4. Алиса передает зашифрованную и перемешанную колоду Бобу. Он не знает, где какие карты.
5. Боб выбирает шифрование ключа B и использует его для шифрования каждой карты из уже зашифрованной и перетасованной колоды.
6. Боб тасует колоду.
7. Боб передает дважды зашифрованную и перетасованную колоду обратно Алисе.
8. Алиса расшифровывает каждую карту, используя её ключ А. Но шифрование Боба все ещё остается, то есть она не знает, где какие карты.
9. Алиса выбирает ключ шифрования каждой карты (А1, А2 и т. д.) и шифрует их по отдельности.
10. Алиса передает колоду Бобу.
11. Боб расшифровывает каждую карту, используя его ключ В. Индивидуальное шифрование Алисы все ещё остается, то есть он не знает, где какие карты.
12. Боб выбирает ключ для шифрования каждой карты (B1, B2 и т. д.) и шифрует их по отдельности.
13. Боб передает колоду обратно Алисе.
14. Алиса показывает колоду всем игрокам (в данном случае игроки — Алиса и Боб).

Теперь колода перемешана.

Во время игры Алиса и Боб будут забирать карты из колоды, для которых известен порядок в перемешанной колоде. Когда кто-либо из игроков захочет увидеть свои карты, он будет запрашивать соответствующие ключи от другого игрока. Этот игрок (после проверки того, что игрок действительно имеет право смотреть на карты) передает индивидуальные ключи для этих карт другому игроку. Также необходимо проверить, что игрок не пытался запросить ключ к картам, которые ему не принадлежат.

Пример

Алиса и Боб раздают три карты $a,b,c$. Далее используется алгоритм:

1) Они выбирают простое число $p=23$, Алиса выбирает простое число $c_{1}=7$, взаимно простое с $p-1$, и вычисляет число $d_{1}$ по обобщенному алгоритму Евклида, то есть: $(c_{1}*d_{1})\mod (p-1)=1$ , отсюда $d_{1}=19$.

2) Аналогично Боб определяет свою пару чисел: $c_{2}=9$ и $d_{2}=5$.

3) Далее Алиса выбирает три различных числа в промежутке $[1,p-1]$ , например $a_{0}=2,b_{0}=5,c_{0}=3$ , и ставит их в соответствие своим картам. Она передает их Бобу в открытом виде.

4) Затем Алиса вычисляет числа: $u_{1}=2^{7}\mod 23=13;u_{2}=5^{7}\mod 23=17;u_{3}=3^{7}\mod 23=2;$, перемешивает их и посылает Бобу.

5) Пусть Боб выбирает любое число, например $17$, пересылает Алисе, и это число — её карта (в данном случае $b$).

6) Теперь Боб вычисляет: $v_{1}=13^{9}\mod 23=3;v_{2}=2^{9}\mod 23=6$ .

7) Он посылает числа Алисе, она выбирает, например, $3$ и вычисляет $w_{1}=3^{19}\mod 23=6$ .

8) Алиса отправляет число Бобу, он вычисляет $z=6^{5}\mod 23=2$ , таким образом он получает свою карту $a_{0}$, то есть карта $a$. Карта $c$ остается в прикупе, при этом Алиса и Боб об этом не знают.

Недостатки

Данный алгоритм имеет недостатки. При шифровании данных некоторые свойства этих данных могут быть сохранены из открытого текста в шифротекст. Это может быть использовано для пометок определенных карт. Таким образом, стороны должны договориться об использовании колоды, где нет карт со свойствами, которые сохраняются во время шифрования.

Кроме того, используемая схема шифрования должна быть защищена от атак на основе открытого текста: Боб не может определить первоначальный ключ Алисы.

Инструментарий для ментальных карточных игр

Описание сложных протоколов для выполнения и проверки большого количества операций с картами и колодами карт приводится в статье Кристиана Шиндельхауэра. Данная работа связана с операциями «общего назначения» (перетасовка, вставка карты в колоду), которые создают протоколы, применимые к любой карточной игре.

Библиотека libtmcg (C++) обеспечивает реализацию инструментария  (неопр.). Шиндельхауэра. Она была использована для реализации немецкой карточной игры скат. В этой игре 3 игрока и колода из 32 карт, поэтому вычислений значительно меньше, чем в покере, в котором от пяти до восьми игроков и используется полная колода из 52 карт.

Протокол «покер без перетасовки»

На сегодняшний день алгоритм ментального покера, основанный на стандартном протоколе «Алиса-Боб», не может обеспечить высокую производительность в онлайн-играх. Требование, что каждый игрок шифрует каждую карту по отдельности, накладывает существенные ограничения. Статья Голле описывает протокол ментального покера, при котором достигается наибольшая эффективность за счет использования свойств игры в покер и ухода от модели «зашифровать-перемешать». Вместо перетасовки карт игроки генерируют (в зашифрованном виде) случайные числа, которые используются для выбора следующей карты. Каждую новую карту необходимо сравнить с остальными, которые уже были розданы, для обнаружения дубликатов. Таким образом, этот метод наиболее эффективен в играх типа «покер», в которых количество карт, раздаваемых игрокам, очень мало по сравнению с размером всей колоды.

Алгоритм генерации карт требует организовать криптосистему с двумя ключевыми свойствами. Шифрование Е должно быть аддитивно гомоморфным, то есть таким что: E(c₁)E(c₂) = E(c₁ + c₂). Во-вторых, коллизии должны быть обнаружены без раскрытия открытого текста. Другими словами, задавая E(c₁) и E(c₂), мы можем определить, выполняется ли равенство c₁ и c₂. Одним из примеров системы с такими свойствами является схема шифрования Эль-Гамаля.

Алгоритм работает следующим образом:

1. Игроки создают пустой список L, который фиксирует используемые карты.
2. Чтобы взять карту, каждый игрок вычисляет случайное число r_i в {0, …, 51}, вычисляет E(r_i) и публикует схему обязательства E(r_i).
3. Затем игроки показывают их значение E(r_i) и можно убедиться, что каждый игрок честен с остальными.
4. Игроки вычисляют значение $\Pi E(r_{i})=E(\Sigma r_{i})$, которое образует новую зашифрованную карту E(r*) : $r*=\Sigma r_{i}$
5. Игроки проверяют, есть ли E(r*) в L. Если нет, E(r*) раздается соответствующим игроком и добавляется к L. Когда карты раскрыты, они могут быть совместно расшифрованы.

Таким образом, игроки должны только определить способ шифрования карт, который используется в игре, а также некоторые ограничения на коллизии, которые так же малы, как и количество необходимых карт.

См. также

• Доказательство с нулевым разглашением
• Электронные деньги

Литература

• Goldwasser S., Micali S. Probabilistic encryption & how to play mental poker keeping secret all partial information (англ.) // STOC'82: Proceedings of the fourteenth annual ACM symposium on Theory of computing — New York City: ACM, 1982. — P. 365—377. — ISBN 978-0-89791-070-5 — doi:10.1145/800070.802212
• Ади Шамир, Рональд Л. Райвест, Леонард М. Адельман. Покер без карт // Математический цветник = The Mathematical Gardner / Составитель и редактор Дэвид А. Кларнер. Перевод с английского Ю. А. Данилова под редакцией И. М. Яглома. — М.: Мир, 1983. — С. 58—66.
• Fortune S., Merritt M. Poker Protocols (англ.) // Advances in Cryptology — CRYPTO ’84: 4th Annual International Cryptology Conference, Santa Barbara, 1984, Proceedings / R. B. J. George, D. Chaum — New York City: Springer-Verlag New York, 1985. — P. 456—466. — 491 p. — (Lecture Notes in Computer Science; Vol. 196) — ISBN 978-0-387-15658-3 — ISSN 0302-9743; 1611-3349 — doi:10.1007/3-540-39568-7_36
• Adi Shamir, Ronald L. Rivest and Leonard M. Adleman. Mental Poker // Mathematical recreations: a collections in honor of Martin Gardner (англ.) / edited by David A. Klarner. — 2nd ed. — Dover Publications, 1998. — P. 37—43. — ISBN 0-486-40089-1.
• Golle P. Dealing cards in poker games (англ.) // International Conference on Information Technology: Coding and Computing (ITCC'05) — IEEE, 2005. — Vol. 1. — P. 506—511. — ISBN 978-0-7695-2315-6 — doi:10.1109/ITCC.2005.119
• Рябко Б. Я., Фионов А. Н. Основы современной криптографии для специалистов в информационных технологиях — Научный мир, 2004. — 173 с. — ISBN 978-5-89176-233-6
• Schindelhauer C. A Toolbox for Mental Card Games (англ.). — Medizinische Universitat Lubeck, 1998.
• Stamer H. Efficient Electronic Gambling: An Extended Implementation of the Toolbox for Mental Card Games (англ.). — WEWoRC, 2005.