Обеспечение безопасности протоколов пересечения закрытых множеств во вредоносных моделях с линейной сложностью

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:13, 12 декабря 2015.
Linear-Complexity Private Set Intersection Protocols Secure in Malicious Model
Title1.png
Авторы Emiliano De Cristofaro, Jihye Kim and Gene Tsudik
Опубликован 2009 г.
Сайт International Association for Cryptologic Research
Перевели Igor Nikolaev
Год перевода 2015 г.
Скачать Оригинал

Аннотация

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

Введение

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

  1. Авиационная безопасность. Министерство внутренней безопасности (МВБ) Соединенных Штатов обязано отклонять посадку или высадку любого пассажира на любом рейсе из/в США, основываясь на так называемом списке террористических угроз. На сегодняшний день авиалинии обязаны отдавать МВБ всю информацию о пассажирах, включая важную личную информацию, такую как номера кредитных карт. Кроме последствий для конфиденциальности, этот образ действия создаёт проблемы с надёжностью (в основном) для обычных данных пассажиров и наводит на опасения относительно потенциальной потери данных. В идеале, МВБ следует получать информацию только относящуюся к пассажиру, при этом не раскрывая её авиалиниям.
  2. Здравоохранение. Страховым компаниям часто приходится получать информацию о застрахованных пациентах из сторонних источников, таких как больницы и другие страховые организации. Компании не могут раскрывать данные о своих клиентах, в то время как последние не могут предоставлять информацию о других клиентах.
  3. Правоохранительные органы. Следователям (например, ФБР) нужно получать информацию о подозреваемых от других органов (например, местное отделение полиции, департамента транспорта, налоговая, работодатель). В большинстве случаев, компрометирование данных о подозреваемом опасно (или просто запрещено). Со своей стороны, другие стороны не могут выдавать следователям полный набор информации о подозреваемом и делятся только необходимой для дела информацией. Также, запросы ФБР должны быть первоначально заверены какими-либо вышестоящими инстанциями (например, федеральным судьей). Таким образом, ФБР получает доступ только к информации, обозначенной в легитимном запросе.

Злоумышленники в ПЗМ

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

Авторизованный (Клиентский) вход

Вредоносные стороны не могут предотвратить изменение их входных наборов, даже если протокол является безопасным во вредоносной модели. Беря во внимание тот факт, что клиент узнает пересечения в то время, как сервер не узнаёт ничего, это создает серьёзные угрозы серверной приватности. Например, предположим, что вредоносный клиент доверительно следует протоколу, но наполняет входные данные набором, который по его предположению ближе всего к серверному набору (особенно, если набор может быть легко и исчерпывающе пронумерован). Это бы повысило количество информации, которое он узнает. В крайнем случае, клиент может даже заявить, что его набор содержит все возможные элементы. Несмотря на то, что сервер может наложить ограничение на размер набора, клиент все равно сможет изменять свой набор через многочисленные вызовы выполнения протокола. Мы утверждаем, что эта проблема не может быть эффективно решена без какого-либо механизма авторизации входных данных клиента. Вследствие этого, нужен доверенный источник сертификации (ИС) для того, чтобы сертифицировать входные наборы, как предложено в [DJKT09[2], CZ09[3]]. Этот вариант называется “Авторизованный закрытый набор пересечений” (АПЗМ) в [DT10][4]. Заметим, что ИС это сущность, которая находится оффлайн; ему не доверяют и не вовлекают в процесс вычисления пересечений. Как было сказано выше, входная авторизация обеспечивает невозможность вредоносных клиентов манипулировать их входными данными в целях нарушения приватности сервера. Однако, это абсолютно бесполезно, если манипуляции совершаются с входными данными сервера. Следующим шагом к обеспечению безопасности против вредоносных серверов будет создание авторизации для входных данных сервера, по аналогии с авторизации со стороны клиента. Не смотря на то, что таким способом также можно обеспечить безопасность во вредоносной модели, мы не будем идти в этом направлении. Основная причина в том, что гораздо логичнее авторизовываться клиенту (который получает пересечения), чем серверу (который не получает ничего). Однако, мы уверены, что стоит подробнее исследовать одновременное использование и клиентской и серверной авторизации. В итоге, вопрос об отказе от двусторонней авторизации и потере в безопасности ПЗМ во вредоносной модели остаётся открытым.

Технические карты и вклады

