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

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

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

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

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

Перетасовка карт с использованием коммутативного шифрования

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

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

Алгоритм

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

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

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

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

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

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

Слабость

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

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

«Набор инструментов для интеллектуальных карточных игр» и его реализация

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

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

Протокол покера без тасования

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

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

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

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

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

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

Повышение производительности за счет повышения доверия

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

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

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

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

Ссылки

^ А. Шамир, Р. Ривест и Л. Адлеман, «Ментальный покер», Техническая записка LCS/TM-125, Массачусетский технологический институт, апрель 1979 г. https://apps.dtic.mil/dtic/tr/fulltext /u2/a066331.pdf
^ Моти Юнг : Криптопротоколы: подписка на открытый ключ, секретная блокировка и многопользовательская игра в ментальный покер (расширенное резюме). КРИПТО 1984: 439–453.

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

Внешние ссылки

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

[1] А. Шамир, Р. Ривест и Л. Адлеман, «Ментальный покер», Техническая записка LCS/TM-125, Массачусетский технологический институт, апрель 1979 г. https://apps.dtic.mil/dtic/tr/fulltext /u2/a066331.pdf

[2] Моти Юнг : Криптопротоколы: подписка на открытый ключ, секретная блокировка и многопользовательская игра в ментальный покер (расширенное резюме). КРИПТО 1984: 439–453.

[1]

[2]