Совместные конфиденциальные вычисления: как это работает

Привет, Хабр! Меня зовут Пётр Емельянов и я — эксперт по машинному обучению (и не только) в Skillbox (и не только), а еще – CEO межбанковской скоринговой платформы Bloomtech. В этой статье расскажу про конфиденциальные вычисления. Статья написана по мотивам моего вебинара для закрытого комьюнити Skillbox Code Experts, объединяющего экспертов направления программирования.

Введение

Моя основная деятельность — конфиденциальная обработка данных. Это такая развивающаяся область науки и техники, в которой часто возникает что-то новое, поэтому терминология ещё не устоялась. То, чем я занимаюсь, по-английски называется Secure Multi-Party Computation, а на русский переводят как совместные или многосторонние вычисления. Однажды я видел перевод: «многопартийные вычисления», – но, надеюсь, это единичный случай. Лично мне нравится вариант: «конфиденциальные вычисления», который использует википедия. Его буду использовать и я.

Представьте, вы собрали какие-то ценные данные, зашифровали их и сохранили на диске. Таким образом, вы защищаете данные во время хранения (data-at-rest). Далее, предположим, вам нужно передать данные по сети с одного сервера на другой. Серверы устанавливают защищённое соединение и обмениваются данными – снова зашифрованными. Так серверы защищают данные во время передачи (data-in-transit). Пока всё знакомо и понятно. Далее вы собираетесь делать то, ради чего вы эти данные собирали, хранили и передавали: использовать их. Что-нибудь посчитать, агрегат какой-нибудь, статистику или даже модельку обучить. Анализировать зашифрованные данные —, затруднительно, поэтому вы их расшифровываете и… делате беззащитными.

Во-первых, это странно: вы старательно защищали данные, когда хранили и передавали, и вдруг почему-то перестали. Во-вторых, это опасно: атаки, утечки, несанкционированный доступ, всё, что угодно может случиться, когда данные уязвимы. Ну, и в-третьих, расшифровывать не обязательно: существуют методы, защищающие данные, когда они используются (data-in-use). Совместные конфиденциальные вычисления – один из них.

Безопасность и Конфиденциальность   

Конфиденциальность и безопасность – связанные понятия, но акценты разные.

Пусть есть человек, его зовут Боб, и у него украли банковскую карту. Это типичное нарушение безопасности, security breach. В общем, караул, деньги Боба под угрозой. На самом деле всё не так страшно: Боб звонит в банк или нажимает две кнопки в банковском приложении и блокирует карту. Проблема решена, деньги спасены. В цифровом мире это – заслуга информационной безопасности.

И вот наш Боб заблокировал свою карту, успокоился, проголодался, захотел пиццу и всем об этом рассказал. У рынка появилось знание: Боб хочет пиццу. Полезное ли это знание? Безусловно. Но монетизировать его сложно, потому что Боб хочет пиццу прямо сейчас и хочет её недолго: съел и перестал хотеть. Это знание конфиденциально, его раскрытие – нарушение конфиденциальности, но последствия от такого раскрытия временны, как и само знание.

Теперь представим, что кто-то узнал, сколько Боб зарабатывает. Это очень ценная информация, утечка которой может неприятно повлиять на Боба: зависть коллег, агрессивный маркетинг, личная безопасность. А ещё – это длящаяся информация, её сложно «отменить». Боб не может позвонить начальнику и пожаловаться: «Шеф, тут пронюхали, сколько я получаю, давайте я буду зарабатывать какую-нибудь другую сумму». Но даже если может, это не решит проблему: рынок долго будет опираться на данные о доходах Боба и предлагать ему банковские продукты, квартиры в новостройках и китайские автомобили.

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

Как обеспечить конфиденциальность данных? 

Самый простой вариант: не обрабатывать данные. Если такой вариант не подходит, нужно защищать данные на всех этапах жизненного цикла: хранение (data-at-rest), передача (data-in-transit), использование (data-in-use). Когда храните и передаёте данные, всё более или менее ясно: их можно зашифровать. Что делать, когда вы используете данные?

Чтобы ответить на этот вопрос, нужно ответить на другой: что такое использование данных? Данные – это числа, и за всеми технологиями и методами их обработки – от простых описательных статистик до искусственного интеллекта – стоит математика. Обработать данные – значит что-то посчитать: сложить, умножить, вычислить нелинейную функцию.

Традиционная парадигма таких вычислений подразумевает, что всё должно быть сложено в одно место: и данные (числа), и алгоритмы обработки. Поэтому очевидная стратегия защиты конфиденциальных данных – защита этого единого места, защита центра обработки данных.

Первый вариант тут – административный: просто заставить убедить всех складывать свои данные в одно место и потом забирать оттуда результат их обработки (само собой, не безвозмездно). Второй вариант — административно-технологический: сделать специальную железяку, которая аппаратно защищает область памяти даже от того, кто физически эту железяку контролирует. Так, например, устроены доверенные среды исполнения (Trusted Execution Environment, TEE), самая заметная из которых – Intel SGX. Это прекрасная технология, значительно лучше, чем обычная административная централизация, но это… – всё равно централизация. Просто доверять придется не условному хозяину сервера, а производителю технологии. К тому же, это vendor lock.