На протяжении последних лет, было предложено несколько элегантных (но не всегда эффективных) ПЗМ и АПЗМ протоколов, которые безопасны во вредоносных моделях, при стандартных допущениях [KS05[5], HL08[6], DSMRY09[7], CZ09[3], CKRS09[8], HN10[9]]. Только в [JL09][10] реализован протокол безопасности ПЗМ, дающий линейную сложность при работе во вредоносной среде. Его доказательство требует, чтобы домен был ограничен полиномом в параметре безопасности и требует реализации модели Common Reference String (CRS), где ссылочная строка, включая безопасный RSA модуль, должны быть совместно сгенерированы надежной третьей стороной. Остальные результаты (такие как [DT10][4]) создают протоколы безопасности ПЗМ и АПЗМ в получестной модели при допущениях типа one-more-XXX с гораздо более низкой вычислительной и коммуникационной сложностью. (Отметим, что предыдущая работа находится в секции 2). Как показано в [DT10][4], с помощью анализа и экспериментов, существует заметная разница в эффективности между двумя “семьями” ПЗМ/АПЗМ протоколов: теми, которые безопасны во вредоносных моделях и теми, которые безопасны в получестных моделях. В этой работе нашей основной целью является создание эффективных протоколов безопасности ПЗМ и АПЗМ при стандартных допущениях с вредоносными участниками (и сервером и клиентом). Нашей отправной точкой будет протокол с линейной сложностью из [DT10] (в основном второй и третий), который безопасен только в получестных моделях. В первую очередь, мы модифицируем АПЗМ структуру [DT10] и получим АПЗМ протокол, безопасный во вредоносных моделях при стандартных RSA допущениях (в ROM). Далее, мы изменим его ПЗМ копию: в то время, как ПЗМ протокол линейной сложности в [DT10] безопасен при допущении One-More-Gap-DH против получестных сторон, наш модифицированный вариант безопасен во вредоносных моделях при стандартных DDH допущениях (опять же, в ROM). Мы представляем формальное доказательство всех предложенных протоколов. Вклад нашей работы:

  1. В меру наших знаний, наш АПЗМ протокол является первым результатом с линейной вычислительной и коммуникационной сложностью во вредоносной модели. (В предыдущей работе достигнута квадратичная вычислительная сложность.)
  2. Наш ПЗМ протокол также даёт линейную сложность. Хотя, что некоторые прежние работы (то есть [JL09][10]) также дали такую же асимптотическую границу, мы не требуем CRS модель и наше доказательство не ограничено размером входного домена. Мы также демонстрируем, что наш протокол несет значительно пониженные постоянные факторы.
  3. Мы доказываем безопасность предложенных протоколов при наличии вредоносных противников при стандартных криптографических (RSA и DDH) допущениях, в ROM.

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

Связанные работы

Этот раздел является обзором предыдущих работ по ПЗМ и АПЗМ.

Предыдущие работы по ПЗМ

