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

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

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

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

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

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

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

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

Пусть миллионеры Алиса и Боб хотят выяснить, чьё состояние больше, не разглашая точную сумму своих состояний. Для определённости предположим, что у Алисы имеется i миллионов, а у Боба — j, где 1<i и j<10. Для начала Алисе и Бобу понадобится надёжная криптосистема с открытым ключом, например, RSA^[3]. Пусть 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)^[4] и CCD (Chaum, Crepeau и Damgard)^[5]. Этот подход обычно применяется тогда, когда известно, что большинство участников честные (что возможно только в том случае, когда число участников больше двух). Другой подход представляет функцию в виде логической схемы. Этот подход был использован Эндрю Яо при построении искажённой схемы (англ. garbled circuit)^[6], а также в протоколе GMW (Goldreich, Micali и Wigderson)^[7].

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

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

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

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

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

Входной провод w1	Входной провод w2	Выходной провод w3	Зашифрованная таблица вычисления
${\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₂.

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

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

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

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

Примечания

1. Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160—164
2. Yehuda Lindell, Benny Pinkas: A Proof of Yao’s Protocol for Secure Two-Party Computation, Cryptology ePrint Archive, Report 2004/175
3. Solution to the Millionaire’s Problem Архивировано 19 мая 2008 года.
4. M. Ben-Or, S. Goldwasser and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In 20th STOC, 1-10, 1988.
5. P. Bogetoft, D.L. Christensen, I.Damgard, M. Geisler, T. Jakobsen, M. Kroigaard, J.D. Nielsen, J.B. Nielsen, K. Nielsen, J.Pagter, M. Schwartzbach and T. Toft. Secure multiparty computation goes life. In Financial Cryptography and Data Security — FC 2009
6. A. Yao. How to generate and exchange secrets. In 27th FOCS, 162—167, 1986.
7. Goldreich, S. Micali and A. Wigderson. How to play any mental game — A completeness theorem for protocols with honest majority. In 19th STOC, 218—229, 1987.
8. P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. and T. Toft. A practical implementation of secure auctions based on multiparty integer computation. In Financial Cryptography and Data Security — FC 2006, Springer-Verlag LNCS 4107, 142—147, 2006.
9. D. Malkhi, N. Nisan, B. Pinkas and Y. Sella. Fairplay — a secure two-party computation system. In Proc. of 13th USENIX Security Symposium, 2004.
10. A. Ben-David, N. Nisan and B. Pinkas. FairplayMP: a system for secure multi-party computation. In Computer and Communications Security — CCS 2008, ACM, 257—266, 2008.
11. Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (Print) 1611-3349 (Online), ISBN 978-3-642-02616-4, DOI 10.1007/978-3-642-02617-1
12. Rashid Sheikh, Brijesh Kumar and Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (Online),Vol.6, No.2, Nov. 2009