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

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

В конфиденциальном вычислении участвуют N участников p ₁ , p ₂ , …, p _N . У каждого участника есть тайные входные данные d ₁ , d ₂ , …, d _N соответственно. Участники хотят найти значение F(d ₁ , d ₂ , …, d _N ) , где F — известная всем участникам вычислимая функция от N аргументов. Допускается, что среди участников будут получестные нарушители , то есть те, которые верно следуют протоколу, но пытаются получить дополнительную информацию из любых промежуточных данных.

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

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

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

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

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

1. Боб выбирает случайное целое число x из N бит и конфиденциально считает k=E _a (x) ;
2. Боб посылает Алисе число k-j+1 ;
3. Алиса конфиденциально считает значения y _u =D _a (k-j+u) для u=1,2,…,10 ;
4. Алиса выбирает случайное простое число p из N/2 бит так, чтобы числа z _u =y _u mod(p) отличались по меньшей мере на 2 по модулю p для всех u и посылает число p Бобу;
5. Алиса посылает числа z ₁ , z ₂ , …, z _i с последующими числами z _i+1 +1, …, z ₁₀ +1 ; числа берутся по модулю p;
6. Боб, который знает, сколько у него денег ( j ), сравнивает число под номером j с числом x mod p , выбранном на первом шаге, и, если они равны, то Боб делает вывод о том, что i ⩾ j , и i < j в противном случае;
7. Боб сообщает результат Алисе.

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

Реализации

Существует два различных подхода к реализации протокола. Первый подход обычно основан на разделении секрета и работает на представлении вычисляемой функции в виде ( англ. 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 в двоичном формате.
• Участник p ₁ генерирует для каждого провода логической схемы два различных случайных числа k ⁰ u k ¹ . Числа представляют шифрованные ноль и единицу в этом проводе соответственно.
• Участник p ₁ создаёт для каждой схемы зашифрованную таблицу вычисления. Для бинарного вентиля OR такая таблица будет выглядеть следующим образом:

Входной провод w 1	Входной провод w 2	Выходной провод w 3	Зашифрованная таблица вычисления
${\displaystyle k_{1}^{0}}$	${\displaystyle k_{2}^{0}}$	${\displaystyle k_{3}^{0}}$	${\displaystyle c_{1}=E_{k_{1}^{0}}(E_{k_{2}^{0}}(k_{3}^{0}))}$
${\displaystyle k_{1}^{0}}$	${\displaystyle k_{2}^{1}}$	${\displaystyle k_{3}^{1}}$	${\displaystyle c_{2}=E_{k_{1}^{0}}(E_{k_{2}^{1}}(k_{3}^{1}))}$
${\displaystyle k_{1}^{1}}$	${\displaystyle k_{2}^{0}}$	${\displaystyle k_{3}^{1}}$	${\displaystyle c_{3}=E_{k_{1}^{1}}(E_{k_{2}^{0}}(k_{3}^{1}))}$
${\displaystyle k_{1}^{1}}$	${\displaystyle k_{2}^{1}}$	${\displaystyle k_{3}^{1}}$	${\displaystyle c_{4}=E_{k_{1}^{1}}(E_{k_{2}^{1}}(k_{3}^{1}))}$

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

Смысл этой таблицы таков: если мы знаем зашифрованные значения сигнала k ₁ u k ₂ на входных проводах вентиля w ₁ u w ₂ соответственно, то мы можем вычислить зашифрованное же значение сигнала, вычислив для всех i=1…4 значение ${\displaystyle d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))}$ . В трёх случаях из четырёх должна возникнуть ошибка, а в оставшемся четвёртом мы получим зашифрованное значение k ₃ сигнала на выходе вентиля.

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

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

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

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

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

Примечания