Хорошо известно, что ПЗМ могут быть реализованы через безопасные двухсторонние вычисления [Yao82][11]. Однако, часто бывает, что гораздо более эффективным является вариант с доверенными протоколами (см. [FNP04[12], KS05][5]); в этом направлении мы и будем работать в этой статье. Далее, мы рассматриваем ПЗМ как взаимодействие между сервером и клиентом . Множество сервера содержит элементов, а множество клиента — . Фридман и др. [FNP04] представили концепт ПЗМ и показали протоколы, основанные на Очевидно Полиномиальных Оценках (ОПО) [NP06][13]. Основная идея — представление множества в виде полинома с индивидуальными элементами в роли его корней. Архитектура получестных настроек обеспечивает линейную коммуникационную и квадратичную вычислительную сложность. Используя правило Горнера и сбалансированное распределение, можно свести модульное возведение в степень к для сервера и для клиента. [FNP04] также предлагает архитектуры для вредоносного клиента и получестных моделей. Этот протокол использует стратегию "срез и выбор", таким образом, расходы увеличиваются статическим параметром безопасности. Также представленное безопасно на уровне протокола в присутствии вредоносного сервера и получестного клиента в ROM. Кисснер и Сонг [KS05][5] предлагают OPE протоколы для общих ПЗМ (также как и для дополнительных операций множествах), и в состоянии работать более, чем с двумя участниками. Протоколы безопасны в стандартной модели против получестных и против вредоносных противников. Это влечет за собой квадратичную вычислительную сложность (но линейную коммуникационную). Последние используют (затратные) общие доказательства, чтобы предотвратить нарушение протокола. Позже, Дачман-Солд и др. [DSMRY09][7] представили улучшенную архитектуру ПЗМ, основанную на [KS05]. Их архитектура включала в себя секретную передачу полиномиальных входов. Так как секретная передача Шамира [Sha84][14] реализовывает коды Рида Сломона, им не нужны общие доказательства. Коммуникационная сложность их протокола , а вычислительная , где — параметр безопасности. Ещё одно семейство протоколов полагаются на так называемые Очевидно Псевдослучайные Функции (ОПСФ). ОПСФ это двусторонний протокол (между отправителем и получателем), который безопасно вычисляет псевдослучайную функцию , где параметрами выступают ключ отправителя и вход получателя. Таким образом первый ничего не узнаёт из взаимодействия, а последний узнает только значение . ПЗМ, основанные на ОПСФ работают так: Сервер владеет случайным секретным ключом , далее для каждого вычисляет , и отыслыает клиенту множество . Затем, и начинают ОПСФ вычисление для каждого (размера ), таким образом ничего не знает о (кроме размера), а знает . Таким образом получает , тогда и только тогда, когда . Идея использования ОПСФ для ПЗМ протоколов взята у Хазая и Линделла [HL08], которые предложили одно безопасное решение против вредоносных противников с односторонним моделированием и ещё одно против скрытых противников [AL07][15]. Этот протокол в дальнейшем был улучшен Джареки и Лью [JL09][10], которые предложили протокол, который является безопасным в стандартной модели в присутствии вредоносных участников с обеих сторон. Протокол основан на допущении q-ичной инверсии Диффи-Хелмана в модели CRS (Common Reference String), где безопасный RSA модуль генерируется доверенной третьей стороной. Операции шифрования выполняются использую аддитивную гомоморфную схему шифрования, такую как схема Камениша и Шоупа [CS03][16]. Как указано в [JL09], этот подход в дальнейшем может быть оптимизирован, используя работу [BCC+09][17]. Используя эту улучшенную архитектуру, [JL09] задаст следующую вычислительную сложность: Пусть будет числом битов, необходимых для представления каждого элемента множества; сервер вычисляет хотя бы оценок ПСФ, т.е. -битовые и групповые экспоненты, плюс групповые экспоненты, в то время как клиент клиент вычисляет хотя бы -битовые экспоненты плюс групповые экспоненты. Мы детально обсуждаем сложность этого решения далее в этой статье. Наконец, отметим, что доказательство в [JL09] требует возможности исчерпывающего поиска по входному домену, т.е. размер входного домена ПСФ должен быть полиномиальным по безопасным параметрам. Последний результат Хазая и Ниссима [NH10][9] представляет из себя улучшенную архитектуру ПЗМ, основанных на OPE [FNP04], но без ROM. Особенность этой архитектуры в том, что она использует доказательства с нулевым знанием, которые дают возможность клиенту продемонстрировать, что зашифрованный полином создан правильно. Также, она использует технику, которая идеально скрывает исполняемую схему и протокол оценки ОПСФ, чтобы воспрепятствовать нарушению протокола со стороны сервера. ПЗМ протокол в [HN10] обеспечивает вычислительную сложность и коммуникационную сложность, где это количество бит, необходимых для представления элемента множества. Заметим, что выполнение лежащей в основе [HN10] ОПСФ требует вызовов передачи и, следовательно, модульных возведений в степень для каждого элемента множества. Однако, этого можно избежать инстанциированием протокола в ROM. Этот протокол также может быть оптимизирован, если допустима утечка серверу размера пересечений, в отличие от наших строгих определений приватности (см раздел 3.3). Тем не менее, результирующий протокол даёт коммуникационной сложности и вычислительной сложности, что всё ещё не является линейным. (Также отметим, что неясно как включить архитектуру ПЗМ [HN10] в АПЗМ.) В другой недавней работе, [DT10] (Рис. 4) представляет адаптивный ПЗМ протокол основанный на слепых RSA подписях [Cha83][18], безопасных в получестных моделях, под допущением One-More-RSA [BNPS03][19] в ROM. Во время фазы инициализации сервер генерирует RSA ключ и присваивает его множеству путём назначения хэша RSA подписи для каждого элемента. Таким образом, серверу надо посчитать RSA подписей во время иницализации и онлайн. В то же время, клиент (пусть ) вычисляет только умножений, таким образом это делает архитектуру привлекательной для клиентов с ограниченными ресурсами. [DT10] (Рис. 3) включает другую ПЗМ, безопасную в присутствии получестных противников, под допущением One-More-Gap-DH в ROM. Распространённым входом являются простые числа ( является порядком подгруппы ) и генератор подгрупп, . Клиент вычисляет и посылает для случайнх в . Также, для он вычисляет и отсылает для в . Сервер берет рандомное в , отсылает , и для каждого возвращает . Дальше, для он вычисляет . Наконец, клиент вычисляет и узнаёт, что , если . Вычислительная сложность этого протокола и возведений в степень (считая короткие экспоненты) для сервера и клиента соответственно.

Предыдущие работы по АПЗМ

