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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:13, 24 декабря 2015.
Key-Dependent Message Security: Generic Amplification and Completenes
NTRU.PNG
Авторы Damien Stehle[@: 1],
Ron Steinfeld[@: 2]
Опубликован 2011 г.
Сайт Homepage of Damien Stehle, Homepage of Ron Steinfeld
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Схемы шифрования сообщений, зависящих от ключа (Key-dependent message - ), остаются защищенными даже при условии, что противник находит соответствие секретных ключей sk и шифрованных сообщений. А именно, схема должна оставаться защищенной даже при шифровании сообщений вида f(sk), где - из некоторого класса функций . Процедура усиления поизводится над -KDM безопасной схемой и преобразует ее в G-KDM безопасную схему, где G-класс более богатый чем . Недавно было показано Бракерски и Бараком, что возможна сильная форма усиления при условии, что изменяемая схема удовлетворяет дополнительным требованиям.

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

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

Ключевые слова:

Введение

Изучение безопасной схемы шифрования, пожалуй, самый центральный предмет вкриптографии. С момента открытия семантической безопасности до разработки CCA-безопасности, современная криптография успешно развила более сильные понятия безопасности, обеспечивающие секретность в высоко состязательных настройках. Тем не менее, все эти сильные понятия безопасности гарантируют секретность только до тех пор,пока зашифрованные сообщения не зависят от секретного ключа. Это ограничение восходит к плодотворной работе Голдвассера и Микали, которые заметили, что семантическая безопасность не может иметь место, если противник поймет шифрование секретного ключа. На протяжении многих лет, такие сценарии использования расценивались как «безопасность ошибки ", которая должна быть предотвращена конструкторами системы.

Десять лет назад, предположение о независимости между секретным ключом и зашифрованными данными было оспорено Camenisch и Lysyanskaya и Блэком и др. Конкретно, Camenisch и Lysyanskaya считали схемы, которые остаются в безопасности при использовании «цикла ключа», где мы имеем ключей, организованных в цикл и каждый ключ шифруется под левого соседа. Обобщение этого понятия, называется безопасностью сообщений,заввисящих от ключа(KDM), было предложено Блэком и др. Неформально, шифрование KDM(t) безопасно по отношению к классу функции , если безопасность поддерживается даже когда противник может попросить шифрования сообщения М = (sk1,..., skt) под i-ым открытым ключом, где sk1,. .. ,skt являются секретными ключами, присутствующими в системе и является произвольной функцией в . Эта понятие безопасности предполагает циклическую безопасность , если достаточно многозначна (например, содержит все "селектор" функции), и она становится строго мощнее, когда функциональный класс растет. Следовательно, хотелось бы, чтобы обеспечить KDM безопасность, делая функциональный класс как можно больше.

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

Хотя многое известно сегодня о безопасности как с положительной так и с отрицательной стороны, до сих пор неясно, может ли схема стандарта шифрования быть трансформирована в схему, которая обеспечивает KDM(t) безопасностm, даже по отношению к единственному ключу (т.е., ) и простым нетривиальные семействам функций (например, селекторы). Следственно, естественно двигаться вперед и изучать возможность построения сильной KDM безопасности, учитывая слабую форму безопасности,как примитива. Это имеет смысл ,так как согласно плодотворной работе Боне и др. и их последователей, известно, что основная форма безопасности (по отношению к семейству "связанных функций ") может быть достигнута несколькими настройками под различные конкретные криптографические предположения. Поэтому, согласно [14], мы спрашиваем:

Существует общее преобразование, которое усиливает безопасность от слабого семейства функций до большего семейства функций ?

Двумя основными особенностями такой процедуры являются общность – транформация должна работать с любой схемой, которая удовлетворяет безопасности, не полагаясь на любое другое дополнительное свойство - и большой разрыв амплификации - в идеале, - очень простой класс функций, в то время как G является таким мощным, насколько это возможно. Вопрос расширения недавно был рассмотрен Brakerski и др[14] и Бараком и др. [10], которые сделал значительный прогресс, показывая, как усилить безопасность нескольких существующих схем. В то время как эти работы достигают относительно большой разрыв амплификации, они лишены обеспечения полной общности, так как они сильно зависят от дополнительных свойств базисной схемы (т.е. понятия моделируемая - безопаность и энтропийная - безопасность – определим позже). В качестве конкретного примера, неизвестно, как использовать любой из этих методов, чтобы усилить -безопасность симметричного ключа шифрования схеме [5], который основан на предположении изучения паритета с шумом (LPN). (Смотрите раздел 1.3 для более подробной информации о этих работах и их отношение к нашему подходу.)

