Протокол конфиденциального вычисления

02.01.2022

В криптографии протокол конфиденциального вычисления (также безопасное, защищенное или тайное многостороннее вычисление, англ. secure multi-party computation) — криптографический протокол, позволяющий нескольким участникам произвести вычисление, зависящее от тайных входных данных каждого из них, таким образом, чтобы ни один участник не смог получить никакой информации о чужих тайных входных данных. Впервые задача конфиденциального вычисления была поднята Эндрю Яо (англ. Andrew Yao) в 1982 году в статье. Два миллионера, Алиса и Боб, хотят выяснить, кто же из них богаче, при этом они не хотят разглашать точную сумму своего благосостояния. Яо предложил в своей статье оригинальный способ решения этой задачи, получившей впоследствии название проблема миллионеров. Гораздо позже, в 2004 году Йехуда Линделл (Yehuda Lindell) и Бенни Пинкас (Benny Pinkas) предоставили математически строгое доказательство корректности протокола Яо в статье. Задача конфиденциального вычисления тесно связана с задачей разделения секрета.

Формализованная постановка задачи

В конфиденциальном вычислении участвуют N участников p1, p2, …, pN. У каждого участника есть тайные входные данные d1, d2, …, dN соответственно. Участники хотят найти значение F(d1, d2, …, dN), где F — известная всем участникам вычислимая функция от N аргументов. Допускается, что среди участников будут получестные нарушители, то есть те, которые верно следуют протоколу, но пытаются получить дополнительную информацию из любых промежуточных данных.

Требования к безопасности

К безопасности протоколов конфиденциального вычисления обычно предъявляются различные требования в зависимости от ситуации. Приведём основные требования.

  • Конфиденциальность. Никто из участников не должен иметь возможности получить больше информации, чем им предписано.
  • Корректность. Каждый участник должен гарантировано получить верные данные.
  • Гарантия получения информации. У участников не должно быть возможности помешать другим участников получить выходные данные.

Пример решения проблемы миллионеров

