Проблема имеет «простое решение» с использованием общих методов.
Существуют расширения проблемы миллионеров Яо о том, как безопасно вычислять любая схема $С(х, у)$. Это целая область исследований, которая обычно называется «Безопасные вычисления» или «Многосторонние вычисления».
Существуют схемы, которые могут сортировать входные данные по имени сортировочные сети. Пока есть технически $O(n\logn)$ (сеть сортировки AKS + сортировка Zigzag), они технически сложны, с плохими константами, поэтому на практике почти всегда лучше использовать $ О (п (\ журнал п) ^ 2) $ сеть сортировки, которых существует множество (например, Batcher Odd-Even Mergesort).
Это означает, что ваша проблема решается путем вычисления сети сортировки (скажем, Batcher Odd-Even Mergesort) с использованием общих методов двухсторонних вычислений.
Глядя на реализации протоколов MPC, это выглядит так: этот от Бостонского университета включает соответствующую демонстрацию. В частности, они
- суммировать два входных массива, а затем
- отсортировать результат с помощью пузырьковой сортировки.
Вероятно, вы можете повторно использовать часть этого кода, но вам нужно быть осторожным.
Гарантия безопасности MPC заключается в том, что
Протокол MPC показывает только $С(х,у)$, напримернастолько хорош, насколько оба участника вносят свой вклад $х, у$ какой-либо доверенной третьей стороне $Т$, который затем вычисляет $С(х,у)$, и говорит им ответ.
Теоретически вы можете взять приведенный выше пример кода, поменять местами часть, которая суммирует вещи, на конкатенацию, и продолжить. Это приведет к практически небезопасной схеме --- учитывая $х$ и $С(х,у)$, восстановить несложно $у$.
Я бы вместо этого предложил иметь $С(х,у)$ вычислить (в отсортированном представлении конкатенации $х||у$) битовый вектор, указывающий, где должны заканчиваться элементы каждой стороны.
Это по-прежнему кодирует всю соответствующую информацию о заказе, но скрывает ввод каждой стороны от другой стороны (за исключением информации о заказе, которая «должна просочиться»).
Это можно сделать с помощью
- Отображение каждого элемента $t$ из $х$ к $2т$,
- Отображение каждого элемента $t$ из $у$ к $2т+1$,
- объединение этих преобразованных элементов,
- сортировка конкатенации,
- отображение $t\mapsto t\bmod 2$ в конце.
Эта схема вычисляет описанную ранее функцию и «разрывает связи» между $х$ и $у$ поставив элемент из $у$ позже в векторе. Этот выбор произволен.
Конечно, это мое представление о разумной схеме $С$ для вычисления, которые могут достичь ваших целей.
Вы можете подумать, что он пропускает слишком много информации, и у вас есть какая-то другая схема, которую вы хотите вычислить.
Вы по-прежнему можете использовать общие методы MPC для этого --- при условии, что вы можете указать вычисление, которое хотите сделать.
В комментариях вы упомянули о желании многопартийной версии этого.
Это непосредственно следует из приведенной выше конструкции, но я все равно буду обсуждать это явно.
Позволять $P_0,\точки, P_{k-1}$ быть сторонами с входными данными $\vec x_0,\dots, \vec x_{k-1}$.
Определение цепи $C(x_0,\dots, x_{k-1})$ что
- для каждого $я$, применяет функцию $t\mapsto kt + i$ каждой координате $x_i$,
- объединяет все результаты вместе
- сортирует результаты, например, с помощью сортировочной сети,
- вычисляет функцию $t\mapsto t\bmod k$ на каждый элемент вывода.
Результатом будет вектор с элементами в $\{0,\dots,k-1\}$.
Для простоты скажем, что результат $[0,3,2,2,1,0,1,3]$.
Это укажет всем 4 сторонам, что относительный порядок их входных данных
- наименьший элемент партии 0
- наименьший элемент партии 3
- наименьший элемент партии 2
- самый большой элемент партии 2
- наименьший элемент партии 1
- самый большой элемент партии 0
- самый большой элемент партии 1
- самый большой элемент партии 3.
Если кто-то использует соответствующую схему MPC (слова, которые нужно искать, это «Злонамеренно безопасные многосторонние вычисления»), то это доказуемо все, что злоумышленник узнает, по модулю некоторых технических предположений. Эти допущения зависят от конкретной схемы, которую вы используете, но обычно они выглядят примерно так:
- не слишком много участников протокола "вступают в сговор с целью нарушения протокола",
- противники эффективны в вычислительном отношении, и
- возможно, есть какая-то фаза «надежной настройки».