Наши результаты

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

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

Общность. Теорема 1 не несет ничего, кроме безопасности в отношении подразумеваемой схемы. Кроме того, теорема (и ее удивительно простое доказательство) нечувствительна к точной настройке безопасности: оно имеет место для любого числа ключей(t), и в обоих случаях симметричный ключ / открытый ключ и CPA / CCA настройки. Во всех этих случаях, будет доказано, что новая схема будет безопасна с теми же настройками, что и оригинальная схема. Это позволяет нам, например, усилить безопасность связанной- безопасной схемы[5], и получить первую схему с симметричным ключом шифрования с сильной безопасностью на основе предположения LPN.

Большой разрыв. Теорема 1 обеспечивает большой разрыв амплификации. На самом деле, этот разрыв может быть далее увеличен следующим образом. Во-первых, мы можем достичь KDM безопасность, зависящуют от длины [10], что означает, что целевое семейства G могут быть принято за семейство всех схем полиномиального размера, размеры которых растут с их длиной на входе и выходе через фиксированную полиномиальную скорость (например, размер схемы является квадратичным на длине входа и выхода). Это семейство очень мощное , и как было показано, достаточно изобильно для большинства известных приложений KDM безопасности [10] . (См раздел 3 для детального описания.) Кроме того, в случае CPA безопасности (как в настройках открытого ключа, так и симметричного), мы можем ослабить требование от основной схемы и запросить KDM безопасность по отношению к проекциям с одним выходом: а именно, все булевы функции , выход которых один бит одного из ключей или его инверсия. Это может быть расширено до параметров CCA с помощью преобразований [9, 15] (хотя в параметрах открытого ключа нужно использовать, кроме того, не-интерактивные доказательства с нулевым знанием).

Ослабление проекций с одним выходом также позволяет прогрессивный интерфейс, к которому мы можем легко подключить предыдущие конструкции. Например, можно создать экземпляр уменьшенной копии схем, которые пользуются безопасности KDM по отношению к связанным функциям, в то же время почти игнорируя технические детали, такие как основное поле и его представление. (Эти детали потребовали некоторых усилий в предыдущих работах. Смотрите приложения в [14, 10, 13].) Вместе с простым доказательством нашей основной теоремы, это позволяет упростить доказательства [10, 13] для существования KDM безопасной схемы шифрования, зависящей от длины согласно Decisional Diffie-Hellman (DDH) предположению [12], [5] the Learning With Errors(LWE), и the Quadratic Residuosity (QR) предположение [13].

Учитывая эту теорему полноты, текущее состояние KDM безопасности имеет сходство с другими "полными" примитивами в в криптографии, такими как односторонние функции или неочевидный обмен[32, 19]: Мы не знаем, как построить эти примитивы из общих слабых предположениях, однако, любой экземпляр связывает весь мир приложений (т.е., все примитивы с симметричным ключом в случае односторонних функций, и общее безопасное вычисление в случае обращая перевод, ср [22, 23]).

За пределами безопасности,зависящей от длины. Несмотря на то, KDM безопасность, зависящая от длины кажется отвечает большинству приложений, можно стремиться к еще более сильному понятию безопасности, в котором класс функций KDM содержит все функции (или эквивалетно все функции вычислимые схемами произвольного полиномиального размера). Весьма вероятно, что любая безопасная схема, зависящая от длины на самом деле достигает полной KDM безопасности (см обсуждение в [10]). Тем не менее, можно захотеть построить такую схему доказуемо безопасным способом. В качестве основного технико-экономического результата, было показано в [10], что любая полностью гомоморфная схема шифрования [20], который позволяет зашифровать секретный ключ (т.е., "циклически безопасный") также полностью KDM безопасно. В свете небольшого количества кандидатов FHE [20, 17], и наше маленькое понимание этого понятия, можно спросить, возможно ли ослабить это требование и добиться полной KDM безопасности при более слабых предположениях.

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

Наша Второе замечание утверждает, что метод самонастройки джентри [20], может быть также использован в KDM настройке (даже в случае немоделируемой конструкции). То есть, если можно построить схему шифрования которая гарантирует KDM безопасность по отношению к цепям, глубина которых немного больше, чем глубина алгоритма дешифрования, то эта схема действительна полностью KDM безопасно. К сожалению, все известные методы амплификации[10, 14] в том числе и в данной работе, усиливают KDM безопасность делая алгоритм дешифрования "глубже". Тем не менее, мы считаем, это замечание является интересным направлением для будущих исследований.

