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

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (April 2019) (Learn how and when to remove this message)

Ментальный покер — это общее название для набора криптографических проблем, которые касаются честной игры на расстоянии без необходимости в доверенной третьей стороне . Этот термин также применяется к теориям, окружающим эти проблемы и их возможным решениям. Название происходит от карточной игры в покер , которая является одной из игр, к которым применим этот тип проблем. Похожие проблемы, описанные как игры для двух участников, — это подбрасывание монеты на расстоянии Блума , проблема миллионеров Яо и забывчивый перевод Рабина .

Проблему можно описать следующим образом: «Как можно разрешить доступ к определенной информации только уполномоченным субъектам, не прибегая к услугам доверенного арбитра?» (Устранение доверенной третьей стороны позволяет избежать проблемы определения того, можно ли доверять третьей стороне, а также может сократить требуемые ресурсы.)

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

Было предложено несколько протоколов для этого, первый из которых был предложен Ади Шамиром , Роном Ривестом и Леном Адлеманом (создателями протокола шифрования RSA ). ^[1] Этот протокол был первым примером того, как две стороны проводили безопасные вычисления, а не безопасную передачу сообщений, используя криптографию; позже из-за утечки частичной информации в исходном протоколе это привело к определению семантической безопасности Шафи Голдвассером и Сильвио Микали . Концепция многопользовательского ментального покера была введена в книге Моти Юнга 1984 года «Криптопротоколы». ^[2] Позже эта область развилась в то, что известно как безопасные протоколы многосторонних вычислений (для двух и нескольких сторон).

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

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

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

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

Теперь колода перетасована.

Этот алгоритм может быть расширен для произвольного числа игроков. Игрокам Кэрол , Дэйв и т. д. нужно только повторить шаги 2-4 и 8-10.

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

Пример: Алиса выбрала карты с 1 по 5 из перетасованной колоды. Боб выбрал карты с 6 по 10. Боб просит посмотреть выданные ему карты. Алиса соглашается, что Боб имеет право посмотреть карты с 6 по 10, и дает ему свои индивидуальные ключи карт от A ₆ до A _10. Боб расшифровывает свои карты, используя как ключи Алисы, так и свои собственные для этих карт, от B ₆ до B _10. Теперь Боб может видеть карты. Алиса не может знать, какие карты у Боба, потому что у нее нет доступа к ключам Боба от B ₆ до B ₁₀ , которые требуются для расшифровки карт.

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

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

Кристиан Шиндельхауэр описывает сложные протоколы для выполнения и проверки большого количества полезных операций с картами и стопками карт в своей статье 1998 года «Инструментарий для ментальных карточных игр» [SCH98]. Работа касается операций общего назначения (маскировка и демаскировка карт, тасование и повторное тасование, вставка карты в стопку и т. д.), которые делают протоколы применимыми к любой карточной игре. Криптографические протоколы, используемые Шиндельхауэром, основаны на квадратичной остаточности , а общая схема по духу похожа на вышеприведенный протокол. Правильность операций можно проверить с помощью доказательств с нулевым разглашением , так что игрокам не нужно раскрывать свою стратегию для проверки правильности игры.

Библиотека C++ libtmcg [STA05] обеспечивает реализацию инструментария Schindelhauer. Она использовалась для реализации защищенной версии немецкой карточной игры Skat , достигая скромной производительности в реальном мире. В игру Skat играют три игрока колодой из 32 карт, поэтому она существенно менее вычислительно интенсивна, чем игра в покер, в которой от пяти до восьми игроков используют полную колоду из 52 карт.

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

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

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

Таким образом, игрокам нужно только вычислить шифрование для карт, которые фактически используются в игре, плюс некоторые накладные расходы на столкновения, которые невелики, пока количество необходимых карт намного меньше размера колоды. В результате эта схема оказывается в 2-4 раза быстрее (по общему количеству модульных возведений в степень), чем самый известный протокол [JAK99], который выполняет полную тасовку с использованием смешанных сетей .

Обратите внимание, что генерация случайных чисел безопасна, пока любой игрок генерирует действительные случайные числа. Даже если k-1 игроков сговариваются сгенерировать число r* , пока k -й игрок честно генерирует случайное , сумма все равно равномерно случайна в {0, 51}.${\displaystyle r'}$${\displaystyle r=r*+r'}$

Измеряемый с точки зрения количества одноагентных шифрований, алгоритм в [GOL05] является оптимальным, когда не происходит никаких коллизий, в том смысле, что любой протокол, справедливый для каждого игрока, должен выполнять по крайней мере столько же операций шифрования. Как минимум, каждый агент должен шифровать каждую фактически используемую карту. В противном случае, если какой-либо агент не участвует в шифровании, то этот агент подвержен обману со стороны коалиции оставшихся игроков. Неизвестные нешифрующему агенту, другие агенты могут делиться ключами, чтобы позволить им всем узнать значения всех карт. Таким образом, любой подход, полагающийся на агентов для выполнения шифрования, должен быть сосредоточен на схемах, которые минимизируют влияние коллизий, если они хотят достичь лучшей производительности.

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

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

1. Серверы S1 и S2 шифруют и перемешивают колоду карт и публикуют негибкое обязательство игрокам по некоторой перестановке зашифрованных карт. Это можно сделать с помощью любого из нескольких хорошо известных криптографических протоколов.
2. Игроки вычисляют независимые случайные числа в диапазоне {0,...,51}, которые объединяются для генерации случайного числа в диапазоне {0,..., 51}, как в [GOL05]
3. Случайное число используется в качестве индекса в случайной перестановке, соответствующий игрок получает «право собственности» на указанную карту, а серверы отправляют этому игроку ключи для считывания значения карты.

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

• Голдвассер, С. и Микали, С. 1982. Вероятностное шифрование и как играть в ментальный покер, сохраняя в тайне всю частичную информацию. В трудах четырнадцатого ежегодного симпозиума ACM по теории вычислений.
• [STA05] Стамер, Х. Эффективная электронная азартная игра: расширенная реализация набора инструментов для интеллектуальных карточных игр. WEWoRC 2005, LN P-74, 1-12, 2005
• [SCH98] Шиндельхауэр, К. Набор инструментов для интеллектуальных карточных игр. Тех. Представитель Медицинского университета Любека.
• [GOL05] Голле, П. Раздача карт в покерных играх. В трудах Международной конференции по информационным технологиям: кодирование и вычисления, (2005)

• Библиография по ментальному покеру
• LibTMCG — библиотека C++ для создания безопасных и честных карточных онлайн-игр
• Раздача карт с помощью криптографии — видео Numberphile с Роном Ривестом, объясняющим интуицию, лежащую в основе статьи «Ментальный покер».