Общая задача многосторонних вычислений

From CryptoWiki
Jump to: navigation, search

Contents

Постановка задачи

Рисунок 1 — Система многосторонних вычислений

Допустим, в многостороннем вычислении участвует p1, p2, ..., pn участников, у каждого из которых имеются входные слова x1, x2, ..., xn. Участники хотят вычислить значение общеизвестной функции F от n переменных. Также среди участников могут быть "получестные" участники, которые пытаются получить дополнительную информацию из промежуточных данных, таких как функция F или при помощи собственных входных слов.

На рисунке 1 показана возможная реализация системы многосторонних вычислений. В данной модели, некоторое число участников предоставляет информацию (например, ставки на аукционе). Информация всегда хранится в зашифрованном виде и пять доверенных третьих лиц (ДТЛ) совместно производят необходимые вычисления. Однако, несколько доверенных лиц могут являться "получестными" (выделены красным на рисунке). После проведения всех вычислений выводится результат в незашифрованном виде.

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

Рисунок 2 — Система многосторонних вычислений

Пусть миллионеры Алиса и Боб хотят выяснить, чье состояние больше, не разглашая точную сумму своего состояния. Для определенности предположим, что у Алисы i миллионов, а у Боба j, где 1<i, j<10. Для начала Алисе и Бобу понадобится надежная криптосистема с открытым ключом. Пусть 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. Боб сообщает результат Алисе.

Видно, что протокол позволяет однозначно определить, чье состояние больше, и при этом участники не могут узнать суммы состояний друг друга. Существуют два различных решения проблемы миллионеров основанных на разных принципах. Первое решение предполагает, что Алиса и Боб владеют собственными односторонними функциями Ea и Eb, которые удовлетворяют свойству коммутативности, т.е. EaEb(x) = EbEa(x). Второе решение использует вероятностный метод шифрования, разработанный Шафи Гольдвассер и Сильвио Микали.

Безопасность многосторонних вычислений

Рассмотрим модель, в которой некоторое подмножество участников находятся под контролем нарушителя и желают атаковать протокол многосторонних вычислений. Безопасные протоколы должны противостоять подобного рода атакам. Чтобы доказать безопасность протокола, необходимо дать точное определение безопасности многосторонних вычислений. Однако, к безопасности протоколов многосторонних вычислений могут предъявляться различные требования в зависимости от задач, решаемых при помощи многосторонних вычислений. Ниже приведены основные требования безопасности, которые подходят практически ко всем задачам многосторонних вычислений.

Конфиденциальность

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

Корректность

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

Независимость входных данных

Участники многосторонних вычислений должны выбирать входные данные независимо друг от друга. Это свойство имеет решающее значение в закрытых аукционах, где торги держатся в секрете, и стороны должны делать ставки независимо от других. Однако, независимость входных данных не подразумевает конфиденциальности. Данное требование необходимо для случаев, когда злоумышленник может создать зашифрованные данные, не зная исходного значения. Например, на аукционе при известном зашифрованном значении ставки 100$, злоумышленник может создать зашифрованное значение ставки размером 101$.

Гарантированное получение выходных данных

Ни у одного из участников не должно быть возможности помешать кому-либо из остальных участников получить выходные данные. Другими словами, злоумышленник не должен иметь возможности нарушить вычисление путем проведения атаки "Отказ в обслуживании".

Практическое применение многосторонних вычислений

Рассмотрим следующее примеры:

  1. Алиса предполагает, что она может иметь некую генетическую болезнь, и она хочет узнать диагноз. Она также знает, что Боб имеет базу данных, содержащую образцы ДНК различных заболеваний. После того, как Алиса получает образец своей ДНК-последовательности, она посылает его Бобу, который раскроет Алисе диагноз. Тем не менее, если Алиса обеспокоена насчет конфиденциальности своей личной жизни, описанный выше процесс не является приемлемым, поскольку он позволяет Бобу узнать ДНК Алисы, а также ее диагноз.
  2. После дорогостоящего исследования рынка, компания А решила, что расширение деятельности компании в некотором регионе принесет огромную прибыль. Однако известно, что ее конкурент, компания B, собирается укрепить свои позиции в неизвестном компании А регионе. Стратегически, А и В не хотят конкурировать в одном и том же регионе, поэтому хотят знать, перекрываются ли области их влияния, при этом не передавая информацию о своих намерениях (обе компании имеют дорогостоящую информацию о рынке. Например: зная информацию, что А и В заинтересованы в аренде одного и того же места, компания недвижимости может повысить цену в ходе переговоров). Таким образом, им нужен способ решения проблемы, который позволяет сохранить конфиденциальность важной информации.
  3. Две финансовые организации планируют совместно работать над проектом для получения прибыли. Каждая компания хотела бы, чтобы ее требования были удовлетворены (как правило, они моделируются в виде линейных уравнений или линейных неравенств). Однако требования каждой из организаций могут включать в себя конфиденциальную информацию, например важные данные о проектах заказчика. Ни одна из организаций не намерена раскрывать свои требования другой стороне, или даже некоторой «доверенной» третьей стороне. Как они могли бы сотрудничать по этому проекту, сохраняя при этом конфиденциальность индивидуальной информации?

Рассмотренные выше примеры являются типичными задачами, решить которые позволяют многосторонние вычисления: две или более стороны хотят провести вычисления на основе личных входных данных, и каждый нуждается в их конфиденциальности.

Также многосторонние вычисления используются в следующих областях:

  • Электронное голосование
  • Выборы в сети Интернет
  • Частные торги и аукционы
  • Защита анализируемых данных
  • Обмен подписями или функциями дешифрования

Пример реализации многосторонних вычислений

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

Исходный код демонстрационной программы: File:MPC demo src.zip

Исполняемые файлы демонстрационной программы: File:MPC demo.zip

Глоссарий

Библиографический указатель

Перейти к списку литературы

Вернуться на главную страницу

Вернуться к оглавлению


Махаев Я.Э.

Огуло В.И.

2014

Назад