Наши методы

Чтобы сформулировать вопрос амплификации, мы определяем понятие сокращения между функцией семейств что означает, что любая схема, которая обеспечивает безопасность по отношению к может быть преобразованы (с помощью сокращения полного черного ящика) в новую схему, которая удовлетворяет безопасности по отношению к . Мы опишем новый способ получить таких сокращения на основе техники рандомизированных функций кодирования [29, 7]. Прежде, чем мы объясним это понятие, давайте начнем с более простого случая детерминированного кодирования.

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

Эта простая идея обеспечивает прямое снижение с очень хорошей структурой: любой запрос для новой схемы переводится в единственный запрос для оригинальной схемы. Этот простой один запрос-в-один запрос перевод ведетк высокому уровню общности: преобразование нечувствительно к точной настройке (симметричный ключ / открытый ключ и CPA / CCA), к числу ключей, и может быть использовано по отношению к большим семействам функция и , так как каждый функция из кодируется некоторой функцией из в через пару универсальных отображений и . C одной стороны, можно пожаловаться, что безопасность не была действительно усилена, так как функция и его кодирования , по существу, эквивалентны. Оказывается, этот недостаток может быть легко исправлен, позволив быть рандомным кодированием . В случае рандомного кодирования (RE), функция зависит не только от , но и от дополнительного случайного входного . Для каждого фиксированного , выход в настоящее время рассматривается как распределение (индуцированное случайным выбором r), котороое должно кодировать значение . А именно, есть два электронной эффективно вычислимых случайных отображения S и R такие, что для любого : (1) рапределение S (g(х)) неотличимо от , и (2) с высокой вероятностью выбора r(или даже с вероятностью единица) . Можно расссматривать эти условия, заявив, что кодируется набором функций {fr (х)} r, где fr(х) = f(х, r).

Теперь предположим, что наша схема KDM безопасна по отношению к семейству {fr (х)} r , затем мы можем применить изложенный выше подход и получить схему, которая удовлетворяет безопасности по отношению к g. Единственное отличие состоит, что в настоящее время шаг сообщения предварительной обработки рандомизирован: чтобы зашифровать сообщение сначала нужно закодировать его на рандомизированном отображении S (M), а затем использовать оригинальную функцию шифрования. Снижение безопасности, по существу, то же самое за исключением того, что запрос для в новой схеме эмулируется старым запросом для случайно выбранной функции fr..Эта идея может быть легко расширена на случай, когда все функции в кодируются функциями из :

Теорема 2 (неформальная). Если является RE О, то . Суть этой теоремы является то, что, в отличие от детерминированного кодирования, рандомное кодирование может представлять сложные функции наборами очень простой функций [29, 30, 7, 6]. Конкретно, путем объединения теоремы, описанной выше с RE кодированиями [6], которые, в свою очередь, основаны на искаженной цепи Яо [34], мы получаем наш главные результаты (Теорема 1).

Сравнение c BGK и BHHI

Наши методы вдохновлены и [14] (BGK), [10] (BHHI). Мы считаем, что наш подход наследует положительные черты каждой из этих работ, и проливает новый свет на то, как они относятся друг к другу. Рассмотрим основные идеи этих конструкций и объясним, как они соотносятся с нашим решением.

Снижение BGK Отправной точкой в работе [14] является схема шифрования, которая удовлетворяет энтропийной безопасности по отношению к . Грубо говоря, это означает, что безопасность должны поддерживаться не только тогда, когда выбрано равномерно от пространства ключа kно также и при его выбирают равномерно от подпространсва , а именно . Опираясь на это утверждение, BGK показывает, что для каждого эффективно вычисляемого инъективного отображения , можно усилить безопасности от к классу, т.е., по отношению к функциям для каждой . Идея состоит в том, чтобы выбрать ключ из и использовать оригинальную схему с ключом . Это позволяет перевести запрос для новой схеме в энтропийный-KDM запрос для старой схеме.

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

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

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

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

