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

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

В криптографии протокол конфиденциального вычисления (также безопасное/защищенное/тайное многостороннее вычисление, англ. 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 с числом x, выбранном на первом шаге, и если они равны, то Боб делает вывод о том, что i ⩾ j, и i < j в противном случае.
  7. Боб сообщает результат Алисе.

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


Реализации[править | править вики-текст]

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

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

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

Пример протокола[править | править вики-текст]

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

  • Представим функцию F в виде логического контура, то есть представим входные данные функции F в двоичном виде, а саму функцию реализуем с помощью операций AND, OR и NOT. Тогда на вход логического контура подаются биты всех аргументов функции F,а сам контур состоит из логических гейтов AND, OR и NOT, и на выходе выдаёт результат функции F в двоичном формате.
  • Участник p1 генерирует для каждого провода логической схемы два различных случайных числа k0 u k1: они представляют шифрованные ноль и единицу в этом проводе соответственно.
  • Участник p1 создаёт для каждого контура зашифрованную таблицу вычисления. Для бинарного гейта OR такая таблица будет выглядеть следующим образом:
Входной провод w1 Входной провод w2 Выходной провод w3 Зашифрованая таблица вычисления
k_1^0 k_2^0 k_3^0 c_1 = E_{k_1^0}(E_{k_2^0}(k_3^0))
k_1^0 k_2^1 k_3^1 c_2 = E_{k_1^0}(E_{k_2^1}(k_3^1))
k_1^1 k_2^0 k_3^1 c_3 = E_{k_1^1}(E_{k_2^0}(k_3^1))
k_1^1 k_2^1 k_3^1 c_4 = E_{k_1^1}(E_{k_2^1}(k_3^1))

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

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

  • Участник p1 передаёт логический контур и зашифрованные таблицы вычисления для всех контуров участнику p2.
  • Участник p1 передаёт участнику p2 зашифрованные значения сигналов входных проводов для тех входов, которые соответствуют входным данным участника p1.
  • Для каждого входного провода wi соответствующего входным данным p2, участник p1 передаёт участнику p2 с помощью протокола забывчивой передачи число k_i^{b_i}, где 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
  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