Полностью устойчивые к утечкам подписи

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:03, 30 октября 2015.
Fully Leakage-Resilient Signatures
NTRU.PNG
Авторы Elette Boyle,[@: 1],
Gil Segev[@: 2],
Daniel Wichs[@: 3]
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__


Аннотация. Схема подписей будет полностью устойчивой к утечкам (согласно Кацу и Вайкунтанату, ASIACRYPT '09), если она неподдельна при адаптивной атаке на сообщение, даже в условиях, когда противник может получить ограниченную (произвольную) информацию по всем промежуточным значениям, используемым в системе. Это сильное и значимое понятие безопасности, которое охватывает широкий круг атак по побочным каналам. Одной из основных задач при построении таких схем является работа с утечкой, которая может зависеть от случайных битов, используемых алгоритмом подписи, и, кроме того построение таких схем известно лишь для модели случайных алгоритмов. Более того, даже в моделе случайного алгоритма известные схемы устойчивы только к утечкам меньше половины длины ключа.
В этой работе мы создаем схемы полностью устойчивые к утечкам без случайных алгоритмов. Мы приводим схему, которая является устойчивой к любым утечкам длины бит, где L это длина ключа. Наш подход основывается на общих криптографических примитивах, и в тоже время допускает достаточно эффективные исполнения на основе конкретных числовых предположений. Кроме того, мы показываем, что наш подход распространяется и на непрерывную модель утечки, недавно введенную Додисом, Хараламбием, Лопес-Альтом и Вихсом (FOCS '10), а также Бракерски, Калайем, Кацом и Вайкунтанату (FOCS '10). В этой модели, ключ подписи может быть обновлен, в то время как его соответствующий проверочный ключ остается фиксированным, и объем утечки считается ограниченным только между любыми двумя последовательными обновлениями ключей.

Введение

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

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

Атаки с памятью: ограниченные и продолжительные утечки. Модель атак с памятью была введена Акавием, Гольдвассером и Вайкунтанатом [2]. Основной предпосылкой является то, что противник может узнать произвольную информацию о состоянии системы, при единственном условии соблюдения ограничения, что объем информации ограничен. Точнее, противник может адаптивно выбирать вычислительную функцию, работающую за полиномиальное время и знать значение , отвечающее за внутреннее состояние системы для некоторых ограниченных выходных размеров .

В работе [2] предполагается, что существует априорно определенная граница утечек , которая ограничивает общий объем информации, полученный противников от всей системы, значением . Мы называем это моделью с ограниченными утечками. Обычно граница утечек также связана размеров секретного ключа, так что относительно большая доля секретного ключа может утечь. Многие исследования занимались разработкой различных криптографических примитивов в этой модели, например, с схемы шифрования с открытым ключом и на основе идентификации подписей (см. [3] [4][5][6][7] [8] [9]).

Недостатком ограниченной дифференциальной модели является то, что, если система используется постоянно в течение достаточно длительного времени, то объем утечки к противнику может превысить априорно определенные границы. Таким образом, мы бы хотели ограничить размер утечки, а не общее количество утечек. Если мы не ограничим общую утечку, то любая статическая часть информации, которая остается неизменной в системе может в конечном итоге быть полностью восстановлена противником. Следовательно, секретные ключи таких систем должны периодически обновляться. В последнее время Додис и соавт. [10], Бракерски и соавт. [11] предложили продолжительную модель утечек, в которой схема периодически сама обновляет свой внутренний секретный ключ, в то время как соответствующий открытый ключ остается фиксированным. В этой модели, только объем утечки, обнаруженный противником между любыми двумя последовательными обновлениями системы считается априорно ограниченным некоторой границей . Тем не менее, нет никакой априорной оценки общего объема информации, доступной противнику для всей системы.

Отметим, что в обоих моделях противник может узнать частичную, но все же произвольную, информацию о секретном ключе. В отличие от других моделей, где, либо утечка считается «низкой сложности» (как для цепочек) [12][13], либо определенные секретные значения считаются не имеющими утечек.

Схемы подписей устойчивые к утечкам. В этой работе мы изучаем безопасность схем подписей для моделей с ограниченными и продолжительными утечками. Схемы подписей в ограниченной моделе были предложены Алвеном, Додисом , и Вихсом [5], Кацом и Вайкунтанатом в [4], где основное внимание было уделено утечке (только) ключа подписи схемы. В частности, схема подписи устойчива к утечкам в ограниченной моделе, если она неподдельна против адаптивных атак на выбранные сообщения [14], даже если выбранные противником функции ключа подписи имеют адаптивную утечку. Схемы подписи, удовлетворяющие этому понятию безопасности были построены как на основе общих криптографических примитивов в стандартной модели [4], так и на основе Фиат-Шамирова преобразования [15] в моделе случайных алгоритмов [4][5].

Хотя это понятие устойчивости к утечкам уже охватывает несколько атак, оно не полностью применимо к общим атакам, которые могут зависеть от полного внутреннего состояния системы. В частности, проблема в том, что обе схемы подписей из [4][5] являются рандомизированными и, следовательно, внутренние состояние включает в себя, в дополнение к секретным ключам, все случайные значения, использованные алгоритмом подписания. Схемы могут быть уязвимы для атак, которые (также) зависят от этой случайности.

Это было уже отмечено Кацом и Вайкунтанатом в работе [4], где они выдвинули строгие понятия полностью устойчивых к утечкам схем подписей (в ограниченной модели). Это понятие требует, чтобы схема подписи оставалась неподдельной при адаптивных атаках, даже если противник получает ограниченную утечку информации обо всех промежуточных значениях, используемых за все время для системы, включая секретные ключи и внутренние случайные монеты (понятие может быть расширено для модели продолжительных утечек [11] [10]). Это строгое понятие лучше описывает реальные атаки, опираясь на модели для временных и мощностных затрат. Однако, известные в настоящее время, построения полностью устойчивых к утечкам схем доказуемо безопасны только для случая модели со случайными алгоритмами [5][11] [10][4]. Более того, даже для модели случайных алгоритмов, известные схемы являются устойчивыми для утечки не более чем половины длины ключа подписи [5][10][4], или требуют обновления ключа после каждых нескольких исполнений алгоритма подписания, даже при отсутствии утечки [11] (это необходимо даже в ограниченной моделе, в которой обновление не является частью стандартного исполнения). В стандартной модели, только построения "одноразовых" подписей из [4] будут полностью устойчивы к утечкам. В параллельных работах Малкина, Тераниши, Вахлиша и Юнга [16] предлагаются альтернативные схемы подписи в продолжительной моделе. Хотя эти схемы кажутся сильно отличающимися на первый взгляд, они могут рассматриваться в качестве отдельных видов общей стратегии, которую мы рассмотрим далее.

Наши достижения

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

Затем мы расширим наш подход для продолжительной модели, опираясь на модель с односторонними утечками, недавно введенную Додисом, Хараламбиевым, Лопесом и Вихсом [10]. Наша результирующая схема подписей наследует свойство устойчивости к утечкам от односторонней модели, при последовательных ключевых обновлениях во время алгоритма обновления. В частности, наша схема для существующих построений односторонних отношений [10][11] дает схему, которая является устойчивой к утечке случайных битов, используемых для алгоритма обновления, а любая утечка длины битов между любыми двумя обновлениями ключа, на основе симметричных внешних Диффи-Хелмановских (SXDH) предположений, или битов между обновлениями на основе предположения по принятию решений.

Наконец, отметим, что наш подход дает первое разделение между ограниченными моделями утечек, которое было предложено Наором и Сегевом [3], а позже уточнено Додисом и другими. [[10], определение 7.2]. Шумовая утечка это реалистичное обобщение ограниченной утечки, в которой утечка не обязательно имеет ограниченную длину, и гарантируется, что секретный ключ все еще имеет некоторую энтропию, даже при утечке. Это приводит к открытой проблеме, согласно Наору и Сегеву.

Обзор нашего подхода.

В этом разделе мы представляем обзор нашего подхода для построения полностью устойчивой к утечкам схемы подписей. Мы сосредоточимся на нашем построении в ограниченной модели, так как это уже подразумевает идеи, лежащие в основе нашего подхода, и мы отсылаем читателя к полной версии работы для обзора нашего построения в продолжительной моделе. Мы начнем с более точного описания понятия полностью устойчивой к утечкам схемы подписи в ограниченной моделе. Далее мы кратко опишем схему подписи Каца и Вайкутаната[4], которая служит в качестве отправной точки, и объясним основные проблемы в построении полностью устойчивой к утечкам схемы подписей. Основная часть этой работы сфокусирована на нашем построении. Моделирование полностью устойчивых схем подписей. Схема подписи будет полностью устойчивой к утечкам в ограниченной моделе, если она неподдельна для противников, которые могут получить, как подписи для любого сообщения, так и ограниченную утечку информации для всех промежуточных значений, используемых при подписании для всей системы. Этот момент формализуется за счет рассмотрения эксперимента, включающего в себя автора и противника. Во-первых, автор вызывает алгоритм генерации ключей и получает ключ проверки и ключ подписи . В таком случае, значение state инициализируется для содержания случайных монет,использованных алгоритмом генерации ключей. Противнику дается ключ проверки и он может адаптивно представить два типа запросов: запрос подписания и запрос утечек. Запрос подписания состоит из сообщения m, и осуществляется за счет запуска алгоритма подписания ключа и сообщения. После каждого такого запроса, случайные монеты, использованные в алгоритме подписания, добавляются к state. Запрос утечки состоит из функции утечек , применяемой к state. Функция утечки должна быть эффективно вычислимой, а сумма длин выходов должна быть ограничена сверху заранее определенным параметром . Противник будет успешным, если он выводит пару (), где это сообщение, для которого подписывается запрос, а является подписью для при ключе проверки . Мы отсылаем читателя к разделу 3 для формального определения.

Схема Каца Вайкунтаната. Предложенная этими авторами схема подписи [4] опирается на устойчивый второй прообраз (SPR) функции (для некоторых ), CPA-безопасной схеме шифрования с открытым ключом,и NIZK системе доказательств. Ключом подписания будет значение , а ключом проверки набор , где это открытый ключ для схемы шифрования, а является общей ссылкой на строку из системы доказательств. Подпись для сообщения состоит из шифротекста , зашифровывающего с использованием , и доказательства того, что шифротекст c действительно шифрует для некоторых .

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

  1. Типичные ключи проверки имеют много возможных секретных ключей. В частности, множество имеет размер примерно .
  2. "Реальные" подписи схемы вычислительно неотличимы от «поддельных» подписей, статистически независимых от ключа подписания. Это вытекает из семантической безопасности схемы шифрования и из системы доказательств с нулевым разглашением. В частности, "поддельные" подписи для сообщения могут быть получены путем шифрования , а затем с помощью NIZK симулятора для получения доказательств.
  3. Учитывая ключ расшифровки для соответствующих , любые допустимые подделки противника могут быть использованы для извлечения прообраз из y. Это следует из обоснованность системы доказательств, гарантирующей, что подделка противникабудет "реальной" подписью и, следовательно, соответствующий шифротекст можно будет расшифровать в действительный прообраз .

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

Основные проблемы. Доказательство безопасности схемы Каца-Вайкунтаната основывается на том аргументе, что, учитывая большое количество подписей для выбранных сообщений и битов утечек из ключа подписания , противнику все равно сложно угадать значение . Однако, когда утечка может зависеть также и от случайности, используемой алгоритмом подписания, это не выполняется и схема будет небезопасной в целом. Основная проблема заключается в том, что в предыдущих рассуждениях мы использовали возможность замены "реальных" подписей за "поддельные". Этот шаг, в свою очередь, опирался на безопасность схемы шифрования и доказательства с нулевым разглашением. Тем не менее, мы не можем полагаться на эти свойства, если противник может также получать утечку случайных монет схемы шифрования и системы доказательств! Рассмотрим, например, схему с CPA безопасной схемой шифрования, определенной как , где является безопасной схемой шифрования и PRG это псевдослучайный генератор, применяемый для случайного узла . Утечка из узла , длина которого может быть произвольно короче , полностью раскрывает ключ подписи . Аналогичное исполнение для системы доказательства может имеет подобное свойство, когда утечки зависят от случайностей, используемых при доказательстве.

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

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

Сложность заключается в получении схемы шифрования, в которой шифротексты независимы от сообщения (в нашем случае от ключа подписи ), которое они зашифровывают. В частности, это явно противоречит скрытости для шифротекста. Мы можем представить это с помощью известных схем шифрования, где ключ шифрования может быть получен в одном из двух неотличимых режимов: «инъективном» режиме, который позволяет проводить расшифровку, и в режиме "с потерями", в котором шифртекст статистически скрывает сообщение. Но важно помнить, что мы должны удовлетворять следующим двум свойствам одновременно: (1) способности отвечать на запросы противника поддельными подписями, которые не раскрывают никакой информации о , (2) умению извлекать свидетеля из подделки противника. Установив в любом из этих режимов, можно добиться одного из данных свойств, но не обоих одновременно! Основным инструментом для решения этого конфликта является разработка схемы шифрования с потерями, где шифрование некоторого сообщения теряется, в то время как другие остаются неизменными.

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

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

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

Отметим, что в модели со случайными алгоритмами есть простое преобразование от селективной безопасности к полной безопасности, оно проводится за счет подписания выходов случайных алгоритмов, примененных к сообщению. Кроме того, в стандартной моделе существует простое преобразование с потерей безопасности, просто за счет "угадывания" подделки: это может привести к полной безопасности схемы при некоторых экспоненциальных допущениях. Наконец, существует общее преобразование (согласно [17]) за счет хэширования сообщения с хамелеонной хэш-функцией [18] и подписания каждого хэш индекса по отдельности. К сожалению, это приводит к длинным подписям. Все эти универсальные методики также работают при полной устойчивости. Мы предлагаем альтернативу, которая не обладает указанными недостатками.

Для фактической схемы мы следуем подходу Боне и Бойена [19] для преобразования выборочно-защищенной схемы шифрования в полностью безопасную, за счет использования хэш-функций (см. раздел 2.3). В данном случае применяется более тонкая "стратегия разметки" вместо стратегии "все, кроме одного" для выборочной безопасных схем. В частности, мы вводим понятие схемы шифрования открытого ключа с потерями. Это обобщение ALBO схемы шифрования, где множество возможных маркеров разбивается на инъективные маркеры и маркеры с потерями по отношению к (в частности, может быть больше одного инъективного маркеры). Основная идея этого подхода заключается в обеспечении с большой вероятностью того, чтобы все запросы противника попадали в раздел "потерей", в то время как подделки попадают в «инъективный» раздел.

Сравнение с работой [16]. Альтернативный способ сочетает SNIWI схемы с теговым шифрованием. Наш основной результат показывает, как построить полностью устойчивые к утечкам подписи из такой системы доказательств. Работа [16] может рассматриваться, как альтернативный вариант этой стратегии, опирающейся на Грот-Сахаеву NIZK схему [20]. Эти NIZK схемы либо статистически неразличимы, либо зависят от выбора CRS.

Структура работы.

В разделе 2 мы вводим некоторые предварительные понятия и обозначения. Раздел 3 содержит определение безопасности в ограниченной дифференциальной моделе. В разделе 4 мы вводим схему шифрования открытого ключа с потерями, инструмент, используемый в наших построениях. Раздел 5 содержит различные построения и доказательства безопасности нашей схемы в ограниченной дифференциальной моделе. Наконец, в разделе 6 мы приводим несколько заключительных замечаний и открытые проблемы. Мы отсылаем читателя к полной версии статьи для конкретных построений нашей схемы, основанных на линейном предположении и расширении схемы до продолжительной модели.

Предварительные сведения.

В этом разделе мы приведем некоторые основные инструменты, используемые в наших построениях.

Устойчивость второго прообраза.

Множеством эффективно вычислимых функций будет пара алгоритмов (KeyGen, F), где KeyGen является вероятностным алгоритмом, который для входа выводит для функции . Такое множество устойчиво для второго прообраза (SPR), если для случайно выбранного входа и для случайно выбранной функции вычислительно невозможно найти такой вход , что и . Это упрощает понятие для множества универсальных односторонних хэш-функций, введенных Наором и Юнгом [21], в котором вход х может быть выбран в состязательной форме (но, по-прежнему, независимо от функции ).

TemplateDifinitionIcon.svg Определение «Определение 2.1 (Устойчивость второго прообраза). »
Множество эффективно вычислимых функций является устойчивым для второго прообраза, если для любого вероятностного алгоритма выполняется для некоторой незначительной функции , где вероятность берется по и по внутренним случайностям для KeyGen и

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

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

Статистические неинтерактивные системы доказательств для неразличимых свидетелей.

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

TemplateDifinitionIcon.svg Определение «Определение 2.2 (SNIWI система).  »
Статистической неинтерактивной системой доказательств с неразличимыми свидетелями для языка L с отношением свидетелей будет тройка таких алгоритмов (CRSGen, P, V), для которых выполнены
  1. Идеальная полнота: для всех выполняется , где ,а вероятность берется по внутренним случайностям из
  2. Адаптивная правильность: Для всех вероятностных проверок выполнено
    для некоторой незначительной функции
  3. Статистическая неразличимость свидетелей: Существует такой вероятностный алгоритм , что:
  • Распределения и вычислительно неразличимы.
  • Для любого такого набора , где и , распределения и являются статистически неразличимыми, где

Подобные системы подразумеваются построением Грота, Островского и Сахайя [24], удовлетворяющему строгому понятию неинтерактивной системы доказательств с нулевым разглашением. Их построения могут быть основаны либо на сложности проблемы принятия решения для подгрупп [25], либо на проблеме принятия решений в линейной задаче [26]. Как отмечалось Гротом, их алгоритм CRSGen допускает выборку (в частности, распределение общей строки статистически близко к равномерному), которая является техническим свойством, необходимым для нашего построения в ограниченных моделях.

Допустимые хэш-функции.

Концепция допустимых хэш-функция впервые была определена Боне и Бойеном [19] для преобразования выборочно безопасных схем шифрования в полностью безопасные. В данной работе мы используем такие хэш-функции похожим образом для преобразования выборочно безопасных схем подписей (там, где противник заранее подделывает сообщение, прежде чем получить ключ проверки) в полностью безопасные. Основная идея допустимых хэш-функции заключается в том, что они позволяют сократить доказательство безопасности за счет разделения пространства сообщений на такие два подмножества, которые мы обозначим как красное (R) и синее (B), что существует существенная вероятность того, что все сообщения из запросов противникабудут в синем подмножестве, а подделка будет в красном подмножестве. Это полезно, когда симулятор может эффективно ответить на запросы подписей в синем наборе, но при сложном определении подделки сообщения в красном множестве. Наши определения допустимых хэш-функции схожи с Кэшом, Хофхайнцем, Килцем и Пайкертом [27].

Для , мы определяем функцию , «раскрашивающую» пространство маркеров следующим образом:

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

TemplateDifinitionIcon.svg Определение «Определение 2.3 (Допустимые хэш-функции [19][27]).»
Мы говорим, что будет множеством допустимых хэш-функций, если для всех существует множество таких строк, что выполняются следующие два свойства:
  • Для каждого вероятностного алгоритма существует незначительная функция , удовлетворяющая .
  • Для любого многочлена существует и такое эффективно вычислимое , что для всех , и мы имеем:

Отметим, что для идентифицирующего шифрования [19][27] плохие наборы должны быть эффективно узнаваемы, что не требуется в нашем случае. Кроме того, мы говорим, что является множеством допустимых хэш-функций, если оно удовлетворяет определению 2.3, даже когда алгоритм принимает в качестве входа внутреннюю случайность, использованую для отбора функции.

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

Моделирование устойчивых к утечкам схем подписей.

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

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

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

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

TemplateDifinitionIcon.svg Определение «Определение 3.1 (FLR безопасность - ограниченная утечка). »
Схема подписи является -полностью устойчивой к утечкам в ограниченной дифференциальной моделе, если для любого вероятностного противника выполнено, что вероятность успеха пренебрежимо мала в n, где событие задается как:
  • 1. Берется , вычисляется , и задается .
  • 2. Противник получает в качестве входа пару , и может адаптивно провести запрос алгоритмов, определяемых следующим образом:
  • Запрос подписи. Алгоритм подписания получает в качестве входа сообщение , отбирает , а затем вычисляет . Обновляется и выводится .
  • Запрос утечек. Алгоритм утечек получает в качестве входа описание эффективно вычислимой функции и выводит . Мы называем выходной длиной j-й функции утечки.
  • 3.Противник выводит пару .
    4. отвечает за событие, в котором:
  • не запрашивалось алгоритмом подписания
  • сумма выходной длины всех функций утечек не превосходит .

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

Шифрования с открытым ключом с R потерями.

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

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

TemplateDifinitionIcon.svg Определение «Определение 4.1 (PKE схемы с R потерями).  »
Пусть будет эффективно вычислимым бинарным отношением. Схемой шифрования с потерями будет такой набор алгоритмов , что:
  1. Генерация ключей: Для любых значений , алгоритм генерации ключей KeyGen для входа выводит секрет ключ и открытый ключ .
  2. Расшифровка для инъективных тегов: Для таких любых значений и маркера , что , и для любого сообщения выполнено
    для некоторой незначительной функции , где , а вероятность берется по внутренним случайностям для KeyGen, Enc и Dec.
  3. Случай тегов потери: Для любого значения и тега , при , для каждой пары ключей , созданной , и для каждой пары сообщений , распределения и будут статистически неразличимы.
  4. Неразличимость начальных значений: Для любой последовательности пар , когда , два множества и будут вычислительно неразличимы.

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

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

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

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


В нашем построении схемы подписи шифрования с потерями будет использоваться в сочетании с допустимыми хэш-функциями (приводятся в разделе 2.3).

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

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

Схема подписей в моделе с ограниченными утечками.

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

  • Пусть будет множеством открытых устойчивых для второго прообраза функций для некоторого (см. раздел 2.1).
  • Пусть будет множеством допустимых хэш-функций (см. раздел 2.3).
  • Пусть будет схемой шифрования с потерями. (См. раздел 4).
  • Пусть будет SNIWI системой доказательств для языка (См. раздел 2.2).

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

  • Генерация ключей: Для входа , алгоритм KeyGen отбирает равномерно распределенное , описание функции из SPR множества, и вычисляет . Далее отбирается описание допустимых хэш-функций , значения и для открытого ключа схем шифрования с потерями и общая строка для SNIWI системы доказательств, соответственно. Выводится ключ подписи и ключ проверки .


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

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


  • Проверка: Для сообщения и подписи на входе, алгоритм Verify вызывает испытание системы доказательств и выводит 1 только когда .

Заключительные замечания и открытые проблемы.

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

Ограниченные утечки против шумовых утечек. В некоторых случаях не всегда возможно предположить, что общая сумма утечек ограничена сверху битами. Это привело к появлению подхода Наора и Сегева [3] (впоследствии уточненного Додисом и соавт. [13[10], определение 7.2]), где рассматриваются более общие понятие шумовых утечек, и где утечка не обязательно имеет ограниченную длину, но гарантированно уменьшает среднюю энтропию секретного ключа не более чем на . Хотя наши схемы безопасны по отношению к ограниченным утечкам, они, на самом деле, небезопасны по отношению к шумовым утечкам. Это, кажется, первый раз когда предлагается разделение между ограниченными утечками и шумовыми утечками, и это приводит к открытой проблеме, поставленной Наором и Сегевым.

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

Моделирование сложных утечек для схем подписей. В случае шифрования открытого ключа были предложены более общие модели утечек на предположении, что ключ не может быть эффективно восстановлен для заданной утечки (см.[28][29][30][8]). Для схем подписей, однако, это не ясно, как осмысленно формализовать такие атаки. Было бы интересно формализовать такие сложные схемы (особенно, когда возможна утечка промежуточного значения, а также построить схемы, которые являются устойчивыми к утечкам в такой модели.

Благодарности.

Мы благодарим Мони Наора, Брента Уотерс, и участников Eurocrypt '11 за полезные замечания по этой работе.


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

  1. Massachusetts Institute of Technology, Cambridge, MA 02139, USA , E-mail: [1]
  2. Microsoft Research, Mountain View, CA 94043, USA, E-mail: [2]
  3. New York University, New York, NY 10012, USA, E-mail: [3]

Примечания

Литература

  1. Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984)
  2. 2,0 2,1 Akavia, A., Goldwasser, S., Vaikuntanathan, V.: Simultaneous hardcore bits and cryptography against memory attacks. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 474–495. Springer, Heidelberg (2009)
  3. 3,0 3,1 3,2 Naor, M., Segev, G.: Public-key cryptosystems resilient to key leakage. In: Halevi,S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 18–35. Springer, Heidelberg (2009)
  4. 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 4,10 4,11 4,12 4,13 Katz, J., Vaikuntanathan, V.: Signature schemes with bounded leakage resilience.In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 703–720. Springer, Heidelberg (2009)
  5. 5,0 5,1 5,2 5,3 5,4 5,5 Alwen, J., Dodis, Y., Wichs, D.: Leakage-resilient public-key cryptography in the bounded-retrieval model. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp.36–54. Springer, Heidelberg (2009)
  6. Alwen, J., Dodis, Y., Naor, M., Segev, G., Walfish, S., Wichs, D.: Public-key encryption in the bounded-retrieval model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 113–134. Springer, Heidelberg (2010)
  7. Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 382–400. Springer, Heidelberg (2010)
  8. 8,0 8,1 Brakerski, Z., Goldwasser, S.: Circular and leakage resilient public-key encryption under subgroup indistinguishability (or: Quadratic Residuosity strikes back). In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1–20. Springer, Heidelberg (2010)
  9. Dodis, Y., Haralambiev, K., Lopez-Alt, A., Wichs, D.: Efficient public-key cryptography in the presence of key leakage. Cryptology ePrint Archive, Report 2010/154 (2010)
  10. 10,0 10,1 10,2 10,3 10,4 10,5 10,6 10,7 Dodis, Y., Haralambiev, K., Lopez-Alt, A., Wichs, D.: Cryptography against continuous memory attacks. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 511–520 (2010)
  11. 11,0 11,1 11,2 11,3 11,4 Brakerski, Z., Tauman Kalai, Y., Katz, J., Vaikuntanathan, V.: Cryptography resilient to continual memory leakage. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 501–510 (2010)
  12. Ishai, Y., Sahai, A., Wagner, D.: Private circuits: Securing hardware against probingattacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481.Springer, Heidelberg (2003)
  13. Faust, S., Rabin, T., Reyzin, L., Tromer, E., Vaikuntanathan, V.: Protecting circuits from leakage: the computationally-bounded and noisy cases. In: Gilbert, H.(ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 135–156. Springer, Heidelberg(2010)
  14. Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure againstadaptive chosen-message attacks. SIAM Journal on Computing 17(2), 281–308(1988)
  15. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263,pp. 186–194. Springer, Heidelberg (1987)
  16. 16,0 16,1 16,2 Malkin, T., Teranishi, I., Vahlis, Y., Yung, M.: Signatures resilient to continualleakage on memory and computation (2010) (manuscript)
  17. Brakerski, Z., Tauman Kalai, Y.: A framework for efficient signatures, ring signaturesand identity based encryption in the standard model. Cryptology ePrint Archive, Report 2010/086 (2010)
  18. Krawczyk, H., Rabin, T.: Chameleon signatures. In: Proceedings of the Network and Distributed System Security Symposium (NDSS) (2000)
  19. 19,0 19,1 19,2 19,3 19,4 Boneh, D., Boyen, X.: Secure identity based encryption without random oracles.In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 443–459. Springer,Heidelberg (2004)
  20. Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In:Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer,Heidelberg (2008)
  21. Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st Annual ACM Symposium on Theory ofComputing, pp. 33–43 (1989)
  22. Hsiao, C.-Y., Reyzin, L.: Finding collisions on a public road, or do secure hash functions need secret coins? In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152,pp. 92–105. Springer, Heidelberg (2004)
  23. Rompel, J.: One-way functions are necessary and sufficient for secure signatures.In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing,pp. 387–394 (1990)
  24. Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP.In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer,Heidelberg (2006)
  25. Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In:Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg(2005)
  26. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.)CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004)
  27. 27,0 27,1 27,2 Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp.523–552. Springer, Heidelberg (2010)
  28. Dodis, Y., Tauman Kalai, Y., Lovett, S.: On cryptography with auxiliary input.In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing,pp. 621–630 (2009)
  29. Dodis, Y., Goldwasser, S., Tauman Kalai, Y., Peikert, C., Vaikuntanathan, V.:Public-key encryption schemes with auxiliary inputs. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 361–381. Springer, Heidelberg (2010)
  30. Goldwasser, S., Tauman Kalai, Y., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: Proceedings of the 1st Symposium on Innovations in Computer Science, pp. 230–240 (2010)