Для тех, кто не хочет передавать свои данные в единый центр (даже аппаратно защищённый производителем), существуют программные, исключительно алгоритмические методы конфиденциальной обработки данных. Это, прежде всего, совместные конфиденциальные вычисления и гомоморфное шифрование. Про гомоморфное шифрование мы как-нибудь поговорим отдельно, а сегодня наша тема – совместные вычисления, они же SMPC (Secure Multi-Party Computation), они же (S часто опускают) – просто MPC.

Основных момента в MPC два: 1) владелец данных – активный участник вычислений; 2) для того, чтобы делать математику с числами, сами числа видеть не обязательно. Как это работает? Давайте разбираться на примере.

Конфиденциальное сложение

Пусть есть три достаточно скрытных товарища – Алиса, Боб и Мэллори. Алиса знает некоторое секретное число , Боб знает секретное число , а Мэллори знает секретное число z. Наша задача вычислить сумму так, чтобы 1) товарищи не узнали чисел друг друга; 2) товарищи не консолидировали свои числа у некой третьей стороны.

Для простоты пусть , и . Боб генерирует два случайных числа из равномерного распределения, пусть это будет (-5) и 6, и вычисляет третье как . Что получилось? А получилось, что Боб разложил свой секрет в сумму трёх случайных чисел: . Алиса и Мэлори делают тоже самое, у Алисы выходит , а у Мэлори: .

 Далее Боб оставляет одно случайное слагаемое себе (пусть это будет ), а другие передает товарищам: уходит Алисе, а – Мэллори. Алиса и Мэллори повторяют за Бобом: одно число оставляют себе, два других раздают соседям: по одному – каждому. Казалось бы, товарищи обменялись информацией, но всё, что они передали друг другу, – исключительно случайные числа. Извлечь из них полезную информацию невозможно.

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

Следующий шаг такой: товарищи складывают случайные числа, которые имеют. Каждый вычисляет одно, тоже случайное число. У Боба получается , у Алисы — , у Мэллори – .

Далее друзья обмениваются числами, которые рассчитали. Боб передаёт свой Алисе и Мэллори, Алиса передаёт Бобу и Мэллори, а Мэллори передаёт Алисе и Бобу. Теперь у всех одинаковый набор чисел, остаётся их сложить. Каждый участник вычисляет и узнаёт сумму своего и двух секретных слагаемых своих друзей, которые никому их не передавали и нигде не консолидировали. На этом протокол конфиденциального сложения завершается.

Помните, как в начальной школе вам объясняли коммутативность (правило перестановки) сложения: от перестановки мест слагаемых сумма не изменяется. Именно это и произошло. Мы просто сделали слагаемые случайными.

Два важных замечания. Во-первых, модульная арифметика: чтобы вычисления были безопасными в строгом математическом смысле, считать всё нужно по модулю некоторого фиксированного числа (этот момент я опустил для простоты). Во-вторых, случайность: тема фундаментальная, поэтому про случайность – подробнее.

Случайность для разделения секретов 

Обычные программисты часто недооценивают случайность, для них это просто вызов функции из стандартной библиотеки. Например, rand() в С/С++ или random.random() в python. Полагаю, немногие задумываются о том, что у этих функций «под капотом».

Расскажу историю о важности случайности, о которой даже кино сняли The Luckiest Man in America. Посмотрите на картинку: 1984 год, Майкл Ларсен оставляет без штанов обыгрывает американский телеканал CBS в игровое телешоу Press Your Luck. В первом раунде этой игры участники отвечают на вопросы и зарабатывают очки. Во втором раунде участники соревнуются в удачливости и либо теряют все очки, заработанные в первом раунде, либо преумножают их. Устроено это примерно так: по экрану хаотично движется квадрат, участник нажимает кнопку, квадрат останавливается, и, в зависимости от того, где он остановился, участник либо выигрывает, либо проигрывает. Проигрывает, конечно, значительно чаще. Но не наш Майкл.

Полгода Майкл записывал выпуски Press Your Luck на видеомагнитофон, а потом пересматривал записи снова и снова. И в итоге «сломал систему». Майкл выяснил, что движения квадрата по экрану вовсе не случайны: есть паттерны, их всего пять, они повторяются по кругу. Майкл поехал на игру и стал нажимать на кнопку. Первый раз он ошибся, потому что не знал, как быстро среагирует система, но потом приноровился, и началось настоящее шоу. Майкл нажал на кнопку 47 раз и промазал лишь однажды (как раз когда изучал скорость реакции кнопки). Майкл выиграл более 100 тысяч долларов – на тот момент абсолютный рекорд для телевизионных игровых шоу Америки.

Я рекомендую посмотреть эту игру (ссылка), действительно занятно. Особенно, когда Майкл начинает радоваться до того, как останавливается квадрат. Потому что Майкл знает заранее, где он остановится. Биографию Ларсена (ссылка) тоже почитайте: скупал краденое, чинил кондиционеры, водил фургон с мороженым. Вполне литературный сюжет: «маленький» человек, победивший систему.

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

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

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

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

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

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