BHHI построение такой схемы шифрования путем объединения двустороннего безопасно вычислимого протокола с двумя сообщениями (т.е. на основе искаженной цепи Яо [34]) с сильной версией рассеянного перевода, который удовлетворяет дополнительному свойству циклической безопасности. Последнее примитивно называют целевым шифрованием(TE). Основная идея заключается в том, чтобы отобразить гомоморфное свойство в качестве безопасно вычисляемой задачи, в которой первая часть содержит сообщение , а вторая часть содержит функцию . Циклический характер ТЕ примитива позволяет использовать этот гомоморфизм, даже если вход является секретным ключом. Наконец, BHHI показывает, что ТЕ может быть построена на основе схемы связанного безопасного шифрования, которое удовлетворяет сильному понятию моделирования: существует симулятор, который учитывая открытым ключом pk может имитировать зашифрованный текст таким образом, что является неотличимы даже для тех, кто обладает секретным ключом.

Строительство BHHI кажется концептуально отличным от нашего подхода RE (т.е. гомоморфизм против кодирования). Кроме того, само строительство не только синтаксически отличимо, но также полагается на различны блоки построения (например, ТЕ). Все еще, построение RE разделяет важную идею с BHHI: использование безопасных методов вычислений. Известно, что RE тесно связаны с многопартийными протоколами вычисления (МPC), и, действительно, роль RE в нашем снижении напоминает роль МPC в BHHI. В обоих решениях в какой-то момент снижение безопасности применяет RE / МPC для функции из g в g. Более того, обе работы достигают высокий уровень безопасности иллюстрируя RE / МPC примером искаженной схемой Яо (GC) - это инструмент, который ведет к автономному построению RE[6], так и к безопасному протоколу вычисления, состоящему из двух частей, когда оснащен OT.

Следует подчеркнуть, однако, что фактические конструкции различаются в некоторых важных аспектах. В то время как мы, по существу шифруем кодировку целиком основанное на GC в основной схеме шифрования модифицирует GC протокол с циклически безопасным OT (т.е. TE). Графически, наша основная KDM безопасная схема "обертывает" кодировку GC, в то время как в безопасный примитив "посажен внутри" протокола GC. Это различие влияет как на общность, так и на простоту следующим образом.

Во-первых, BHHI вынуждено осуществлять безопасный OT, примитив, который кажется, гораздо сильнее, чем стандартные KDM безопасные схемы шифрования. Например, безопасные схемы шифрования с симметричным ключом может быть построена на наличии случайного оракула [11], в то время как протоколы OT не могут [28] . Кроме того, как мы уже упоминали, хотя ТЕ может быть основано на нескольких известных безопасно связанных схемах (например, те, которые позволяют сильное моделирование), предположение LPN (с постоянной частоту ошибок) является конкретным примером, при которых безопасная схема шифрования с симметричным ключом связывает существующие функции, пока не известно о OT. Кроме того, поскольку BHHI отправляет искаженные схемы в открытом виде, не трудно показать, что в результирующая схема не CCA-безопасной, даже если TE обеспечивает безопасность CCA. Наконец, модификация протокола GC приводит к относительно сложному доказательству безопасности.

Вводная часть

Для положительного целого числа n ∈ N, пусть [n] обозначим множество {1,…, n}, и равномерное распределение по {0, 1} n обозначим Un. Функция ε (n) пренебрежимо мала, если она стремится к нулю быстрее, чем 1 / nc для любой константы с> 0. Термин эффективный относится к вероятностным машинам, которые работают за полиномиальное время в параметре безопасности.

Эффективные функции и рандомные функции. Рандомная функция f: {0, 1} * ×{0, 1} * → {0, 1} * это функция, второй вход которойрассматривается как случайный вход. Мы пишем f (x, r), чтобы обозначить оценку f на детерминированном входе х и случайном входе r, и, как правило, положим, регулярность длины и эффективную оценку следующим образом: существуют эффективно вычислимые многочлены m (n) и ℓ (n) и эффективно вычислимое семейство схем {fn: {0, 1} n {х 0, 1} m (n) → {0, 1} ℓ (n)}, которое вычисляет ограничение f на n-битных детерминированных входных данных. Если функция не регулярной длины, мы предполагаем, что семейство схем индексируется парой входной и выходной параметров (n, ℓ), и требует оценки за полиномиальное время(n, ℓ). Наконец, детерминированная функция соответствует частному случаю, когда m(n) = 0.

