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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:02, 30 июня 2016.
Secure Computation on the Web: Computing without Simultaneous Interaction
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Shai Halevi[@: 1],
Chih-Yehuda Lindell[@: 2] and Benny Pinkas[@: 3]
Опубликован 2010 г.
Сайт Department of Computer Science
Перевели Stanislav Bogatyrev
Год перевода 2016 г.
Скачать оригинал


Аннотация. Защищенные вычисления позволяют взаимно подозрительным участникам вычислить совместную функцию на основе их личных входных данных, предоставляя мощные гарантии безопасности. Однако, его использование на практике ограничено. Наша позиция - одна из причин для этого состоит в том, что модель вычислений в сети не подходит к типу шаблонов связи, необходимых для защищенных вычислений. Конкретнее – во многих веб-сценариях клиенты независимо подключаются к серверам, взаимодействуют с ними и отключаются. Это исключает использования протоколов защитных вычислений, требующих одновременного взаимодействия всех участников. Мы приступаем к изучению защищенных вычислений в модели “клиент-сервер”, где каждый клиент подсоединяется к серверу единожды и взаимодействует с ним, без необходимости подключения какого-либо другого клиента одновременно. Мы укажем некоторые присущие этой модели ограничения и дадим определения, которые опишут то, что может быть сделано. Так же мы представим основной результат осуществления и несколько действительно удобных протоколов для некоторого числа интересующих нас функций. Все наши протоколы базируются на стандартных предположениях, и мы достигли безопасности как в случае модели пассивно-честного (англ. semi-honest) противника, так и действительно вредоносного (англ. malicious).

Введение

Веб-серверы являются доминирующим средством коммуникации в современном обществе. В качестве примера можно привести пользователей социальных сетей, которые взаимодействуют, посылая сообщения на веб-серверы их сети, чтобы "написать на стене" своих друзей (и эти серверы отправляют сообщения к получателям); программное обеспечение различных комиссий, использующих веб-системы для распространения своих отзывов и обсуждений; читателей, участвующие в онлайн-опросах на сайтах газет; участников онлайн аукционов; избирателей, голосующих онлайн и т.д. Во многих случаях, прямое взаимодействие между пользователями невозможно просто потому, что они оффлайн большую часть времени. Сегодня почти во всех системах веб-сервер служит не только средством коммуникации, но и доверенной стороной.

Серверы получают всю информацию от пользователей и делает всю обработку, и пользователи доверяют им использовать их информацию только для нужд приложения (или согласно “политике конфиденциальности” сайта). Это может быть целесообразным в некоторых случаях, но в большинстве случаев у пользователей нет причин доверять серверу или друг другу, и действительно – известно много случаев, когда это доверие было неоправданным[1]

Естественным подходом к устранению этой проблемы является использование криптографических методов устранения доверенных сторон. В самом деле, в последние три десятка лет виден колоссальный объём работы в рамках научно-исследовательского сообщества криптографии (под общим названием защищенные многосторонние вычисления, так же протокол конфиденциального вычисления, secure multi-party computation), посвященный нахождению различных путей преобразования систем, которые полагаются доверенных лиц в системах, которые им не нужны (см. пример в [2], глава 7).

В самом деле, с клиентской стороны, работающей на Web 2.0, имеется огромная масса сторон с серьезными вычислительными платформами и противоречивыми интересами, все они хотели бы взаимодействовать друг с другом для выполнения некоторых совместных задач. Кажется, что это идеальные условия для массового развёртывания системы защищенных многочастных вычислений, но на деле такого развёртывания не происходит. Некоторые причины связаны с практическими проблемами браузерной технологии (например, клиент не может убедиться в том, что запустил нужную программу), но здесь мы сосредоточимся на более криптографической причине. В частности, на том факте, что текущие многосторонние протоколы кажутся несовместимыми с коммуникационными моделями нынешних веб-приложений. Большая часть работы с протоколом конфиденциальных вычислений предполагает, что все участники остаются в сети в течение всего процесса вычисления, и большинство решений также полагаются на сильные коммуникационные примитивы, такие как радиопередача. Однако, клиенты в сети подключаются к серверу в разные моменты времени и, как правило, не взаимодействуют друг с другом. Таким образом, нас интересует, можно ли устранить для веб-сервера необходимость быть доверенным участником, даже в этой обстановке слабо связанных сторон, которые отключены от сеты большую часть времени.

