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

Поделись знанием:
Перейти к: навигация, поиск

В криптографии протокол конфиденциального вычисления (также безопасное/защищенное/тайное многостороннее вычисление, англ. 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 Зашифрованная таблица вычисления
<math>k_1^0</math> <math>k_2^0</math> <math>k_3^0</math> <math>c_1 = E_{k_1^0}(E_{k_2^0}(k_3^0))</math>
<math>k_1^0</math> <math>k_2^1</math> <math>k_3^1</math> <math>c_2 = E_{k_1^0}(E_{k_2^1}(k_3^1))</math>
<math>k_1^1</math> <math>k_2^0</math> <math>k_3^1</math> <math>c_3 = E_{k_1^1}(E_{k_2^0}(k_3^1))</math>
<math>k_1^1</math> <math>k_2^1</math> <math>k_3^1</math> <math>c_4 = E_{k_1^1}(E_{k_2^1}(k_3^1))</math>

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

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

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

Отрывок, характеризующий Протокол конфиденциального вычисления

– Хорошо, хорошо, – проговорил офицер с угрозой, и, повернув лошадь, поехал прочь рысью, трясясь на седле.
– Собака на забог'е, живая собака на забог'е, – сказал Денисов ему вслед – высшую насмешку кавалериста над верховым пехотным, и, подъехав к Ростову, расхохотался.
– Отбил у пехоты, отбил силой транспорт! – сказал он. – Что ж, не с голоду же издыхать людям?
Повозки, которые подъехали к гусарам были назначены в пехотный полк, но, известившись через Лаврушку, что этот транспорт идет один, Денисов с гусарами силой отбил его. Солдатам раздали сухарей в волю, поделились даже с другими эскадронами.
На другой день, полковой командир позвал к себе Денисова и сказал ему, закрыв раскрытыми пальцами глаза: «Я на это смотрю вот так, я ничего не знаю и дела не начну; но советую съездить в штаб и там, в провиантском ведомстве уладить это дело, и, если возможно, расписаться, что получили столько то провианту; в противном случае, требованье записано на пехотный полк: дело поднимется и может кончиться дурно».
Денисов прямо от полкового командира поехал в штаб, с искренним желанием исполнить его совет. Вечером он возвратился в свою землянку в таком положении, в котором Ростов еще никогда не видал своего друга. Денисов не мог говорить и задыхался. Когда Ростов спрашивал его, что с ним, он только хриплым и слабым голосом произносил непонятные ругательства и угрозы…
Испуганный положением Денисова, Ростов предлагал ему раздеться, выпить воды и послал за лекарем.
– Меня за г'азбой судить – ох! Дай еще воды – пускай судят, а буду, всегда буду подлецов бить, и госудаг'ю скажу. Льду дайте, – приговаривал он.
Пришедший полковой лекарь сказал, что необходимо пустить кровь. Глубокая тарелка черной крови вышла из мохнатой руки Денисова, и тогда только он был в состоянии рассказать все, что с ним было.
– Приезжаю, – рассказывал Денисов. – «Ну, где у вас тут начальник?» Показали. Подождать не угодно ли. «У меня служба, я зa 30 верст приехал, мне ждать некогда, доложи». Хорошо, выходит этот обер вор: тоже вздумал учить меня: Это разбой! – «Разбой, говорю, не тот делает, кто берет провиант, чтоб кормить своих солдат, а тот кто берет его, чтоб класть в карман!» Так не угодно ли молчать. «Хорошо». Распишитесь, говорит, у комиссионера, а дело ваше передастся по команде. Прихожу к комиссионеру. Вхожу – за столом… Кто же?! Нет, ты подумай!…Кто же нас голодом морит, – закричал Денисов, ударяя кулаком больной руки по столу, так крепко, что стол чуть не упал и стаканы поскакали на нем, – Телянин!! «Как, ты нас с голоду моришь?!» Раз, раз по морде, ловко так пришлось… «А… распротакой сякой и… начал катать. Зато натешился, могу сказать, – кричал Денисов, радостно и злобно из под черных усов оскаливая свои белые зубы. – Я бы убил его, кабы не отняли.
– Да что ж ты кричишь, успокойся, – говорил Ростов: – вот опять кровь пошла. Постой же, перебинтовать надо. Денисова перебинтовали и уложили спать. На другой день он проснулся веселый и спокойный. Но в полдень адъютант полка с серьезным и печальным лицом пришел в общую землянку Денисова и Ростова и с прискорбием показал форменную бумагу к майору Денисову от полкового командира, в которой делались запросы о вчерашнем происшествии. Адъютант сообщил, что дело должно принять весьма дурной оборот, что назначена военно судная комиссия и что при настоящей строгости касательно мародерства и своевольства войск, в счастливом случае, дело может кончиться разжалованьем.
Дело представлялось со стороны обиженных в таком виде, что, после отбития транспорта, майор Денисов, без всякого вызова, в пьяном виде явился к обер провиантмейстеру, назвал его вором, угрожал побоями и когда был выведен вон, то бросился в канцелярию, избил двух чиновников и одному вывихнул руку.
Денисов, на новые вопросы Ростова, смеясь сказал, что, кажется, тут точно другой какой то подвернулся, но что всё это вздор, пустяки, что он и не думает бояться никаких судов, и что ежели эти подлецы осмелятся задрать его, он им ответит так, что они будут помнить.
Денисов говорил пренебрежительно о всем этом деле; но Ростов знал его слишком хорошо, чтобы не заметить, что он в душе (скрывая это от других) боялся суда и мучился этим делом, которое, очевидно, должно было иметь дурные последствия. Каждый день стали приходить бумаги запросы, требования к суду, и первого мая предписано было Денисову сдать старшему по себе эскадрон и явиться в штаб девизии для объяснений по делу о буйстве в провиантской комиссии. Накануне этого дня Платов делал рекогносцировку неприятеля с двумя казачьими полками и двумя эскадронами гусар. Денисов, как всегда, выехал вперед цепи, щеголяя своей храбростью. Одна из пуль, пущенных французскими стрелками, попала ему в мякоть верхней части ноги. Может быть, в другое время Денисов с такой легкой раной не уехал бы от полка, но теперь он воспользовался этим случаем, отказался от явки в дивизию и уехал в госпиталь.


В июне месяце произошло Фридландское сражение, в котором не участвовали павлоградцы, и вслед за ним объявлено было перемирие. Ростов, тяжело чувствовавший отсутствие своего друга, не имея со времени его отъезда никаких известий о нем и беспокоясь о ходе его дела и раны, воспользовался перемирием и отпросился в госпиталь проведать Денисова.
Госпиталь находился в маленьком прусском местечке, два раза разоренном русскими и французскими войсками. Именно потому, что это было летом, когда в поле было так хорошо, местечко это с своими разломанными крышами и заборами и своими загаженными улицами, оборванными жителями и пьяными и больными солдатами, бродившими по нем, представляло особенно мрачное зрелище.
В каменном доме, на дворе с остатками разобранного забора, выбитыми частью рамами и стеклами, помещался госпиталь. Несколько перевязанных, бледных и опухших солдат ходили и сидели на дворе на солнушке.
Как только Ростов вошел в двери дома, его обхватил запах гниющего тела и больницы. На лестнице он встретил военного русского доктора с сигарою во рту. За доктором шел русский фельдшер.
– Не могу же я разорваться, – говорил доктор; – приходи вечерком к Макару Алексеевичу, я там буду. – Фельдшер что то еще спросил у него.
– Э! делай как знаешь! Разве не всё равно? – Доктор увидал подымающегося на лестницу Ростова.
– Вы зачем, ваше благородие? – сказал доктор. – Вы зачем? Или пуля вас не брала, так вы тифу набраться хотите? Тут, батюшка, дом прокаженных.
– Отчего? – спросил Ростов.
– Тиф, батюшка. Кто ни взойдет – смерть. Только мы двое с Макеевым (он указал на фельдшера) тут трепемся. Тут уж нашего брата докторов человек пять перемерло. Как поступит новенький, через недельку готов, – с видимым удовольствием сказал доктор. – Прусских докторов вызывали, так не любят союзники то наши.
Ростов объяснил ему, что он желал видеть здесь лежащего гусарского майора Денисова.
– Не знаю, не ведаю, батюшка. Ведь вы подумайте, у меня на одного три госпиталя, 400 больных слишком! Еще хорошо, прусские дамы благодетельницы нам кофе и корпию присылают по два фунта в месяц, а то бы пропали. – Он засмеялся. – 400, батюшка; а мне всё новеньких присылают. Ведь 400 есть? А? – обратился он к фельдшеру.
Фельдшер имел измученный вид. Он, видимо, с досадой дожидался, скоро ли уйдет заболтавшийся доктор.
– Майор Денисов, – повторил Ростов; – он под Молитеном ранен был.
– Кажется, умер. А, Макеев? – равнодушно спросил доктор у фельдшера.
Фельдшер однако не подтвердил слов доктора.
– Что он такой длинный, рыжеватый? – спросил доктор.
Ростов описал наружность Денисова.
– Был, был такой, – как бы радостно проговорил доктор, – этот должно быть умер, а впрочем я справлюсь, у меня списки были. Есть у тебя, Макеев?
– Списки у Макара Алексеича, – сказал фельдшер. – А пожалуйте в офицерские палаты, там сами увидите, – прибавил он, обращаясь к Ростову.
– Эх, лучше не ходить, батюшка, – сказал доктор: – а то как бы сами тут не остались. – Но Ростов откланялся доктору и попросил фельдшера проводить его.
– Не пенять же чур на меня, – прокричал доктор из под лестницы.
Ростов с фельдшером вошли в коридор. Больничный запах был так силен в этом темном коридоре, что Ростов схватился зa нос и должен был остановиться, чтобы собраться с силами и итти дальше. Направо отворилась дверь, и оттуда высунулся на костылях худой, желтый человек, босой и в одном белье.
Он, опершись о притолку, блестящими, завистливыми глазами поглядел на проходящих. Заглянув в дверь, Ростов увидал, что больные и раненые лежали там на полу, на соломе и шинелях.
– А можно войти посмотреть? – спросил Ростов.
– Что же смотреть? – сказал фельдшер. Но именно потому что фельдшер очевидно не желал впустить туда, Ростов вошел в солдатские палаты. Запах, к которому он уже успел придышаться в коридоре, здесь был еще сильнее. Запах этот здесь несколько изменился; он был резче, и чувствительно было, что отсюда то именно он и происходил.
В длинной комнате, ярко освещенной солнцем в большие окна, в два ряда, головами к стенам и оставляя проход по середине, лежали больные и раненые. Большая часть из них были в забытьи и не обратили вниманья на вошедших. Те, которые были в памяти, все приподнялись или подняли свои худые, желтые лица, и все с одним и тем же выражением надежды на помощь, упрека и зависти к чужому здоровью, не спуская глаз, смотрели на Ростова. Ростов вышел на середину комнаты, заглянул в соседние двери комнат с растворенными дверями, и с обеих сторон увидал то же самое. Он остановился, молча оглядываясь вокруг себя. Он никак не ожидал видеть это. Перед самым им лежал почти поперек середняго прохода, на голом полу, больной, вероятно казак, потому что волосы его были обстрижены в скобку. Казак этот лежал навзничь, раскинув огромные руки и ноги. Лицо его было багрово красно, глаза совершенно закачены, так что видны были одни белки, и на босых ногах его и на руках, еще красных, жилы напружились как веревки. Он стукнулся затылком о пол и что то хрипло проговорил и стал повторять это слово. Ростов прислушался к тому, что он говорил, и разобрал повторяемое им слово. Слово это было: испить – пить – испить! Ростов оглянулся, отыскивая того, кто бы мог уложить на место этого больного и дать ему воды.
– Кто тут ходит за больными? – спросил он фельдшера. В это время из соседней комнаты вышел фурштадский солдат, больничный служитель, и отбивая шаг вытянулся перед Ростовым.
– Здравия желаю, ваше высокоблагородие! – прокричал этот солдат, выкатывая глаза на Ростова и, очевидно, принимая его за больничное начальство.
– Убери же его, дай ему воды, – сказал Ростов, указывая на казака.
– Слушаю, ваше высокоблагородие, – с удовольствием проговорил солдат, еще старательнее выкатывая глаза и вытягиваясь, но не трогаясь с места.
– Нет, тут ничего не сделаешь, – подумал Ростов, опустив глаза, и хотел уже выходить, но с правой стороны он чувствовал устремленный на себя значительный взгляд и оглянулся на него. Почти в самом углу на шинели сидел с желтым, как скелет, худым, строгим лицом и небритой седой бородой, старый солдат и упорно смотрел на Ростова. С одной стороны, сосед старого солдата что то шептал ему, указывая на Ростова. Ростов понял, что старик намерен о чем то просить его. Он подошел ближе и увидал, что у старика была согнута только одна нога, а другой совсем не было выше колена. Другой сосед старика, неподвижно лежавший с закинутой головой, довольно далеко от него, был молодой солдат с восковой бледностью на курносом, покрытом еще веснушками, лице и с закаченными под веки глазами. Ростов поглядел на курносого солдата, и мороз пробежал по его спине.