Функциональные множества. Функциональное множество это набор функций {fz} z∈Z проиндексированое набором индексов Z ⊆ {0, 1} *, где для каждого z функция fz имеетконечная область {0, 1}n(z) и конечный спектр {0, 1}ℓ (z), где n, ℓ: {0, 1} * → N. По умолчанию, мы предполагаем, что эти множества эффективно вычисляемы, то есть, функции n (z), ℓ (z), а также функция F (z, х) = fz (х) вычислимы за полиномиальное время (|z|). Следовательно n (z), ℓ (z) <poly(| z |). Мы также предполагаем, что |z| <poly(n(z), ℓ (z)).

Рандомное кодирование функций. Интуитивно, рандомное кодирование функции g(х) является рандомным отображением F (х; r), распространение выхода которого зависит только от выхода g. Мы формализуем эти интуитивные знания с помощью понятия частного вычисляемого рандомного кодирования [6], в то время как принятие первоначального определения от неравномерной противостоящей настройки до унифицированной настроки (т.е. перехватчики моделируются вероятностным полиномиальным времени машины Тьюринга). С другой стороны функция g ={ gn: {0, 1}n {→ 0, 1} ℓ (n)}и рандомная функция f={fn :{0, 1}n × {0, 1}m (n) → {0, 1}s(n)}, обе из которых являются эфеективно вычисляемыми. Мы говорим, что f кодирует g, если существуют алгоритмы восстановления Rec и эффективного моделирования Sim, которые удовлетворяют следующему:

- Идеальная корректность. Для каждого х ∈ {0, 1}n, вероятности ошибок Pr [Rec (1n, f(х, U(n))) ≠g(х)] и Pr [Rec(1n, Sim(1n, g(х))) ≠ g(х)] оба нулевые.

- Вычислительная конфиденциальность. Для каждого для каждого эффективного перехватчика А у нас есть Pr [Af (·, U) (1n) = 1] - Pr [А Sim(g(·)) (1n) = 1] <neg(n),

где оракулы определены следующим образом: положим, что первый оракл x возвращает образ из f(x; Um (| х |)), а второй оракул возвращает образ из Sim(1| х |, g(х)).

Это понятие естественно распространяется на функции gn, ℓ, не имеющие регулярную длину и индексирующиеся как и по входной, так и по выходной длинам. Тем не менее, мы всегда предполагаем, что конфиденциальность параметризована только по длиной входного сигнала (т.е. противника работает без стажа / отличительная вероятность должна быть полиномом / принебрижима по длине входного сигнала.) Обратите внимание, что, без потери общности, мы можем предположить, что отношение длины выхода ℓ всегда известна дешифрования и моделирования (т.е. всегда может быть закодирована как часть на выходе fn, ℓ).

Схемы шифрования (синтаксис). Схему шифрования состоит из трех эффективных алгоритмов (KG, E, D), где KG – алгоритм генерации ключа, которому далипараметр безопасности 1k выводит пару (sk, pk) ключей шифрования и дешифрования; Е –алгоритм шифрования, который принимает сообщение M ∈ {0, 1} * и ключ шифрования pk и выводит зашифрованный текста C; D – алгоритм дешифрования, который принимает зашифрованный текст С, и ключ дешифрования sk и выводит исходный текст M '. Мы также предполагаем, что оба алгоритмы принимают параметр безопасности 1k в качестве дополнительного входа, но, как правило опускаем эту зависимость для простоты. Корректность требует, чтобы ошибка дешифрования

max┬(M∈{0,1}*)⁡□(〖_((sk,pk) )〗←┴█(Pr@R) 〖_KG(1k) 〗 [D_sk (E_pk (M))≠M] )

была незначительным для k, где вероятность берется по случайности KG, E и D. Для параметра безопасности к, обозначим Кk пространство, из которого выбраны ключи дешифрования. Без потери общности, мы всегда предполагаем, что Кk = {0, 1} k.

Согласно Голдрейху [23], отметим, что определение, данное выше, соответствует схеме шифрования как и с открытым ключом, так и с симметричным ключом, где последния соотствует частному случаю, когда ключ дешифрования sk и ключ шифрования pk эквиваленты. Как мы увидим, различие между двумя настройками будет частью определений безопасности.

KDM безопасность

Пусть схема шифрования с пространством ключей . Положим является функцией. -арное функциональное KDM множество является является эффективным с множеством функций

 . Обозначим  набор . 

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

Результаты сведения и полноты

KDM сведения с помощью рандомного кодирования