Авторизационные пересечения закрытых множеств (АПЗМ) определены в [DT10][4] для того, чтобы расширить ПЗМ и для поддержки авторизации клиентских входных данных. Каждый клиентский вход должен быть авторизован (через подпись) каким либр доверенным лицом, например, центром сертификации. Основываясь на третьем примере в разделе 1: чтобы получить информация о подозреваемом от его работодателя, ФБР необходимо быть должным образом авторизованными. АЗПМ предоставляет авторизацию, использующую цифровую подпись. Отметим, что авторизации полученные от ЦА приватны для клиента и не могут быть раскрыты серверу. [DT10] показывает, что ПЗМ протокол на Рис.3 (показан в конце раздела 2.1) может быть инстанциирован в RSA системе, где клиентские входные данные это множество RSA подписей и сервер подтверждает их путём модификации протокола следующим образом. Клиенту нужно получить от ЦА подпись (для входа . вычисляет аккумулятор и отсылает для случайного . Также, он вычисляет и отсылает для случайного . Сервер берёт рандомный , отсылает , и, для каждого , отсылает обратно . Далее, для он вычисляет . Наконец, клиент вычисляет , и узнает, что , если . Асимптотическая сложность этого решения такая же, как и у стандартной ПЗМ, представленной выше, т.е. и возведений в степень для сервера и клиента соответственно. (Несмотря на то, что короткие экспоненты заменены на "RSA" экспоненты.) Результирующий протокол безопасен для получестных моделей под стандартными RSA допущениями в ROM. Отметим, что использование "авторизованного" входа клиента увеличивает приватность сервера: под RSA допущениями, клиент не узнаёт ничего о входной информации сервера, пока она не содержит действительной RSA подписи. Другими словами, появляется сильная корреляция между серверной приватностью и сложностью подделки подписей клиентской стороной. Похожий концепт (адаптирующийся к АПЗМ) это Public-Key Encryption (Шифровка публичного ключа) c Oblivious Keyword Search в [CKRS09][8]. Он предлагает использование криптосистемы, основанной на сущностях, (вдохновленной PEKS в [BDOP04][20]), где клиент получает лазейки в поиске от ЦА и использует их, чтобы осуществлять поиск в зашифрованных данных сервера. Клиент узнаёт только информацию о лазейках, в то время, как сервер не узнаёт ничего. Протокол безопасен в присутствии вредоносных противников в стандартной модели под Билинейным Решающим допущением Диффи-Хеллмана [BF03][21]. Он использует подификацию IBE Бойена-Вотерса [BW06][22]. Даже не считая доказательства с нулевым знанием, сервер посчитает шифров [BW06] (каждый из которых требует 6 возведений в степень и представления группы из 6 элементов). Клиенту нужно будет протестировать каждый из PEKS для каждого из лазеек, следовательно произвести дешифровок. Наконец, [CZ09][3] представляет схожую идею — закрытое пересечение сертифицированных множеств. Эта архитектура позволяет доверенной третьей стороне убедиться в том, что все входы протокола действительны и прикреплены к конкретному участнику протокола. Предложенный протокол обоюден (т.е. обе стороны получают пересечения) и строится рассеянной полиномиальной оценкой и достигает квадратичных вычислительных и коммуникационных излишков.

Подготовка

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

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

Криптографические допущения

Определение 1. Пусть — циклическая группа и пусть — её образующий элемент. Предположим, что битовая длина размера группы равна . Задача DDH является сложной в , если для каждого эффективного алгоритма вероятность:

незначительная функция от .

Определение 2. Пусть RSA-Gen — алгоритм, который выдаёт так называемые "безопасные RSA экземпляры", т.е. пары , где , — маленькое простое число такое, что , и — случайные -битные простые субъекты с такими ограничениями, что для простых . Задача RSA является сложной, если для каждого эффективного алгоритма вероятность:

незначительная функция от .

Инструменты

В этом разделе мы рассмотрим подпись знаний дискретного логарифма и равенство двух дискретных логарифмов в циклической группе . В частности, мы рассмотрим , где известен либо порядок , либо неизвестен, но его битовая длина общеизвестна. Фуджисаки и Окомато [FO97][23] показали, что (под сильным RSA допущением) стандартные доказательства знания, которые работают в группе с известным порядком, также доказывают знание в это постановке. Мы определили дискретный логарифм в соответствии с образующим элементов , как любое целое число такое, что в . Мы предполагаем, что параметра безопасности .

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

Определение 4. (ZK для DL для группы с неизвестным порядком) Пусть , где порядок группы неизвестен, но известно, что его битовая длина равна . Пара удостоверяет, что является подписью знаний дискретного логарифма в соответствии с образующим элементом , для сообщения .

Участник при наличии секретным может вычислить подпись, выбрав случайное (или ) и затем вычислив и , как и в (или в ).

Определение 5. (ZK для EDL для группы с известным порядком) Пусть порядка . Пара удостоверяет, что является подписью дискретного логарифма и в соответствии с образующим элементом , и в соответствии с образующим элементом , для сообщения .

Определение 6. (ZK для EDL для группы с неизвестным порядком) Пусть , где порядок группы неизвестен, но известно, что его битовая длина равна . Пара удостоверяет, что является подписью знаний дискретного логарифма и в соответствии с образующим элементом , и в соответствии с образующим элементом , для сообщения .

Участник при наличии секретным может вычислить подпись, выбрав случайное (или ) и затем вычислив и , как и в (или в ).

Модель безопасности

Мы предполагаем, что вредоносный противник будет иметь произвольное поведение. Неформально, протокол безопасности в этой модели, при условии отсутствия противников, взаимодействующих с реальным протоколом (где нет TTP) может узнать больше при реальном выполнении, чем при выполнении в идеальных условиях. Другими словами, для любого противника, который благополучно атакует реальный протокол, существует симулятор, который успешно атакует такой же протокол в идеальных условиях. Теперь мы можем определить идеальный набор функций для ПЗМ и АПЗМ. В частности, в отличие от ПЗМ, АПЗМ работает с (оффлайн) ЦА, применяя алгоритмы (KGen, Sign, Ver). ЦА генерирует пару ключей , оглашает публичный ключ , и для клиентского входа выдаёт подпись .

Определение 7. Идельный набор функций для АПЗМ (APSI) протокола между сервером с входом и клиентом с входом определяется следующим образом:

где — открытые входы .

Определение 8. Идельный набор функций для ПЗМ (PSI) между сервером с входом и клиентом с входом определяется следующим образом:

где — открытые входы .

АПЗМ Протокол

Теперь мы представим протокол для безопасных вычислений авторизованного пересечения множеств. Начнём с АПЗМ протокола [DT10] (представленного в разделе 2.2), безопасного в получестных моделях. Мы описываем модифицированную версию, которая безопасно реализует характеристики во вредоносной модели, в ROM, под RSA и DDH допущениями. ЦА (доверенная третья сторона, которая авторизирует входные данные клиента) реализуется следующими алгоритмами:

KGen: Основываясь на параметре , этот алгоритм генерирует безопасный RSA модуль , где и берёт случайный элемент s.t. . RSA экспоненты выбираются стандартным способом: — маленькое простое число, . Этот алгоритм исправляет хэш-функцию и . Секретный ключ и публичный ключ: .

Подпись: Для входа этот алгоритм создаёт авторизацию .

Ver: Для входа этот алгоритм удостоверяет, что .

Результирующий протокол представлен на Рис. 1.

Теорема 1. Если RSA и DDH проблемы сложны, а являются доказательствами с нулевым знанием, тогда протокол на Рис. 1 это результат безопасных вычислений в ROM.

Доказательство. [Построение идеального мира из вредоного сервера ]

Симулятор построен следующим образм:

Развертывание: выполняет и публикует параметры

Хэш-запросы к и : создаёт две таблицы и , чтобы соответственно ответить на запросы и . Особенности:

  • На запрос к , проверяет  : если так, то возвращает , иначе возвращает и хранит в .
  • На запрос к , проверяет  : если так, то возвращает , иначе возвращает и хранит в .
CommonInput2.png
Рис.1. Наш АПЗМ протокол с линейной сложностью безопасен против вредоносных противников

Симуляция реального клиента и идельного сервера

1. выбирает и вычисляет для каждого
2. посылает и симулирует доказательство
3. После получения и взаимодействия с , как верификатор в доказательстве , если доказательство верифицировано, то запускает алгоритм получения . В противном случае, завершается.
(a) Для каждого , проверяет и , такое, что и . Если так, то добавляем к ; иначе, добавляем модель-болванку к .
(b)Затем, играет роль идеального сервера, который использует , чтобы ответить на запрос идеального клиента .

Так как распределение отправленное идентично распределению предоставленному реальным клиентом и доказывает, что система с нулевым знанием, состояния во время взаимодействия с реальным клиентом и с симулятором неразличимы.

[Выход реального (честного) клиента , взаимодействующего с ]

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

1. вычисляет из для . Так как , описанный выше, получает и добавляет в , идеальный также выдает при входе .
2 не запрашивает для , но . Этот случай имеет вероятность .

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

[Создание идеального из вредоносного реального клиента ] Симулятор описывается следующим образом:

— Развертывание и хэш-запросы к и : Также, как и Развёртывание и ответы, описанные выше, для создания .
— Авторизация запросов: На вход , отвечает , где и хранит в таблице .
— Симуляция реального сервера и идеального клиента :
1. После получения , и взаимодействия с в роли верификатора доказтельства , проверяет достоверность доказательства . Если не достоверно, то симуляция завершается. Иначе, выполняется алгоритм получения для и вычисляется такое, что .
2. Для каждого :
- Если такое, что , то добавим элемент-болванку к , где и случайно выбраны из соответствующего домена.
- Если такое, что , но такое, что , тогда на выход и завершить симуляцию.
- Если такое, что и такое, что , тогда добавим в множество .
3. играет роль клиента в идеальном случае. На вход взаимодействует с идеальным сервером через TTP.
4. На основе полученных пересечений , с из идеального взаимодействия, формирует , где — элементы-болванки, а — функция пермутации.
5. берёт и вычисляет и для .
6. Для каждого :
- Если , вычисляет .
- Если , вычисляет .
7. возвращает и симулирует доказательство .

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

— Развёртывание: На вход устанавливается и выбирает образующий элемент . (Заметим, что случайный в выбран генерацией реального ключа с вероятностью 1/2.)
— Авторизационные запросы: На вход возвращается и , определяет и записывает в .
— Хэш-запросы : На запрос к , если , тогда передаёт , где и хранит в . (Так как равномерно распределена в , также равномерно распределена в .)

Предположим, что произошло на . Затем, получает такое, что и выдаёт , который нарушает RSA допущение.

Теперь, если не случился, то представления, взаимодействующие с и с реальным протоколом, различаются только в вычислении для , но . Пусть — событие при котором запрашивает на для и .

Требование 2. Если событие имеет значительную вероятность, тогда может быть использован для нарушения DDH допущения.

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

— Развёртывание: На вход устанавливает и выбирает образующий элемент и <math<e \leftarrow_r \Z_N</math>.
— Авторизационные запросы: Также, как и в симуляции <math\mathcal{C}h_1</math>
— Хэш-запросы к : На запрос к , если , тогда возвращает , где , и записывает в . (Так как — случайное число из , распределение вычислительно неотличимо от равномерного распределения .)
— В вычислениях для :
  • устанавливает и вычисляет для (вместо выбора и вычисления и ).
  • Для каждого , если вычисляет .

Дано и , делаем замену на в симуляции и . Таким образом, представления во время взаимодействия с реальным сервером и с симулятором неразличимы под DDH допущением. Предположим, что произошло , то есть делает запрос к на для , но . проверяет и так, что для каждого , но . В таком случае, возвращает True. В противном случае — False. Таким образом, DDH допущение нарушено.

Поэтому, так как и имеют незначительную вероятность, то представления в протоколе с реальным сервером и во взаимодействии с ничтожно малы.

[Выход честного реального сервера , взаимодействующего с ]

Наконец, реальный сервер , взаимодействующего с в реальном протоколе, выдаёт и идеальный , взаимодействующий с получает . Это конец Теоремы 1.

Наш АПЗМ протокол отличается от [DT10] следующим:

— Мы изменяем вход протокола и добавляем эффективные доказательства нулевого знания, чтобы предотвратить нарушение протокола сервером и клиентом и позволить извлечение входа.
— Мы умножаем клиентский вход на -1 в случайном бите, чтобы: (1) убедиться в том, что они равномерно распределены в , и (2) упростить уменьшение RSA задачи.
— Мы не используем "аккумулированные" значения, такие, как , так как они не нужны ни для защиты протокола, ни для извлечения входа во время симуляции.

ПЗМ Протокол

Этот раздел представляет наш протокол для безопасных вычислений пересечений множеств. Это модифицированная версия ПЗМ протокола [DT10] (описанного в Разделе 2.1), безопасного в получестных моделях под One-More-Gap-DH допущением (в ROM). Мы исправили это, чтобы получить протокол, который безопасно реализует во вредоносной модели под DDH допущением (в ROM). Мы предполагаем, что KGen генерирует , где и — простые, такие, что и являются образующими .

Результирующий протокол представлен на Рис. 2.

Теорема 2. Если DDH задача сложна и доказательства нулевого знания, протокол на Рис. 2 безопасен для в ROM.

Доказательство. [Создание идеального из вредоносного реального сервера ]

Симулятор строится так:

— Развёртывание: выполняет KGen и выводит публичные параметры .
— Запросы и : создаёт две таблицы и , чтобы ответить на запросы и соответственно. Особенности:
  • На запрос к , проверяет : если выполняется, то возвращает , иначе возвращает и сохраняет в .
  • На запрос к , проверяет : если выполняется, то возвращает , иначе возвращает и сохраняет .
— Симуляция реального клиента и идеального сервера :
1. берёт и (для ).
2. посылает и симулирует доказательство .
3. После получения , и взаимодействия с в роли верификатора в доказательстве , если верифицировано, то выполняет алгоритм извлечения для . В противном случае завершается.
(a) Для каждого , проверяет и , причём и . Если выполняется, то добавим к ; иначе, добавляем элемент болванку в .
(b) Далее играет роль идеального сервера, который использует , чтобы ответить на запрос идеального клиента .
Pic2.png
Рис. 2. Наш ПЗМ протокол с линейной сложностью безопасен против вредоносных противников

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

[Выход честного реального клиента взаимодействующего с ]

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

1. вычисляет из для . Так как извлекает и добавляет в , идеальный также выдаёт для входа .
2. не запрашивает на , но равен . Это событие случается с незначительной вероятностью, ограниченной .

Поэтому, с вероятностью , реальный клиент взаимодействует с и идеальный клиент взаимодействует с , получая идентичный выход.

[Создание идеального из вредоносного реального клиента ]

Симулятор строится так:

— Развёртывания и хэш-запросы к : Такое же, как развёртывание для .
— Симуляция реального сервера и идеального клиента :
1. После получения , и взаимодействия с , как верификатор , проверяет . Если не верифицировано, то завершает. Иначе, выполняет алгоритм извлечения для и вычисляет .
2. Для каждого , если , где , то добавляем в множество . Иначе, добавляем элемент болванку в .
3. играет роль клиента в идеальном случае. На вход , взаимодействует с идеальным сервером через TTP.
4. На этапе получения пересечений из идеального взаимодействия, формирует , где — элементы болванки, а — функция пермутации.
5. выбирает и вычисляет и для .
6. Для каждого :
  • Если , вычисляет .
  • Если , вычисляет .
7. возвращает и симулирует доказательство .

Пусть fail — событие, которое запрашивает у на для . Если fail не происходит, то мы утверждаем, что представления в реальной игре с реальным сервером во взаимодействии с симулятором неразличимы.

Требование. Если fail случается с весомой вероятностью, то может быть использован для нарушения DDH допущения.

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

— Развёртывание: На вход устанавливает и выбирает образующий .
— Хэш-запрос к : На запрос к , если , тогда возвращает , где , и записывает в .
— В вычислении :
  • устанавливает и вычисляет .
  • Для каждого , если , вычисляет .

Используя аргумент, схожий с аргументом из доказательства теоремы 1, представления во время взаимодействия с реальным сервером и с симулятором неразличимы под DDH допущением. Предполагая, что случился fail, то есть делает запрос к на для , но . проверяет, если и , причём для каждого . Если так, то выдает True. Иначе False. Таким образом, решает DDH проблему.

Так как fail случается с ничтожно малой вероятностью, представления в протоколе с реальным сервером и взаимодействием с маловероятны.

[Выход честного реального сервера , взаимодействующего с ]

Наконец, реальный сервер , взаимодействующий с в реальном протоколе, выводит и идеальный , взаимодействующий с получает .

Эффективность протокола

В этом разделе мы анализируем эффективность протоколов и сравниваем их предварительные результаты. Мы суммируем разные особенности и оцениваем асимптотическую сложность предварительной работы на АПЗМ и ПЗМ. Напомним, что мы используем и , чтобы обозначить количество элементов в серверном и клиентском входных множествах соответственно. Также, мы указываем, что они могут поддерживать расширения для передачи данных — ПЗМ-вариант представлен в [DT10] и описан в деталях в расширенной версии в [DKT10][24].

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

Сравнение ПЗМ [Рис. 2] и [JL09]. Наш ПЗМ протокол обеспечивает такие же (линейные) асимптотические излишки, как и в предыдущей работе [JL09], в ROM. Однако, базовые криптографические операции [JL09], спрятанные в O() нотации, гораздо затратнее, чем те, что указаны на Рис. 2.

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

Заметим, что ПЗМ протокол на Рис. 2 во вредоносных моделях имеет общую стоимость . Учитывая ограничения места хранения, мы ссылаемся на расширенную версию [DKT10] для всех деталей наших оценок.

Чтобы посчитать число операций в [JL09], мы используем оптимизированный OPRF [BCC+09][17] и для стандартных неинтерактивных ZK в ROM. Мы выбираем множество элементов и выводим их в 40-битный домен. [примечание 1]. Общая стоимость [JL09] во вредоносной модели .

  1. Напомним, что в доказательство [JL09] производится обмен размера входного домена на потери в безопасности, так как симулятор сильно загружен при поиске
Таблица 2. Сравнение АПЗМ протоколов
Протокол Стандартная модель Вредоносная модель Допущение Коммуникационная сложность Сервер Клиент Передача данных
[CKRS09] Да Да BDH [BW06] [BW06] Да
[CZ09] Да Да Сильный RSA эксп. эксп. Нет
Рис. 2 [DT10] Нет Нет RSA эксп. эксп. Да
Наш АПЗМ Нет Да RSA эксп. эксп. Да


Таблица 3. Сравнение ПЗМ протоколов
Протокол Стандартная модель Вредоносная модель Допущение Коммуникационная сложность Сервер Клиент Передача данных
[FNP04] Да Нет Homom. Encr. эксп. эксп. Да
[KS05] Да Да Homom. Encr. эксп. эксп. Нет
[JL09] Да Да Dtcisional q-DH, CRS эксп. эксп. Да
[HN10] Да Да DDH эксп. эксп. Нет
Рис. 3 [DT10] Нет Нет One-More-Gap-DH эксп. эксп. Да
Рис. 4 [DT10] Нет Нет One-More RSA эксп. умн. Да
Наш ПЗМ Нет Да DDH эксп. эксп. Да

Выбрав, например, , протокол на Рис. 2 потребует на полтора процента меньше общего числа модульных умножений, чем в [JL09] (даже с оптимизированным OPRF). Только когда , [JL09] имеет меньшие затраты. Далее, заметим, что будучи безопасной в стандартной модели, ПЗМ в [JL09], по сравнению с нашей, имеет три существенных недостатка: (1) Размер набора элементов должен быть полиномиальным в параметре безопасности, в то время, как наш протокол может брать элементы из , (2) Требует Decisional q-DH допущения и CRS модели, где безопасный RSA модуль должен быть сгенерирован доверенным третьим лицом, и (3) неясно, как его конвертировать в АПЗМ.

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

Заключение

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

Благодарности. Это исследование было поддержано US Intelligence Advanced Research Projects Activity (IARPA) под грантом номером FA8750-09-2-0071, а также Basic Science Research Program через National Research Foundation of Korea, профинансированным Ministry of Education, Science and Technology (2009-0070095) и ’Developing Future Internet Network Model - Mathematical Approach’ National Institute for Mathematical Sciences. Джие Ким является соответственным автором этой работы. Мы также хотели бы поблагодарить Ксьаомин Ли и Джае Хонг Сио за полезные комментарии.

Ссылки

  1. Goldreich, O.: Foundations of cryptography: Basic applications. Cambridge Univ. Press, Cambridge (2004)
  2. De Cristofaro, E., Jarecki, S., Kim, J., Tsudik, G.: Privacy-Preserving Policy-Based Information Transfer. In: Goldberg, I., Atallah, M.J. (eds.) Privacy Enhancing Tech- nologies. LNCS, vol. 5672, pp. 164–183. Springer, Heidelberg (2009)
  3. 3,0 3,1 3,2 Camenisch, J., Zaverucha, G.: Private intersection of certified sets. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 108–127. Springer, Heidelberg (2009)
  4. 4,0 4,1 4,2 4,3 De Cristofaro, E., Tsudik, G.: Practical Private Set Intersection Protocols with Lin- ear Complexity. In: Financial Cryptography and Data Security (2010)
  5. 5,0 5,1 5,2 Kissner, L., Song, D.: Privacy-preserving set operations. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 241–257. Springer, Heidelberg (2005)
  6. Hazay, C., Lindell, Y.: Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 155–175. Springer, Heidelberg (2008)
  7. 7,0 7,1 Dachman-Soled, D., Malkin, T., Raykova, M., Yung, M.: Efficient Robust Private Set Intersection. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 125–142. Springer, Heidelberg (2009)
  8. 8,0 8,1 Camenisch, J., Kohlweiss, M., Rial, A., Sheedy, C.: Blind and Anonymous Identity- Based Encryption and Authorised Private Searches on Public Key Encrypted Data. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 196–214. Springer, Heidelberg (2009)
  9. 9,0 9,1 Hazay, C., Nissim, K.: Efficient Set Operations in the Presence of Malicious Ad- versaries. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 312–331. Springer, Heidelberg (2010)
  10. 10,0 10,1 10,2 Jarecki, S., Liu, X.: Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg (2009)
  11. Yao, A.C.: Protocols for secure computations. In: FOCS, pp. 160–164 (1982)
  12. Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersec- tion. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg (2004)
  13. Naor, M., Pinkas, B.: Oblivious polynomial evaluation. SIAM Journal on Comput- ing 35(5), 1254–1284 (2006)
  14. Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 47–53. Springer, Heidelberg (1985)
  15. Aumann, Y., Lindell, Y.: Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 137–156. Springer, Heidelberg (2007)
  16. Camenisch, J., Shoup, V.: Practical verifiable encryption and decryption of discrete logarithms. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 126–144. Springer, Heidelberg (2003)
  17. 17,0 17,1 Belenkiy, M., Camenisch, J., Chase, M., Kohlweiss, M., Lysyanskaya, A., Shacham, H.: Randomizable Proofs and Delegatable Anonymous Credentials. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 108–125. Springer, Heidelberg (2009)
  18. Chaum, D.: Blind signatures for untraceable payments. In: CRYPTO (1983)
  19. Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSA- inversion problems and the security of Chaum’s blind signature scheme. Journal of Cryptology 16(3), 185–215 (2003)
  20. Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key Encryption with Keyword Search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)
  21. Boneh, D., Franklin, M.K.: Identity-based encryption from the weil pairing. SIAM Journal of Computing 32(3), 586–615 (2003)
  22. Boyen, X., Waters, B.: Anonymous Hierarchical Identity-Based Encryption (With- out Random Oracles). In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 290–307. Springer, Heidelberg (2006)
  23. Fujisaki, E., Okamoto, T.: Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997)
  24. De Cristofaro, E., Kim, J., Tsudik, G.: Linear-Complexity Private Set Intersec- tion Protocols Secure in Malicious Model, Cryptology ePrint Archive (2010), http://eprint.iacr.org/2010/469