Помимо практического интереса, который мы обсуждали выше, многосторонние вычисления в этой модели имеют значительный теоретический интерес. Не совсем ясно, может ли теоретически значимое безопасное вычисление быть достигнуто в условиях, где участники выполняют одно-единственное взаимодействие с ненадежным сервером в различное время (в пассивно-честных или вредоносных условиях). Следовательно, мощность этой модели - естественный теоретический вопрос, требующий рассмотрения.

Отметим сразу, что наивный подход с использованием полностью гомоморфного шифрования[3][4] не решает проблему защищенных вычислений в наших условиях. Это связано с тем, что хотя каждый участник может шифровать его входные данные и вычисление может быть завершено гомоморфно, необходимо дешифровать окончательные шифротексты, предотвращающая при этом расшифровку промежуточных.

Наш вклад

Мы начнём изучение безопасного вычисления со слабо связанных сторон. Мы определим настройки безопасности, и заметим, что в этом случае не всегда возможно достигнуть такого же уровня защищенности как при стандартных условиях защищённых вычислений. Мы формализуем то, что может быть достигнуто в этой модели, и затем представим теоретические и практические конструкции для обоих типов противника - пассивно-честного и вредоносного. Все наши конструкции полагаются на стандартных предположениях (таких как решение Диффи-Хеллмана, англ. Decisional Diffie–Hellman, DDH), и находятся в стандартной модели. Единственным исключением является то, что для нашей практической конструкции и случая вредоносных противников, мы используем случайные оракульные машины для получения практического неинтерактивного нулевого разглашения (англ. zero-knowledge), используя протокол Фиата-Шамира.[5]

Начнём с учёта самых основных настроек сервера с участниками, обозначив их . Каждый участник имеет вход , а остальные участники хотят совместно вычислить функцию (например, узнать сумму входных значений, или их максимум). Для упрощения описания, рассмотрим случай, когда участники общаются с сервером по порядке - первый , затем участник , и так далее вплоть до , и после взаимодействия с каждым сервер в состоянии узнать выходное значение.

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

В первую очередь рассмотрим случай пассивно-честных участников. Легко увидеть, что даже в этой модели протоколы не могут всегда предоставлять одинаковые гарантии безопасности, как стандартные защитные протоколы функций оценки (англ Standard Secure Function Evaluation Protocols, SFE). Например, если последние участников "вступили в сговор" с сервером, то они всегда смогут оценить остаточную функцию на сколь угодно любом количестве входов . Это связано с тем, что эти последние участников должны иметь возможность вычислить для любого возможного вектора их входных значений . Более того, поскольку первые сторон более не участвуют в процессе, ничто не помешает последним просто перезапустить остальные протоколы много раз со входами .

Мы формализуем неотъемлемую утечку в этой модели, вводя понятие однораундового разложения (англ. one-pass decomposition) функции: разложение функции с входами это вектор функций такой, что для всех входов верно, что . Здесь есть промежуточный результат, основанный на входах участников до , а определён как пустая строка. Видно, что каждому протоколу для вычисления в нашей модели соответствует некоторое (возможно, случайное) разложение , поэтому, грубо говоря, мы можем думать о как о состоянии сервера с участником . Однако, как мы увидим, не все разложения эквивалентны: некоторые из них лучше, чем другие (а некоторые и не сравнимы). Поэтому мы разбиваем проблемы защищенных вычислений на (а) нахождение безопасного разложения данной функции и (б) разработку протокола для безопасного вычисления данного разложения.