Пусть миллионеры Алиса и Боб хотят выяснить, чьё состояние больше, не разглашая точную сумму своих состояний. Для определённости предположим, что у Алисы имеется i миллионов, а у Боба — j, где 1<i и j<10. Для начала Алисе и Бобу понадобится надёжная криптосистема с открытым ключом, например, RSA. Пусть Ea — произвольная функция шифрования для ключа a, а Da — функция расшифрования с закрытым ключом для открытого ключа a. Пусть a — открытый ключ Алисы. Тогда протокол выглядит так:

  • Боб выбирает случайное целое число x из N бит и конфиденциально считает k=Ea(x);
  • Боб посылает Алисе число k-j+1;
  • Алиса конфиденциально считает значения yu=Da(k-j+u) для u=1,2,…,10;
  • Алиса выбирает случайное простое число p из N/2 бит так, чтобы числа zu=yu mod(p) отличались по меньшей мере на 2 по модулю p для всех u и посылает число p Бобу;
  • Алиса посылает числа z1, z2, …, zi с последующими числами zi+1+1, …, z10+1; числа берутся по модулю p;
  • Боб, который знает, сколько у него денег (j), сравнивает число под номером j с числом x mod p, выбранном на первом шаге, и, если они равны, то Боб делает вывод о том, что i ⩾ j, и i < j в противном случае;
  • Боб сообщает результат Алисе.
  • Видно, что протокол позволяет однозначно определить, чьё состояние больше, и при этом участники не могут узнать состояния друг друга.

    Реализации

    Существует два различных подхода к реализации протокола. Первый подход обычно основан на разделении секрета и работает на представлении вычисляемой функции в виде арифметической схемы (англ. arithmetic circuit), как, например, в протоколах BGW (Ben-Or, Goldwasser и Wigderson) и CCD (Chaum, Crepeau и Damgard). Этот подход обычно применяется тогда, когда известно, что большинство участников честные (что возможно только в том случае, когда число участников больше двух). Другой подход представляет функцию в виде логической схемы. Этот подход был использован Эндрю Яо при построении искажённой схемы (англ. garbled circuit), а также в протоколе GMW (Goldreich, Micali и Wigderson).

    Метод с применением арифметической схемы лучше подходит для выполнения операций сложения и умножения (где у участников есть доли секрета, и воссоздать секрет можно только в случае получения информации от каждого из участников), но плохо подходит для выполнения операций сравнения. Этот подход достиг большого успеха в проекте «SIMAP».

    Метод с использованием логической схемы выполняет операции сложения и умножения с меньшей эффективностью, но легко может выполнять бинарные операции, такие как сравнения. Этот второй подход, на котором основывается система Эндрю Яо для случая двух участников, был реализован Малкхи в системе честной игры (англ. fairplay system). Эта система также предоставляет возможность реализовать необходимую функциональность, представленную высокоуровневым языком программирования в виде логического контура, который потом интерпретируется средой выполнения и безопасно выполняется. Также существует система «FairplayMP», являющаяся расширением «Fairplay» на случай более чем двух участников. Значительным преимуществом основанных на методе систем с логическими схемами является то, что они выполняются за постоянное число обменов информацией, в то время как преимуществом систем, основанных на арифметических схемах, является способность очень быстро выполнять арифметические операции (сложение и умножение).

    Пример протокола

    Для простоты допустим, что в вычислении участвуют два участника, то есть, N=2, и участникам нужно посчитать функцию F.

    • Представим функцию F в виде логической схемы, то есть, представим входные данные функции F в двоичном виде, а саму функцию реализуем с помощью операций AND, OR и NOT. Тогда на вход логической схемы подаются биты всех аргументов функции F, а сама схема состоит из логических вентилей AND, OR и NOT, и на выходе выдаёт результат функции F в двоичном формате.
    • Участник p1 генерирует для каждого провода логической схемы два различных случайных числа k0 u k1. Числа представляют шифрованные ноль и единицу в этом проводе соответственно.
    • Участник p1 создаёт для каждой схемы зашифрованную таблицу вычисления. Для бинарного вентиля OR такая таблица будет выглядеть следующим образом:

    Здесь E k ( x ) {displaystyle E_{k}(x)} означает результат шифрования значения x ключом k, а D k ( y ) {displaystyle D_{k}(y)} — соответственно расшифровка шифротекста y ключом k. Следует выбрать симметричную схему шифрования, обладающую одним дополнительным свойством: при попытке расшифровать текст с неправильным ключом алгоритм возвращает ошибку.

    Смысл этой таблицы таков: если мы знаем зашифрованные значения сигнала k1 u k2 на входных проводах вентиля w1 u w2 соответственно, то мы можем вычислить зашифрованное же значение сигнала, вычислив для всех i=1…4 значение d i = D k 2 ( D k 1 ( c i ) ) {displaystyle d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))} . В трёх случаях из четырёх должна возникнуть ошибка, а в оставшемся четвёртом мы получим зашифрованное значение k3 сигнала на выходе вентиля.

    • Участник p1 передаёт логическую схему и зашифрованные таблицы вычисления для всех схем участнику p2.
    • Участник p1 передаёт участнику p2 зашифрованные значения входных сигналов для тех входов, которые соответствуют входным данным участника p1.
    • Для каждого входного провода wi соответствующего входным данным p2, участник p1 передаёт участнику p2 с помощью протокола забывчивой передачи число k i b i {displaystyle k_{i}^{b_{i}}} , где bi — значение бита тайных входных данных участника p2. При такой передаче участник p1 не узнает значения bi. Так как для каждого провода ранее были случайным образом выбраны свои случайные числа, являющиеся нулём и единицей, то участник p2 не сможет узнать, какое число является нулём, а какое — единицей для входных проводов участника p1, а значит и не сможет узнать входные данные участника p1.
    • Теперь у участника p2 есть зашифрованная логическая схема и зашифрованные значения всех входных проводов. Он вычисляет в зашифрованном виде (как было описано выше) все вентили схемы друг за другом и затем передаёт зашифрованный результат участнику p1.
    • Участник p1 расшифровывает результат и сообщает его участнику p2.

    Используемые протоколы

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

    Практическое применение

    • Электронное голосование. Например, каждый участник может проголосовать за или против, тогда результатом голосования n участников будет функция F(x1, …,xn), где xi может принимать значения 0 (против) и 1 (за).
    • Электронные аукционы. Каждый участник предлагает цену xi, и функция F(x1, …,xn) возвращает номер максимального xi.
    • Статистика. Допустим, студенты хотят узнать лучшую или среднюю оценку, не показывая оценки друг другу.
    • Базы данных. Например, пусть пользователь хочет выполнить запрос к базе данных и получить ответ, не раскрывая запроса. Владелец сервера с базой данных хочет, чтобы при запросах никакая информация, кроме ответа на запрос, не попадала к пользователю. В этом случае участниками протокола конфиденциального вычисления будет как пользователь, так и сервер.
    • Распределённый центр сертификации. Допустим нужно создать центр сертификации, который будет выдавать сертификаты пользователям, подписывая их каким-нибудь секретным ключом. Для защиты ключа ключ можно поделить между несколькими серверами таким образом, чтобы каждый сервер хранил свою часть ключа. Тогда возникнет проблема: как выполнить криптографическую операцию (в данном примере выдачу подписи), не передавая все части ключа на один компьютер. Эта проблема решается с помощью протокола конфиденциального вычисления, где входными данными для функции конфиденциального вычисления являются части ключа и подписываемое сообщение, а выходные данные представляют собой подписанное сообщение.


    Имя:*
    E-Mail:
    Комментарий: