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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Требования к безопасности[править | править код]

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

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

Пример решения проблемы миллионеров[править | править код]

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

  1. Боб выбирает случайное целое число x из N бит и конфиденциально считает k=Ea(x);
  2. Боб посылает Алисе число k-j+1;
  3. Алиса конфиденциально считает значения yu=Da(k-j+u) для u=1,2,…,10;
  4. Алиса выбирает случайное простое число p из N/2 бит так, чтобы числа zu=yu mod(p) отличались по меньшей мере на 2 по модулю p для всех u и посылает число p Бобу;
  5. Алиса посылает числа z1, z2, …, zi с последующими числами zi+1+1, …, z10+1; числа берутся по модулю p;
  6. Боб, который знает, сколько у него денег (j), сравнивает число под номером j с числом x, выбранном на первом шаге, и, если они равны, то Боб делает вывод о том, что 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 в двоичном формате.
  • Участник p1 генерирует для каждого провода логической схемы два различных случайных числа k0 u k1. Числа представляют шифрованные ноль и единицу в этом проводе соответственно.
  • Участник p1 создаёт для каждого контура зашифрованную таблицу вычисления. Для бинарного вентиля OR такая таблица будет выглядеть следующим образом:
Входной провод w1 Входной провод w2 Выходной провод w3 Зашифрованная таблица вычисления

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

Смысл этой таблицы таков: если мы знаем зашифрованные значения сигнала k1 u k2 на входных проводах вентиля w1 u w2 соответственно, то мы можем вычислить зашифрованное же значение сигнала, вычислив для всех i=1…4 значение . В трёх случаях из четырёх должна возникнуть ошибка, а в оставшемся четвёртом мы получим зашифрованное значение k3 сигнала на выходе вентиля.

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

Используемые протоколы[править | править код]

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

Практическое применение[править | править код]

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

Примечания[править | править код]

  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