Пусть F = {f k, z} и G = {g k,w} пара функциональных KDM множеств с одинаковой крастностью t = t(k). Мы говорим, что F кодирует G, если каждая функция g (х) в G имеет рандомное кодирования F(х,r), такое что для каждой фиксации случайной строки r, результирующая функция fr (х) в F. Более формально, функция оценки Gk (z, х) из G должен иметь рандомное кодирование Fk ((r, х), r), что для каждого фиксации r и индекса r, функция F k,z,r (х) = F (k, z, х; r) соответствует функции Fk,w в F, где отображение из (z, r) в w должно быть эффективнотивно вычисляемо в полиномиальное (k) время. Обратите внимание, это означает, что симулятор и декодер универсальны для всех индексов z, а зависят только от величины k. Теорема 3 (основная теорема). Предположим, что функциональное KDM множество кодирует функциональное KDM множество G. Затем, G КДМ-сводится к F через типосохраняющее сведение. Чтобы доказать теорему, мы должны описать конструкцию и безопасное сведение. Отныне, пусть Sim и Rec – универсальные алгоритмы моделирования и восстановления, которые устанавливает кодировку G по F.

Построение 4. Учитывая оракульный доступ к схеме шифрования Е = (KG, E, D), мы определим схему Е следующим образом

KG (1k) = KG (1k) Еpk (М) = Еpk (Sim (М))

Dsk (С) = R (Dsk (С)),

где все алгоритмы (т.е., шифрование, дешифрование, симулятор и восстановление) получитьпараметр безопасности, 1k в качестве дополнительного входа.

Не трудно заметить, что ошибка дешифрования схемы Е такая же, как ошибка дешифрования Е, так как неправильное дешифрование Еpk (М) происходит только тогда, когда Еpk (М’) неправильно определена где M’←Sim(M).

Мы показываем, что безопасность E может быть основан на безопасности Е. Учитывая оракульный доступ к (Т, G) противника А, который атакует Е, мы обозначим (Т, F) противником B, который атакует E случайно выбирая одну из двух стратегий B0 и B1.

Снижение 5 (Противник B A,E). Бросок монеты σ ← {0, 1}. Если σ = 1 вызываем следующего противника B1.

- Инициализация: В вызывает A. Если A запрашивает ключи шифрования затем B делает аналогичный запрос и передает ответ на А.

- Запрос шифрования: Если А делает запрос шифрования (i, M), для i ∈[t] и М ∈ {0, 1} *, то B образуем М '= Sim (M), передает (I, M') в качестве запроса шифрования (wrt к Е) и передает ответ соперника к А.

- KDM запрос: Если А делает запрос KDM (i, g), для i ∈ [t] и , то противник B делает следующее: Она равномерно выбирает случайности r для рандомного кодирования F (·; r) r (·), и запрашивает KDM запрос (i, fr), где fr (·) = F (·; r), которsq, по нашему предположению, в F. Ответ соперника направляется к А.

- Расшифровка запроса: Если А совершает запрос дешифрования (i, С), то B проверяет, является ли он законным (путем проверки всех предыдущих дешифрования / KDM запросов), и если таким образом, (1) передает один и тот же запрос дешифрования сопернику, (2) применяет алгоритм восстановления Rec к результату и (3) отправляет его обратно к А.

- Окончание: В выходит тогда же, когда и А.

Если σ = 0, то вызоваем противника B0. Это противник подобен B1 за исключением того, что шифрование и KDM запросы к А оба переведены в запросы шифрования следующим образом: дан запрос шифрования из А вида (i, M) (соотв., KDM запрос вида (i, r)), противник B0 образует М '= Sim (0ℓ) и запрашивает зашифрованный текст Epki (М '), где ℓ длина М (соотв., длина выхода g). В конце, В0 сбрасывает выход А и выходит.

Обратите внимание, что сведение, описанное выше действительно типа сохранения. Давайте сперва сфокусируемся на противнике B1. Если бит соперника равен 1 (то есть, соперник находится в "реальном режиме"), тогда различие между эмулируемым видом А и видом А в реальной игре KDM, заключается только в разнице способа получения KDM запроса. В реальных игровые ответы на KDM запросы вычисляются правильно, как Epki (g(sk)) = Epki (Sim(g(sk))), в то время как в эмулированной игре, они вычисляются с помощью Epki (f(sk; U)). Однако, это различие не должно быть заметным из-за конфеденциальности рандомного кодирования. Формально, пусть αb k)(соотв., βσ,b (к)) обозначена вероятность того, что А (соотв., Bσ) предполагает вызов бита, когда он принимает значение b. Затем,