Протокол конфиденциального умножения

Умножить числа труднее, чем сложить. Причём, значительно. Есть несколько способов конфиденциального умножения, тут мы рассмотрим самый наивный и простой. Пусть Боб, который знает , и Алиса, которая знает , хотят, чтобы кто-нибудь узнал произведение так, чтобы никто не узнал оригинальные и . Обратите внимание, произведение может узнать кто-нибудь, но не Алиса и не Боб, потому что каждый из них знает один из двух множителей.

Давайте интерпретируем эту задачу геометрически:

Произведение – это площадь прямоугольника со сторонами и . Пусть Боб и Алиса раскладывают свои x и y в суммы трёх случайных чисел:.

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

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

Боб передает и серверу 1, и – серверу 2, и – серверу 3. Алиса поступает симметрично: передает и серверу 1, и – серверу 2, и – серверу 3. Заметьте, схема разделения секрета избыточна: каждый сервер получает два случайных числа из трёх. Чуть забегу вперед: это называется пороговое разделение секрета 2 из 3: секрет разделён между трёмя участниками, но восстановить его могут любые два. Суперсила такой схемы – репликация (если один из участников исчезает, секрет не утрачивается), слабость – двое могут сговориться и узнать секрет третьего. Впрочем, схема обобщается до из : секрет делится на участников, любые могут его собрать. Любознательным рекомендую почитать про схему разделения секрета Шамира, это очень красивая и элегантная математическая конструкция.

Вернёмся к нашим серверам. Сервер 1 теперь может вычислить площади прямоугольников 1, 2, 4, сложить их и получить одно число. Аналогично серверы 2 и 3 вычисляют суммы площадей прямоугольников 5, 6, 9 и 3, 7, 8 соответственно. 

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

Давайте ещё раз, но уже на конкретном примере. Для простоты пусть, как и прежде, , а 3.

 Шаг №1: Боб и Алиса разделяют свои секреты между трёмя серверами, схема разделения пороговая, 2 из 3.

Шаг №2: серверы выполняют локальные вычисления, в результате которых у каждого образуется по одному числу.

Шаг №3: серверы выполняют конфиденциальное сложение этих чисел.

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

Вернёмся к шагу №2. У серверов появились числа, сумма которых равна искомому произведению. Другими словами, эти числа – доли секрета результата, который разделён между участниками вычислений. Это важное свойство многих MPC-протоколов: результат вычислений над долями секрета представляет собой доли секрета. В нашем простом примере серверы их сложили и восстановили результат – произведение xy. Но представьте, что участники вычисляют не просто произведение двух чисел, а сложную функцию, состоящую из большого количества арифметических операций. В этом случае результаты промежуточных операций восстанавливать не нужно (и даже, как правило, нельзя!): участники продолжают оперировать долями секретов, пока не вычислят функцию до конца, и восстанавливают только финальный результат.

Машинное обучение

Взгляните на формулу. Это уравнение линейной регрессии, настоящий алгоритм машинного обучения. Числа   и называют регрессорами или факторами модели, y – это таргет или зависимая переменная, а и — параметры (веса) или коэффициенты регрессии. Обучить регрессию значит подобрать такие параметры и , при которых ошибка модели (условно говоря, разница между показаниями модели и заранее известными результатами) будет минимальной.

В уравнении линейной регрессии нет ничего, кроме умножений и сложений. Алгоритм обучения регрессии – это итеративное обновление параметров, состоящее из умножений и сложений. Выше мы рассмотрели MPC-протоколы, которые позволяют складывать и умножать числа. Получается, инферить и обучать регрессию можно конфиденциально. Не глядя на данные. И на веса модели тоже. Веса – это результат обучения, поэтому, когда оно завершится, веса будут разделены между участниками, которые выполняли вычисления. И самое любопытное: веса можно не восстанавливать, не собирать воедино. Участники могут сообща вычислять регрессию, оперируя долями секретов весов модели. Вдумайтесь: участники не знают данные, на которых обучали модель, участники не знают саму модель (веса), но могут использовать её предсказания. Звучит неплохо, правда?

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

Понятно, что у MPC есть цена – вычислительный оверхэд, накладные расходы. Вы видели, что на одну арифметическую операцию участники выполняют несколько, передавая друг другу случайные числа (то есть обмениваясь сообщениями по сети). Но товар, за который вы платите эту цену, – конфиденциальность данных. В том числе – ваших. И тут лучше не скупиться.

Заключение

Совместные конфиденциальные вычисления – активно развивающаяся область науки и техники, у которой уже есть практические применения. Алгоритмов и протоколов много, постоянно возникают новые, а существующие эволюционируют, становятся быстрее, эффективнее, практичнее. Протоколы сложения и умножения, которые мы рассмотрели в статье, – это букварь, самые основы, местами сознательно упрощённые. Цель такая: сформировать интуицию, показать, что MPC работает, что конфиденциальная обработка данных не просто слова, а децентрализация – правильная (во многих случаях) альтернатива.

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