Хорошие разложения. Хотя любая функция может быть разложена так, как описано выше, некоторые разложения более "интересные" и "естественные". Тривиальным примером служит то, что любая может быть разложена путём отождествления функций и дальнейшим приравниванием . Более интересный пример - функция суммы может быть разложена таким образом, чтобы для каждой соблюдалось равенство . Очевидно, что разложение функции суммы с использованием таких частичных сумм намного лучше, чем её разложение с использованием функции тождества, поскольку оно предоставляет много меньше информации злоумышленнику (в случае поврежденных сервера и участника злоумышленник узнает все входные данные при использовании функции тождества, в отличие от только лишь её частичной суммы).

Мы особенно заинтересованы в минимальном раскрытии (англ minimum-disclosure) разложений , когда несёт не больше информации о входах , чем таблица истинности остаточной функции , описанной выше. Например, легко увидеть, что разложение функции суммы, имеющей все в качестве частичных сумм, в самом деле минимально, потому что для данных и выходного возможно рассчитать частичную сумму . В разделе 2 мы определим понятие минимально раскрытых разложений и опишем множество функций, имещих эффективные minimum-disclosure разложения. Затем, в разделе 4.1 мы опишем практические протоколы для защищенных вычислений некоторых из этих разложений (в модели инфраструктуры открытых ключей, англ. Public Key Infrastructure, PKI). В список функций, которые мы можем обрабатывать таким образом, входят симметричные функций на малых областях (а также некоторые другие функции). Таким образом, например, мы можем построить практический протокол для вычисления референдума, настолько конфиденциальный, насколько это возможно в нашей модели.

Защищенное вычисление любого разложения. Пусть дано специфическое разложение (учитывающее приемлемую утечку, которую мы готовы терпеть при расчёте в нашей модели). Что значит "защищенно вычислить" это разложение для протокола? Интуитивно решив, что есть частичный результат для участника , мы оформляем требование, что эти частичные результаты - единственная вещь, которую могут узнать "плохие" участники.

Во-первых, заметим, что многие из промежуточных результатов могут быть "спрятаны" от нечестных участников. Например, если участники и являются честными, то мы ожидаем, что результаты и останутся скрытыми, даже если нечестный узнает . На самом деле, наше формальное определение требует немного больше: протокол называются защищенным для вычисления данного разложения , если единственной утечкой после последнего честного участника является последний частичный результат. А именно, вид любого набора ненадёжных участников может быть смоделирован, если мы знаем только значение , где - индекс последнего честного участника. Кроме того, если сервер является честным, то ничего, кроме выхода , не обнаружится. (Заметим, что более слабое определение, где плохие участники могут получить все , для которых участник нечестен, по существу, эквивалентно понятию -Hop гомоморфного шифрования[6].

В разделе 5 мы рассмотрим задачу разработки протокола для защищенных вычислений конкретных данных разложений функции . Используя повторно рандомизируемые искаженные схемы, аналогичные Gentry и другим[6], мы покажем, что при предположении Диффи-Хеллмана любое эффективное разложение может быть посчитано защищенно в нашей модели (если доступна инфраструктура открытых ключей). Наш подход упрощает технику из [6], в которой мы используем такие схемы только в сочетании с повторно рандомизируемым шифрованием, в то время как [6] нуждаются также в повторно рандомизируемой забывчивой передаче (англ. Oblivious transfer, OT). Также мы укрепим конструкцию из [6] для того, чтобы справиться с вредоносными участниками. Более подробная информация об этих аспектах - в разделе 5.

Некоторые связанные работы

Некоторые из используемых нами методов аналогичны тем, что использует в своей работе Дэнни Харник и другие[7]. В этой работе они рассматривают параметры многостороннего вычисления, где входы участников включены по одному, с целью минимизации числа забывчивых передач, которые необходимы каждый раз при получении новых входных данных. Конкретно, наши протоколы для симметричных функций напоминают их табличный метод. Другая связанная работа - труд Чоя С.Г. и прочих[8]. Они рассмотрели условия, где участники могут взаимодействовать в фазе установки связи до получения входных данных, и затем они хотят минимизировать онлайн-коммуникацию, при этом сохраняя полную безопасность. Их результаты не применимы к нашей модели, однако лишь потом, что, как мы пояснили, полная безопасность не может быть получена в нашей модели (и это верно даже с учетом интерактивного этапа установки связи).

Однораундовое разложение

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

Определение 1 (Разложение). Пусть - функция переменных (с областью определения и областью значений . Детерминистическим однораундовым разложением (англ. one-pass decomposition) функции называется последовательность функций , такая, что для всех справедливо, что .

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

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

.

Минимально раскрытое разложение

Как было упомянуто выше, некоторые разложения лучше других, а некоторые функции имеют эффективные разложения, которые "хороши настолько, насколько возможно" (в том плане, что они не допускают ничего, кроме вычисления остаточной функции ), в то время как другие разложения не обладают такими свойствами. Зафиксируем функцию от переменных, и некоторые входных значений . Для всех обозначим через "остаточную функцию" и зафиксируем её первые переменных. То есть, для определим, что:

(В частности , а - константа, т.е. ). Как мы объяснили выше, любое разложение должно, по меньшей мере, допускать возможность вычисления для всех остаточных входных векторов . Минимально раскрытым является разложение, которое не допускает ничего больше. А именно, для любых возможно вычислить выходные значения композиции первых функций только с помощью оракульного доступа к остаточной функции .

Определение 2 (Минимально раскрытое разложение). Разложение минимально раскрыто , если существует вероятностная модель чёрного ящика , у которой для каждого вектора входных значений суммарной длины и для каждого функция работает за полиномиальное время , и результат этой функции равен , за исключением небольшой вероятности.[прим. 1]


Следует подчеркнуть, что не все функции имеют эффективные минимально раскрытые разложения[прим. 2], как показывает следующая теорема:

Теорема 1. Если односторонние функции существуют, то существуют и функции, которые не имеют эффективных минимально раскрытых разложений.

Теорема доказана в полной версии статьи [9]. Грубо говоря, разложение является минимально раскрытым только тогда, когда для остаточных функций возможно найти аргументы. Следовательно, псевдослучайная функция (рассмотренная как функция двух аргументов ) не имеет эффективного минимально раскрытого разложения. Полная версия также содержит обсуждение функций с несравнимыми разложениями.

Некоторые функции с минимально раскрытым разложением

Функция суммы. Возможно, простейший пример - функция суммы по группе: . В этом случае разложение на частичные суммы вида очевидно является минимально раскрытым. В самом деле, у нас есть , и модель может просто запросить , получив в ответе .

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

С другой стороны, рассмотрим функцию выбора с индексом в начале - . Здесь минимально раскрытое разложение должно поддерживать значение и бит состояния (ожидается/выполнено) такой, что когда его значение ожидается, значение равно , а когда выполнено - значение равно . Чтобы увидеть, что это разложение действительно минимально раскрыто, заметим, что при данном доступе к модель может проверить, больше ли индекс выбора , чем , например путём проверки, выдаёт ли различные значения на векторах и . Если - модель может найти проверкой входных значений, от которых зависит , а если - модель выдаст (который является выходным значением для каждого входа).

Двоичные симметрические функции. Выходное значение двоичной симметрической функции от переменных зависит только от количества единиц во входном векторе (т.н. вес Хэмминга): например, логические И, ИЛИ, а так же функции эквивалентности и большинства. Отметим, что таблица истинности симметрических функций имеет эффективное представление: для каждого необходимо лишь перечислить выходы на входах с весом Хэмминга . Таким образом, таблица истинности имеет длину , а не . Мы также отмечаем, что для симметрической функции и входного вектора , все соответствующие - так же симметрические, и, более того, таблица истинности может быть вычислена из значения и таблицы истинности . В частности, для таблица истинности получается из удалением последней строки, а для - удалением первой строки из таблицы истинности .

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

Симметрические функции над другими полями. Описанные выше наблюдения могут быть распространены на симметрические функции и над другими полями. Предположим, без потери общности, что поле это для некоторого целого . Функция с входами над является симметрической тогда, когда перестановка входных переменных не влияет на выходное значение. Другими словами, выходное значение зависит только от количества входов, по которым можно предположить значение поля. Этот тим функций является общим для статистических измерений, в том числе функций суммы, среднего значения, медианы, большинства, максимума и так далее.

Таблица истинности симметрической функции над может быть выражена с использованием одной строки для всех входов, которые имеют в точности входов со значением , входов со значением и так далее вплоть до входов со значением , и входов со значением . То есть, в таблице истинности есть строка для каждого -вектора неотрицательных , суммируемых до , так что в итоге мы имеем строк. Отсюда таблица истинности имеет полиномиальный размер для любой константы . Более того,, в этом случае снова имеется свойство, что все - симметрические, и таблица истинности может быть эффективно вычислена из значения и таблицы истинности (см. полную версию для подробной информации).

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

Однораундовые протоколы на основе сервера

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

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

Надежное вычисление разложения. Мы определяем безопасность с помощью идеально-реальной парадигмы в условиях автономности со статическими повреждениями. В идеальном мире существует дополнительная доверенная сторона, которая осуществляет вычисления для участников. В наших условиях, доверенный участник принимает входные данные всех клиентов и личности "испорченных" участников, а затем пересылает серверу выходную функцию, а так же любую информацию, которая, по сути, получается в нашей модели (на основе того, кто испорчен). Следует отметить, что идеальная модель определяется для функции разложения . (Здесь не обязательно включать , так как полностью её определяет.)

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

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

Определение 3 (Защищённое вычисление разложения). Пусть - функция от переменных, и пусть - разложение . Однораундовый протокол на основе сервера защищенно вычисляет разложение в пассивно-честной (соответственно вредоносной) модели, если для любого неравномерного вероятностного полиномиального пассивно-честного (вредоносного) злоумышленника в реальном мире, существует неравномерный вероятностный полиномиальный злоумышленник для пассивно-честного (вредоносного) идеального мира, такой, что для любого и верно

.

где пары ключей выбраны так, как описано выше (тождество по константе ).

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

Определение 4 (Оптимальная секретность). Пусть - функция от переменных. Протокол называют оптимально секретным основанным на сервере однораундовым протоколом для вычисления , если существует минимально раскрытое разложение функции такое, что защищенно вычисляет в пассивно-честной (соответственно вредоносной) модели.

Протоколы, оптимальные на практике

В разделе 5 мы покажем, что любое разложение может быть защищённо вычислено с использованием инфраструктуры открытых ключей, по предположению Диффи-Хеллмана. Как следствие, получим, что любая функция имеет минимально раскрытое разложение, которое может быть вычислено с оптимальной секретностью. Однако, это далеко не практично: даже для простых функций и пассивно-честных злоумышленников потребуются сотни экспоненциальных вычислений. В этом разделе мы представим высокоэффективные протоколы для конкретных примеров из раздела 2.2. Эти протоколы действительно практичны и могут быть реализованы, например, на обзорном сайте конференции для обеспечения безопасности голосования. (Только лишь с несколькими десятками пользователей, решению, обеспечивающему безопасность в присутствии вредоносных противников, потребуется лишь несколько секунд для расчётов каждого клиента и сервера). В полной версии мы опишем протоколы для остальных функций из раздела 2.2.

Протоколы для симметрических функций

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

Пассивно-честный случай. Напомним, что симметрические функции имеют короткую таблицу истинности длины , а так же то, что минимально раскрытое разложение для функций этого класса содержит таблицу истинности для всех , и то, что вычисление следующей таблицы истинности осуществляется удалением первой или последней с троки текущей таблицы. Интуитивно, наш протокол работает, имея первым клиентом , шифруя каждую из записей таблицы истинности итеративно (в слоистой, "луковой", структуре) с использованием открытых ключей всех участников. Затем, каждый участник, в свою очередь, снимает шифрование своим открытм ключом, а затем удаляет первую строку таблицы, если её входное значение равно нулю, или последнюю, если входное значение равно единице. После последнего участника, таблица содержит только одну строку, которая шифруется ключом сервера.

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


Мы решаем эту проблему использованием повторно рандомизируемого шифрования с открытым ключом. Свободно говоря, это означает, что если дано шифрование и открытый ключ , возможно сгенерировать эквивалетное шифрование с независимой хаотичностью. Подчеркнем, что повторная рандомизация должна работать на всех слоях ("лукового") шифрования. Требования здесь отличаются от стандартных понятий. Обозначим как шифрование с использованием хаотичности , и пусть - слоистое шифрование, начинающееся с шифрованием , использующим ключ , и дешифруемое с использованием каждого , в свою очередь, используя хаотичность . Для краткости, будем писать , где и .[прим. 3]

Тогда определим:

Определение 5. Схема с открытым ключом слоисто повторно рандомизируема (англ. layer rerandomizable), если существует процедура такая, что для любого и любого , верно, что

где такие, что все лежат в области значений , а - вектор распределения случайных последовательностей.

Подчеркнём, что определение требует, чтобы повторная рандомизация работала для всех хаотичностей (даже в том случае, если хаотичность "плохо выбрана"). Тем не менее, предполагается, что все открытые ключи "законны" в том, что они находятся в области значений . Слой повторной рандомизируемости может быть получем из любого схемы аддитивного гомоморфного шифрования. А именно, пусть по определению, начальное слоистое шифрование - это

,

где выбраны наугад при ограничении, что .

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

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

Более эффективная схема слоистого, повторно рандомизируемого шифрования может быть построена из схемы Эль-Гамаля. Пусть - группа простого порядка , порожденная элементом . Тогда, для открытого ключа и определим , где . Заметим, что для следует равенство , которое распространяется аналогично для шифровки с использованием независимой случайной строки .

Для того, чтобы сделать слой повторно рандомизируемым без увеличения размера шифротекста, мы определим слоистое шифрование следующим образом. Каждый участник имеет открытый ключ Эль-Гамаля по отношению к той же самой группе , как описано выше. Однако, шифрование открытыми ключами определяется как , где . В общем, мы определяем . Остается показать, как "дешифрует" его собственным ключом и повторно рандомизирует результат. Учитывая , где , а , участник дешифрует, вычисляя и . Это работает, потому что если брать , а мы имеем, что

Так что является верным шифрованием с хаотичностью и открытым ключом . Затем проводится повторная рандомизация так, как описано выше, с использованием открытого ключа . То есть, мы вычисляем и .

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

Теорема 2. Пусть - двоичная симметрическая функция. Если схема шифрования слоисто повторно рандомизируема, и все открытые ключи честных участников так же честно созданы с помощью , то протокол, описанный выше, является оптимально-секретным однораундовым протоколом на основе сервера для вычисления в присутствии пассивно-честных злоумышленников. Кроме того, он безопасен даже в том случае, если пассивно-честный злоумышленник может выбирать хаотичность протокола в произвольном порядке.

Доказательство (эскиз). Отдельно докажем для случаев, когда испорчен и когда нет. Если Если не испорчен, то достаточно доказать, что он получает правильные выходные данные и то, что злоумышленник может смоделировать свою точку зрения без какой-либо помощи доверенной стороны. Правильность этого утверждения следует непосредственно из построения задачи. Точка зрения злоумышленника может быть смоделирована, так как всё шифруется ключом честного сервера. В частности, каждый раз, когда честный участник собирается взаимодействовать с сервером, строится совершенно новая таблица истинности , которая содержит шифрований нуля ключами . Тот фа кт, что это ничем не отличается от реально исполнения, вытекает непосредственно из свойства скрытия шифрования, а так же свойства повторной рандомизируемости.

Далее мы рассмотрим случай, когда сервер повреждён, и - индекс последнего честного участника. В этом случае, модели присваивается значение , которое в этом случае соответствует частичной таблице истинности. Моделирование аналогично предыдущему для каждой итерации вплоть до включительно. На -й итерации моделирует сообщение, переданное честным , путём шифрования открытыми ключами частичной таблицы истинности, полученной от доверенной стороны. Как и прежде, выходное распределение злоумышленника неотличимо от реального исполнения (обратите внимание, что последнее смоделированное сообщение на самом деле идентично реальному исполнению; отличие в предыдущих, которые все есть зашифрованный ноль вместо реальных частичных таблиц истинности). Что и требовалось доказать.

В протоколе выше, использование повторно рандомизируемого шифрования на основе схемы Эль-Гамаля, каждый участник производит менее экспоненциальных вычислений, так что суммарная сложность не превышает . Следовательно, этот протокол может быть применим для большого (но не огромного) количества участников, даже для тысяч. Отметим, однако, что участники должны работать последовательно, и лишь это является ограничением для слишком большого . Кроме того, в этом конкретном случае участники могут подключаться и взаимодействовать с сервером в любом порядке, который является важным свойством для развертывания и внедрения на практике.

Вредоносный случай. Так как пассивно-честный протокол безопасен для любого случайных вариантов, использованных нечестными сторонами, достаточно добавить подписи, чтобы испорченные стороны и/или сервер не могли изменять сообщения, посланные предыдущими участниками, и (не интерактивное) доказательство с нулевым разглашением хорошей репутации для получения гарантий безопасности во вредоносной модели. Мы описываем итоговый протокол в полной версии. Для нашей конкретной реализации Эль-Гамаля, все эти проверки могут быть эффективны, так как они все могут быть сведены к составным операторам, эквивалентным дискретным логарифмам, и они могутбыть сделаны не интерактивно с использованием преобразования Фиата-Шамира в случайно-оракульной модели. В частности, каждому участнику необходимо возведений в степень, поэтому на выполнение протокола со участниками у каждой из сторон уйдет несколько минут.

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

Функции выбора

В этом разделе мы спроектируем оптимально-секретный протокол для функции выбора ., т.е. в случае, когда выбранный участник стоит в начале. Как видно из раздела 2.2, раскрытие в этом случае является наименьшим. В частности, в случае, если последний честный участник идет после выбранного участника, сервер может узнать только выбранное значение (даже не его позицию). В противном случае, наоборот, раскрывается только позиция. (Обратите внимание, что скрытие позиции, на самом деле, единственный интересный вопрос этой функции, так как в противном случае она решается тривиально с использованием позиции выбранного участника и посланного им сообщения).

Пассивно-честный случай. Наш протокол похож на -из- (пассивно-честный) протокол забывчивой передачи, использующий аддитивное гомоморфное шифрование: приёмник, который хочет получить -е значение, генерирует шифротекстов, шифрующих единицу, и лишь шифрует ноль. Используя аддитивный гомоморфизм, передатчик умножает шифротексты на случайные скаляры (различные случайное числа для каждого шифротекста), и затем добавляет их значения к -му шифротексту. Когда приёмник дешифрует сообщение, он получает -е значение нетронутым, в то время как остальные значения случайны.

Наш случай немного более сложен, чем протокол забывчивой передачи, так как а) входные значения разделены между участниками , а не принадлежат одному отправителю, и б) приёмник в нашем случае это сервер , а индекс выборки известен первому участнику . Вторая проблема решается выбором схемы шифрования с пространством для простого текста много большим, чем пространство входов для участников. Теперь, с большой долей вероятности, -й вход будет единственным в пространстве входов, так что сервер может идентифицировать его. Чтобы справиться с первой проблемой мы будем использовать смешанную сетчатую конструкцию (используя, опять же, слоистое повторно рандомизируемое шифрование), в которой каждый участник перемешивает шифротексты, так что следующие участники не могут узнать, от какого именно участника пришёл какой из шифротекстов. (Кроме того, мы используем схему Эль-Гамаля, которая более мультипликативна, нежели аддитивно-гомоморфна, так что мы можем соответственно изменить лежащий в ее основе протокол забывчивой передачи).

Более подробно, с выбранным входным готовит векто шифротекстов Эль-Гамаля, которые зашифрованы порождающим элементом группы , исключая -й, который шифрует единицу группы. -й шифротекст в этом векторе шифруется соединением открытых ключей Эль-Гамаля . (При использовании общего слоистого повторно рандомизируемого шифрования, -й шифруется в луковом тиле с использованием открытых ключей участников до ). Мы назовем этот вектор "начальными шифротекстами" (англ. initial ciphertexts)и обозначим как . Во время протокола начальные шифротексты принимаются неизменными, а участники используют их для обработки другим вектором шифротекстов, который содержит актуальные значения. Мы называем этот другой вектор шифротекстов "рабочими шифротекстами" (англ. work ciphertexts) и обозначим как .

Каждый участник принимает начальные шифротексты и вектор , содержащий шифротекстов. Все тексты из зашифрованы под . принимает -й шифротекст из (который также зашифрован под ), использует мультипликативный гомоморфизм Эль-Гамаля для увеличения размера текста внутри него случайным образом в , затем использует гомоморфизм ещё раз для умножения текста на его входы . Результирующий шифротекст вставляется в , таким образом получая вектор из шифротекстов, который мы обозначим . Затем отслаивает его слой шифрования (результирующийся в шифротекстах под ), случайным образом переставляет шифротексты и повторно рандомизирует их, получая новый вектор шифротекстов ,который отсылает обратно на сервер.