Лемма 2. | β1,1 (к) - α1 (к) | ≤ neg (K).

Доказательство. Мы определяем следующие различитель D, который, учитывая оракульный доступ к либо Р (·; U) или Sim (G (·)), предпринимает попытки различить оба. Противник D эмулирует соперника с битом б = 1. Он генерирует вектор ключей (ski, pki) i∈ [t], выполняя алгоритм генерации ключей KG (1k) t раз. Тогда D вызывает A. Если A выполняет KDM запрос (i, gz), то D вызывает его оракул со значением G (z, sk1,..., skt). Обозначим через М ответ оракула. Различитель вычисляет зашифрованный текст C = Epki (м) и посылает зашифрованный С к А. Если А выполняет другие типы запросов, таких как запросы открытых ключей, запросы шифрования и запросы дешифрования, то различитель D отвечает на них должным образом так, как делает реальный соперник, когда он находится в режиме реального времени Ь = 1. (Для случая из запроса дешифрования (i, С), различитель проверяет, что он является законным путем проверки всех предыдущие запросов KDM / шифрования, и если да, посылает Dski (С)). Различитель останавливает , когда выход равен 1, и только если выходы А равны 1.

Обратите внимание, что: (1) Если D получает оракульный доступ к Sim(G (·)), то вид распределяется именно так, как в реальной игре и поэтому в данном случае выходы D равны 1 с вероятность α1(к); (2) Если D получает оракульный доступ к F (°, U), то вид А распределены так, как в приведенном выше сведении, когда В1 имитирует игру с b = 1, и поэтому в данном случае выходы D равны 1 с вероятностью β1,1 (к). Следовательно, по соглавно конфиденциальности кодирования, отсюда следует, что | β1,1 (к) - α1 (к) | ≤ neg (k).

Мы утверждаем, что в настоящее время нечто подобное происходит в "фальшивом" режиме, когда b = 0; а именно, β1,0 близок к α0. Тем не менее, в этом случае в реальном игре KDM запросы обработаны с Epki (0ℓ) = Epki (Sim (0ℓ)), в то время как в игре, имитируемой B1 эти запросы обработаны с Epki (0s), где ℓ = |g(sk1,... skt) | и S = | F (sk1,... skt; U...) |. Хотя конфиденциальность кодирования гарантирует, что открытые тексты имеют одинаковую длину, то есть, s=| Sim (0ℓ) |, фактические распределения открытых текстов могут различаться, и поэтому может быть так, что два взгляда отличны. По этой причине нужен противник B0, который ломает стандартную (не KDM) безопасность E, когда такой разрыв существует. Формально, мы покажем, что в среднем вероятность успеха B1 и B0 примерно половина вероятности успеха А. С этой целью мы докажем следующее

Лемма 3. β0,1 (K) = а0 (к) и β0,0 (к) + β1,0 (K) = 1.

Доказательство. Во-первых, отметим, что, когда бит соперника b= 1, то вид А, как имитируемый B0 совпадает с видом А в поддельной режиме реальной игры (b = 0). Действительно, в обоих случаях KDM запрос (i, g) (соотв., является запросом шифрования (i, М)) обработанным с Epki (0 | ℓ |) = Epki (Sim(0ℓ)), где ℓ длина выхода g (соотв., ℓ = |М|). Следовательно, β0,1, вероятность того, что выходы B0 равны 1, когда соперник находится в реальном режиме, точно вероятность того, что выходы A равны 0 в реальной игре, когда соперник находится в поддельном режиме. (Напомним, что B сбрасывает выход A). Отсюда следует первое равенство.

