Multi party computation ч.1. Что это такое?

В последних новостях все чаще можно увидеть странные слова "multi-party computation", "secure multi-party computation" или кто-то даже слышал про Nillion (о них позже напишу). Что же это такое?

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

Что это такое и зачем?

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

Tesla и Waymo хотят обучить свои нейроночки на совместных данных, дабы машинки летали по дорогам, при этом не делясь ими друг с другом
Электронное (честное и интимное) голосование, где все хотят за кого-то проголосовать и не раскрывать друг с другом
Электронные аукционы
Хранение и работа с данными, которые достаточно сенситив (например длина члена)

При этом все начиналось достаточно с простой задачи.

Есть три миллионера, как им посчитать средний доход, не раскрывая никому полностью свои цифры?

...Ладно, задача достаточно простая, в реальности она другая, но нужно сначала разобраться с этой.

Средний доход есть сумма / количество, а значит им нужно как-то случайно разбить (используя и 0 и отрицательные числа, в зависимости что попадется) размеры их дохода между друг другом, а потом сложить и разделить на 3.

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

Выглядит громоздко, да, можно упростить решение:

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

Теперь как звучала изначально задача:

Есть два миллионера. Нужно проверить, богаче ли один другого, не разглашая цифр друг с другом или с третьей стороной.

Так как задача является базовой, то имеет огромное количество решений, с самой разной сложностью. Есть как криптографические с PHE, так и для детишек. Сначала разберем для детишек.

Пусть Alice получает 40 млн, а Bob 30
Тогда Alice купит коробки с замком и дыркой как у копилки, нарисует поверх каждой цифры в млн (10, 20, 30, 40, 50,.. 25 там, главное в диапазоне).
И выкинет ключи ото всех коробок, кроме той, где указано его количество денег. (В принципе может продемонстрировать Bob'у, что ключ один (главное чтобы по нему нельзя было коробку идентифицировать)).
Bob же сделает следующее: Пройдет по всем коробкам и опустит листики, внутри которых написано Да или Нет, в зависимости от того, сколько он получает и сколько на коробке.
После этого, он уходит, подходит Alice и проверяет свою коробку (ведь больше никакие не может). И там либо Да, либо Нет, а значит либо они получают одинаково, либо нет, но непонятно кто больше и насколько.

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

Один из сотни криптографических способов (выбрал из-за простоты понимания):

Но для начала нужно объяснить вкратце еще одно популярное направление Homomorphic encryption. По сути, это Layer для чисел (шифрование), позволяющий делать такие же операции, как и с обычными числами, без нарушения их свойств или формата. Но при этом если a>b, то не обязательно будет f(a) >f(b), иначе смысла в схеме не будет особого.

Зачем же она нужна нам тут? Она позволяет проводить следующие операции
(под f^(-1) я подразумеваю расшифрование, под f шифрование)

Мы можем зашифровать и расшифровать чиселку: a = f^(-1) (f(a))
Мы можем складывать в ней и получим идентичные значения при дешифровании (важное условие):
a - b = f^(-1) (f(a) - f(b)
Но также мы можем сделать следующую важную штуку:
f(a) + f(b) = f(a+b)
Тогда по сути a + b = f^(-1) (f(a) + f(b)) = f^(-1) (f(a+b))

Тогда сама схема выглядит следующим образом:

Есть Алиса и число a, есть Боб и число b
Пусть у Боба есть эта схема, он знает как зашифровать и расшифровать. Боб считает f(a) и отправляет Алисе, вместе со схемой.
Алиса придумывает случайное число r и считает V = (f(a) - f(b)) (+) f(r)
(+) это Xor. Функция делает побайтовое следующие действия:

Если битик а и битик б равны, то bit_a (+) bit_b = 0
Иначе bit_a (+) bit_b = 1

Боб расшифрует, получает (a-b) (+) r и отправляет самый левый битик. Этот битик хранит информацию о знаке (a-b) (+) r.
Алиса проводит еще разок Xor битика, полученного от боба и самого левого битика от r и если 0, то a>b, иначе наоборот.

Ничу непонятно, разберем схему с 3 пункта

Если Алиса просто отдаст Бобу f(a) - f(b), то он сможет посчитать это у себя, ведь f(a) - f(b) = f(a-b), а значит f^(-1) (f(a-b)) = a-b и понять сколько зарабатывает Алиса, ничего не сказав ей.
Зачем нужен xor? чтобы полностью поменять число. Не прибавить, не умножить. Покажу на примере
Пусть есть a = 13 и a в битовом формате будет выглядеть так
001101 (нулей может быть больше слева, в зависимости от формата)
и пусть если число b = 23
010111
тогда a (+) b (идем слева направо)

0 (+) 0 = 0
0 (+) 1 = 1
1 (+) 0 = 1
1 (+) 1 = 0
0 (+) 1 = 1
1 (+) 1 = 0

Получим число 26

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

Если вдруг кто-то заинтересовался кодом, то вот он. https://github.com/valpaq/yao-s-milltionare-phe

Если вдруг кто-то заинтересовался, почему же FHE такой клевый, раз туда сюда чиселки можно и все секурно, то вот ответ почему.
Да, это опенсорс штука, не те размеры чисел которые интересуют, но

197 секунд заняла настройка изначальных параметров на моем компуктере, для чисел u16
а также все вычисления крайне долгие и мощностей пока не хватает под них в нашем мире)
Keep building...