После того, как в протоколе поучаствовали все стороны, у сервера имеется вектор "рабочих шифротекстов" , зашифрованный открытым ключом сервера . Сервер дешифрует этот вектор, и если у соответствующего вектора открытого текста имеется один элемент из исходной области определения протокола, то сервер отдает этот элемент на выход. Псевдокод протокола (с использованием общего слоистого повторно рандомизируемого аддитивно гомоморфного шифрования) описан в Протоколе 3.

ПРОТОКОЛ 3 (ДОБАВИТЬ)

Используя те же аргументы, что и в двоичном симметричном случае, приходим к выводу, что приватность Протокола 3 оптимальная в присутствии пассивно-честных противников, если использованные схемы шифрования аддитивно гомоморфны и слоисто рерандомизируемы, а так же имеют пространство открытых текстов, полиномиально много большее, чем входное пространство протокола.

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

Надёжное вычисление любого разложения

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

Наша конструкция: "пассивно-честная" модель

Вредоносная модель

Что дальше? Открытые проблемы

Контакты авторов материала

  1. IBM T.J. Watson Research Center, E-mail: [1]
  2. Bar-Ilan University, E-mail: [2]
  3. Bar-Ilan University, E-mail: [3]

Примечания

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

Литература

  1. A Face Is Exposed for AOL Searcher No. 4417749. (The New York Times, August 9, 2006) http://www.nytimes.com/2006/08/09/technology/09aol.html.
  2. Goldreich, O.: Foundations of Cryptography, Basic Applications. Volume 2. Cambridge University Press (2004)
  3. Rivest, R., Adleman, L., Dertouzos, M.: On data banks and privacy homomorphisms. In: Foundations of Secure Computation, Academic Press (1978) 169–177
  4. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: 41st ACM Symposium on Theory of Computing – STOC 2009, ACM (2009) 169–178
  5. Fiat, A., Shamir, A.: How to Prove Yourself. Practical Solutions to Identification and Signature Problems. In: Advances in Cryptology - CRYPTO’86. Volume 263 of Lecture Notes in Computer Science., Springer-Verlag (1986) 186–189
  6. 6,0 6,1 6,2 6,3 6,4 6,5 Gentry, C., Halevi, S., Vaikuntanathan, V.: i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits. In: Advances in Cryptology - CRYPTO 2010. Volume 6223 of Lecture Notes in Computer Science., Springer (2010) 155–172 Full version available on-line from http://eprint.iacr.org/2010/145.
  7. Harnik, D., Ishai, Y., Kushilevitz, E.: How Many Oblivious Transfers Are Needed for Secure Multiparty Computation? In: Advances in Cryptology - CRYPTO 2007. Volume 4622 of Lecture Notes in Computer Science., Springer (2007) 284–302
  8. Choi, S.G., Elbaz, A., Malkin, T., Yung, M.: Secure Multi-party Computation Minimizing Online Rounds. In Matsui, M., ed.: Advances in Cryptology - ASIACRYPT 2009. Volume 5912 of Lecture Notes in Computer Science., Springer(2009) 268–286
  9. Halevi, S., Lindell, Y., Pinkas, B.: Secure Computation on the Web: Computing without Simultaneous Interaction. (http://eprint.iacr.org/2011/157)