Для доказательства второго равенства мы потребуем, чтобы, когда бит соперника равен 0, то вид А ,имитированный B0, совпадал с видом A, имитированным В1. В самом деле, только единственное отличие состоит, что в первом случае KDM запросы (i, g) обработаны Е (0 Sim (f(sk;r)|), в то время как во втором случае ответ Е (0 |F (Sk; r)|). Длины выходов f и Sim (g (·)) фиксированы (для любого g ∈ G) и, следовательно, должны быть равны (иначе конфиденциальность кодирования нарушается), отсюда и следуют требования. Требование подразумевает, что β0,0 (к) + β1,0 (K) = 1, как выходы В1 исходят от А, и B0 сбрасывает их.

Из объединения двух лемм (2 и 3), следует, что преимуществоВ β =(β1,1 + β1,0 + β0,0 + β0,1) / 4 – ½ , по меньшей мере ½ α-neg(K), где α = 1/2 (α1 + α0) - ½ это преимущество A. Следовательно, мы установили корректность сведения.

Замечание 1. Теорема 3 имеет место, даже если само кодирования использует основное шифрование схемы ε, так долго, пока это использование осуществляется в полностью путем черного ящика (то же относится к любому криптографическому примитиву, который может быть основан на ε путем сведения к черному ящику, например, односторонняя функция). Точнее, наши результаты справедливы (т.е. ведут к KDM сведению /построению черного ящика) пока, безопасность кодирования сводится к безопасности основного примитива (то есть, ε) путем сведения к черному ящику, и пока симулятор и дешифратор мугут быть реализованы, получив доступ к черному ящику для основного примитива. Точно так же, такой доступ к черному ящику может быть предоставлен алгоритму, который отображает фиксированные пары индекс / случайность (z, r) с индексом w функции gk,w= Gk,z,r(х).

Полнота проекций

О полной KDM безопасности

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

Схема шифрования с открытым ключом является моделируемом безопасной, если существует симулятор S с полиномиальным временем такой, что для любого , и каждое семейство схем размера , множество S (pk,fk) является неотличимым от Еpk (fk(sk)). (Заметим, что это означает, что в различитель содержит секретный ключ SK.) Понятия моделируемой циклической безопасности и моделируемой полной KDM безопасности соответствуют двум крайним случаям, когда содержит только тождественные функции, и содержит все функции.

FHE позволяет перевести шифрование сообщения в шифрования родственного сообщения для любой схемы полиномиального . Более формально, мы говорим, что ε полностью гомоморфна, если существует эффективный алгоритм такой, что для каждого , каждого семейства схем размера , и каждой последовательности сообщений , ансамбль Eval (рк, HK, ЕПК (Мк)) является вычисляемо неотличимым от множества .

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

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

Доказательство. Получив моделируемую полностью безопасную схему шифрования с симулятором , мы определим , вызывая на парy , где отображение . Обратите внимание, что размер схемы полином в схема размера h (так как является эффективным). Кроме того, по определению, у нас есть для каждого (sk,pk) ∈ KG (1k), последовательность {Мк} и последовательность {Нк},

   
                                     ,
                                        ,

где обозначаем статическую (вычисляемую) неразличимость. Далее, мы показываем, что если убрать требование моделируемости, то любая схема шифрования , который обеспечивает, безопасность по отношению к функции, которая немного сильнее, чем ее алгоритм дешифрования D, на самом деле полностью безопасна. Это делается, заметив, что «метод самонастройки» Джентри может быть адаптирован к настройке. Предложение 3. Пусть , и пусть будет - KDM безопасное шифрование по отношению к проекциям с одним выходом и по отношению к семейству функций , где степени над и длина шифрования однобитового сообщения с секретным ключом длины . Далее, ε полностью безопасный тип . Доказательство (Набросок). В настройке достаточно доказать полную безопасность по отношению к схемам с единственным выходом. Мы покажем, как преобразовать злоумышленника, который передает произвольные запросы в того, кто использует только запросы от . Пусть схема размера , который состоит из NAND шлюзов, обозначим функцию, вычисляемую по -ому шлюзу , где шлюзы упорядочены в некотором топологическом порядке. Мы переводим KDM запрос для h в t KDM вызовов к , пересекая схему снизу вверх, со шлюза на шлюз, сохраняя следующий инвариант: Я-й запрос будет обработан таким зашифрованным текстом что, если оракул в реальном режиме Ci = Еpk (hi(sk)) и если он находится в поддельном режиме Сi = Epk (0). При входном шлюзе, это может быть достигнуто непосредственно путем единственного запроса с проекцией с одним выходом. Чтобы сделать это для внутреннего шлюза hℓ, входные провода которого подключены к hi и hj в течение некоторого i,j <ℓ, мы используем запрос к . Благодарность. Мы благодарим Iftach Haitner, Юваль Ишай, и анонимных рецензентов за их полезные замечания.

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

  1. CNRS, Laboratoire LIP (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL), 46 Allée d’Italie, 69364 Lyon Cedex 07, France, E-mail: damien.stehle@gmail.com
  2. Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, NSW 2109, Australia, E-mail: ron.steinfeld@mq.edu.au

Примечания

Литература