Криптографический покер

Вопрос возник. Возможно ли реализовать карточную игру покер (холдем) таким образом, чтобы можно было обеспечить полную защиту (понятное дело, криптографическую) процесса игры от подтасовки и мухлежа?

Дано:

1. Игровой сервер — серверное приложение игры
2. Игроки (от 2-10) — приложение игрового клиента

Условия:

1. Игроки получают по 2 карты из рандомно перетасованной колоды
2. На стол выкладывается от 3 до 5 карт из той же колоды
3. Ни сервер, ни другие игроки не могут знать или хоть как-то вычислить какие карты у других игроков, до окончания игры
4. Ни сервер, ни другие игроки не должны знать, какие карты выбраны из колоды, кроме выложенных на стол
5. Раздача карт ведётся из одной колоды, так, чтобы игроков не оказалось два пиковых туза
6. Ни один игрок не может, пользуясь незнанием других игроков, изменить свои карты на желаемые

Интересует не конкретно реализация покера, а именно возможные алгоритмы.

Есть идеи? :)

У каждого игрока есть постоянная пара ключей. Закрытый лежит на сервере и не известен другим игрокам, открытый - только у конкретного игрока, в процессе игры никак по сети не гоняются.
При начале игры каждый игрок генерирует себе временную пару ключей. Закрытые ключи пересылаются между игроками, на сервер не отправляются. Используется для обмена данными между игроками, чтобы сервер ничего не перехватил.
Сервер генерирует колоду и каждую карту защищает своей цифровой подписью.
Сервер отправляет колоду, допустим игроку № 1 - И1. Он перетасовывает колоду и рассылает другим игрокам (шифруя временными ключами).
Каждый игрок соответственно перепроверяет, что с колодой всё нормально (цифровая подпись на месте, набор карт правильный) и шифрует её ключами каждого из игроков.
Полученный набор зашифрованных карт пересылается каждым игроком на сервер.
т.е. каждый игрок отправит на сервер табличку, в которой строка - это карта, а столбец - шифровка карты ключом соответствующего игрока.
Сервер перепроверяет, что все игроки прислали одинаковые таблички и никто ничего не подменил.
Еще раз тасует колоду. Для отправки конкретному игроку карта дополнительно шифруется соответствующим постоянным ключом. Соответственно закрытые карты расшифровываются игроком в два этапа: сначала постоянным ключом, а потом - временным.
Открытые карты отправляются как есть и игроки их расшифровывают только своими временными ключами.
Когда игрок вскрывается, сервер рассылает имеющиеся у него шифровки этих карт другим игрокам, те расшифровывают своими ключами и сверяют, что подмены не было и игроку действительно пришла от сервера эта карта.

hVostt,

Ну, как вариант:

2 колоды: одна на сервере – с картами игроков, вторая у игроков – с номиналами карт.

Игроки согласованно генерируют набор карт [ID –> карта] любым образом и обмениваются ею между собой. Все использованные ID отправляются на сервер (без номиналов). Сервер собирает колоду из 54х (или сколько там карт) ID, тасует её и раздаёт карты игрокам, часть карт выкладывает на стол. При этом игроки знают свои карты, но не знают карты на столе или карты других игроков, а сервер знает все карты, но не знает их номиналов.

Дальше идёт сама игра как обычно. Когда все ставки закончились и все вскрываются – все игроки отправляют свои колоды (одинаковые!) на сервер, он сверяет их между собой и со своими данными о раздаче, строит расклад с номиналами и рассылает его игрокам. Игроки сверяют расклад со своими картами и подтверждают его.

Раунд завершён.

alekcvp
При этом игроки знают свои карты, но не знают карты на столе или карты других игроков

При этом игроки знают свои карты и карты на столе, но не карты других игроков, разумеется.

hVostt
1. Игроки получают по 2 карты из рандомно перетасованной колоды 2. На стол выкладывается от 3 до 5 карт из той же колоды 3. Ни сервер, ни другие игроки не могут знать или хоть как-то вычислить какие карты у других игроков, до окончания игры 4. Ни сервер, ни другие игроки не должны знать, какие карты выбраны из колоды, кроме выложенных на стол

С колодой работает игровой сервер, поэтому, в любом случае, игрокам придётся доверять серверу.

5. Раздача карт ведётся из одной колоды, так, чтобы игроков не оказалось два пиковых туза

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

6. Ни один игрок не может, пользуясь незнанием других игроков, изменить свои карты на желаемые

Тривиальная электронная подпись раздач сервером.
Надо отчётливо понимать, что никакая "интернет-схема" не защищена от утечек по по побочным каналам.
Она же - игра на одну руку. Таким образом, серверу тоже придётся доверять игрокам.

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

С таким пренебрежением, решение становится банальным и тривиальным.

Basil A. Sidorov
Надо отчётливо понимать, что никакая "интернет-схема" не защищена от утечек по по побочным каналам. Она же - игра на одну руку. Таким образом, серверу тоже придётся доверять игрокам.

Ну утечки это уже проблема защиты каналов, я речь про общий алгоритм.

Вот как обмен сообщениями с помощью открытого/закрытого ключа, можно отправлять по открытым каналам. Атака in middle решается с помощью доверенных сертификатов. Но как организовать подобное для игры в покер — пока не понятно.

Pu4koff
Закрытые ключи пересылаются между игроками, на сервер не отправляются. Используется для обмена данными между игроками, чтобы сервер ничего не перехватил.

А зачем обмениваться закрытыми ключами? Может открытыми?

Pu4koff
т.е. каждый игрок отправит на сервер табличку, в которой строка - это карта, а столбец - шифровка карты ключом соответствующего игрока. Сервер перепроверяет, что все игроки прислали одинаковые таблички и никто ничего не подменил.

А как вычислить, что каждый игрок взял себе по карте, которую ОН ЗНАЕТ, но никто больше не знает, и при этом неизвестно, какие карты какой игрок взял, да и вообще, какие конкретно карты были извлечены, чтобы можно было делать предположения?

Известно должно быть только карты, выложенные на стол.

Тут всё бы ничего, если бы из колоды можно было брать любые карты. Но брать можно только из тех, которые другой игрок УЖЕ не взял. Как это вычислить и при этом не раскрыть информацию?

Pu4koff
Соответственно закрытые карты расшифровываются игроком в два этапа: сначала постоянным ключом, а потом - временным. Открытые карты отправляются как есть и игроки их расшифровывают только своими временными ключами.

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

Проблема именно здесь. Непонятно как решать.

alekcvp
Игроки согласованно генерируют набор карт [ID –> карта] любым образом и обмениваются ею между собой.

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

Представим себе реальную ситуацию:

1. Колода карт лежит на столе
2. Все видят эту колоду карт, её нельзя подменить и посмотреть какие там карты
3. Все берут по 2 уникальных карты, количество карт в колоде уменьшается.
4. Никто не знает какие у кого карты, включая крупье, даже если один игрок играет скрытно от казино.

Нужно обеспечить такую же ситуацию, но на уровне приложения. Доверять серверу -- это не решение. Можно выпустить доверенные сертификаты, чтобы исключить атаки men-in-middle. На этом всякое доверие заканчивается.

Слышал, что абсолютно честное (поскольку децентрализованное) казино на блокчейне уже реализовано. Кажется даже не на отдельном блокчейне, а в виде контракта в Эфириуме...