Произвольно назначьте n элементов n агентам таким образом, чтобы каждый агент знал только свой собственный элемент

Question

Проблема

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

Другими словами, задача состоит в том, чтобы найти распределенный алгоритм, который

• однозначно присваивает $n$ номера агентов $1..n$
• позволяет каждому агенту ничего не знать о задании, кроме своего собственного
• при раскрытии задания позволяет другим игрокам проверить выполнение задания

Мы также предполагаем, что знание чужого задания является преимуществом для каждого агента, а преждевременное раскрытие своего собственного - недостатком.Предполагается также, что агенты могут общаться друг с другом скрытым от всех других агентов способом.

Частичное решение

Решение, которое я придумал, работает только при условии, что противники не сотрудничают.

Идея состоит в том, чтобы создать набор $n$ одноразовые номера и назначьте каждому агенту ровно один одноразовый номер.Затем набор передается от агента к агенту в согласованном порядке, скрытом от всех остальных, до тех пор, пока каждый агент не получит набор ровно один раз.Каждый раз, когда агент получает набор, он заменяет свой одноразовый номер новым, запоминает новый одноразовый номер и подтверждает получение набора другими.Вся эта процедура выполняется дважды, и в этот момент все агенты получают набор по крайней мере один раз после того, как все другие агенты меняют местами свои одноразовые номера, что делает невозможным распознавание и, следовательно, сопоставление одноразовых номеров с другими агентами.

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

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

---

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

Все идеи приветствуются!

Answer 1

Эта проблема является частью набора проблем, известных как Ментальный Покер.

Есть отличная и небольшая статья авторы: Шамир, Ривест и Адлеман, которые описывают практический способ реализации такого алгоритма.

Абстракция - это золото:

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

В этом документе даются следующие ответы:

1. Нет.(Предоставлено строгое математическое доказательство.)
2. ДА.(Приведен правильный и полный протокол.)

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

---

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

Предположим, у вас есть $n$ одноразовые номера (числа из $1$ Для $n$).Каждый участник протокола имеет доступ к секретным функциям $e_i$ и $d_i$ которые используются для шифрования и дешифрования данных.Эти функции должны удовлетворять нескольким свойствам, которые мы проанализируем позже.

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

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

Затем третий участник и так далее, пока все участники не перетасуют и не зашифруют данные с помощью своей секретной функции.

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

data = [1..n]
for i in [1..n]:
    data = [e_i(nonce) for nonce in data]
    shuffle(data)

После этой настройки каждый элемент data зашифрованы ли одноразовые номера всеми секретными функциями $e_i$ в случайном порядке, неизвестном ни одному участнику.

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

Участник $я$-th присваивается одноразовый номер на должности $я$.Чтобы восстановить такой одноразовый номер, участник $я$ спрашивает друг друга участник $j eq я$ чтобы расшифровать значение с помощью его секретной функции $d_j$ по очереди.В конце участник $я$ будет иметь свой одноразовый номер, зашифрованный только с помощью собственной секретной функции $e_i$ таким образом, он может восстановить его с помощью $d_i$.

Восстановление одноразового номера $я$:

nonce_i_encrypted = data[i]
for j in [1..n]:
    if j == i:
        continue
    nonce_i_encrypted = d_j(nonce_i_encrypted)

nonce_i = d_i(nonce_i_encrypted)

В конце этой процедуры каждый участник узнает свой одноразовый номер, но ни один другой участник ничего о нем не знает.

После использования этих значений для вашей текущей задачи игрок может заявить, что он действительно контролирует такой одноразовый номер, либо опубликовав секретные функции $e_i$ и $d_i$, так что каждый может локально вычислить все значения или расшифровать значение data[i] после первого шага, но перед вторым шагом, опубликуйте, а затем используйте это значение в качестве входных данных на втором шаге, чтобы полностью расшифровать его.

Функции $e_i$ и $d_i$ должен обладать следующими свойствами:

1. $e_i(x)$ является ли зашифрованная версия сообщения $x$ под ключом $я$,
2. $d_i(e_i(x)) = x$ для всех сообщений $x$ и ключи $я$,
3. $e_i(e_j(x)) = e_j(e_i(x))$ для всех сообщений $x$ и ключи $я$ и $j$,
4. Данный $x$ и $e_i(x)$ криптоаналитику вычислительно невозможно вывести $я$, для всех $x$ и $я$,
5. Передавались какие-либо сообщения $x$ и $y$, вычислительно невозможно найти ключи $я$ и $j$ такой , что $e_i(x) = e_j(y)$.

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

Они предлагают простую схему шифрования, которая удовлетворяет этим свойствам.Допустим, все участники согласны с некоторым большим простым числом $P$ (это нормально, если это зафиксировано в протоколе).И каждый участник тайно выбирает случайное число $k_i$ такой , что $gcd(k_i, P - 1) = 1$.Допустим, $q_i$ это такая ценность, что $k_i \cdot q_i \equiv 1 \mod(P -1)$.Затем участник $я$ может использовать секретные функции:

$$e_i(x) = x^{k_i} \mod(P)$$ $$d_i(y) = y^{q_i} \mod(P)$$

Некоторые предостережения по поводу этого алгоритма:Участники не могут мошенничать таким образом, чтобы сговор помог им узнать одноразовый номер о другом партнере (если, конечно, $n-1$ участники вступают в сговор, и остается только один одноразовый номер).Однако злоумышленные участники могут атаковать протокол, не участвуя в нем, что фактически останавливает процесс обработки, поскольку от каждого участника требуется множество действий, пока они обрабатывают одноразовые номера.Они также могут выдавать тарабарщину, но это можно смягчить, расширив протокол, чтобы определить, какой участник был виновником, и наказать такого участника на более высоком уровне.

---

Я реализовал этот алгоритм для игры в покер в РЯДОМ С блокчейном.Вы можете увидеть код в rust здесь.Обратите внимание, что в блокчейне нет никакой доверенной третьей стороны, но есть доверенная вычислительная среда, которую все участники могут использовать в качестве механизма для запуска этого протокола.