Эффективная криптография с открытым ключом в условиях утечки ключа

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:48, 8 декабря 2015.
Efficient Public-Key Cryptography in the Presence of Key Leakage
Efficient public-key cryptography key leakage.png
Авторы Yevgeniy Dodis[@: 1], Kristiyan Haralambiev[@: 2], Adriana Lopez-Alt[@: 3], and Daniel Wichs[@: 4]
Опубликован 2010 г.
Перевели Dmitriy Yankelevich
Год перевода 2015 г.
Скачать оригинал



Аннотация. Мы изучаем конструкцию криптографических примитивов, устойчивых к обширному классу атак по сторонним каналам, называемых «атаками на память», когда атакующий может неоднократно и адаптивно узнавать информацию о секретном ключе при условии, что общий объем такой информации ограничен некоторым параметром . Несмотря на то, что изучение таких примитивов было начато только недавно Акавиа и др. [1], последующая работа уже дала много таких устойчивых к утечкам примитивов [2][3][4], в том числе подписи, шифрование, идентификация и схемы проверки подлинности ключей. К сожалению, все существующие схемы, - для каждых из четырех указанных выше примитивов, - не удовлетворяют хотя бы одному из следующих желательных свойств:
  • Эффективность. Несмотря на то, модель может быть универсальной, она должна иметь некоторые эффективные реализации, основанные на стандартных криптографических предположениях, и не полагаться на случайные оракулы.
  • Высокая безопасность. Модель должна должна удовлетворять самым строгим формулировкам безопасности (даже в условиях утечки). К примеру, шифрование должно быть устойчиво к атаке на основе подобранного шифртекста (CCA), в то время как подписи должны быть экзистенциально неподдельны.
  • Устойчивость к утечке. Должна быть возможность установить параметры схемы так, чтобы граница утечки могла быть сколь угодно близкой к длине секретного ключа.
В этой работе мы спроектируем первые алгоритмы подписи, шифрования, ID и AKA, которые преодолеют эти ограничения и удовлетворят все свойствам, описанным выше. Более того, все наши модели являются универсальными, в ряде случаев элегантно упрощая и обобщая предыдущие модели (которые не имеют каких-либо эффективных реализаций). Мы также введем несколько инструментов независимого интереса, такие как абстракции (и модели) tSE-NIZK аргументов, и новые отрицаемые DH-подобные AKA протоколы, основанные на любом CCA-безопасном алгоритме шифрования.

Введение

Традиционно, безопасность алгоритма шифрования анализировалась в идеализированной обстановке, где злоумышленник видит только определенное входное/выходное поведение алгоритма, но не имеет другого доступа к его внутреннему секретному состоянию. К сожалению, в реальном мире злоумышленник часто может знать частичную информацию о секретном состоянии путем различных атак с утечкой ключа. Такие атаки составляют большое разнообразие и включают в себя атаки по сторонним каналам [5] [6] [7] [8] [9] [10] , где физическая реализация криптографического примитива может выдавать дополнительную информацию, такую как вычислительное время, энергопотребление, радиационное/шумовое/тепловое излучение и т.д. Другой пример атаки с утечкой ключа - атака методом холодной перезагрузки Хальдерман и др. [11] , где злоумышленник может узнать (не полностью) информацию о содержании памяти машины даже после выключения машины. Алгоритмы, которые доказали безопасность в идеализированной среде, без утечек ключа, могут стать полностью небезопасными, если злоумышленник узнает даже небольшое количество информации о секретном ключе. Действительно, даже очень ограниченные атаки с использованием утечек показали разрушительные последствия для безопасности многих обычных алгоритмов.

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

Наша модель устойчивости к утечкам была введена недавно Акавиа и др. [1] , но уже привлекла много внимания у криптографического сообщества [2] [4] [12] . В частности, как мы рассмотрим позже, мы уже знаем много устойчивых к утечкам примитивов, в том числе такие фундаментальные примитивы, как алгоритмы подписи, алгоритмы шифрования, алгоритмы идентификации и протоколы проверки подлинности ключей. К сожалению, мы заметили, что все существующие алгоритмы, - для каждых из четырех указанных выше фундаментальных примитивов, - не удовлетворяют хотя бы одному из следующих желательных свойств:

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


Результаты

В этой работе мы разработали первые алгоритмы подписи, шифрования, ID и AKA, которые одновременно удовлетворяют свойствам эффективности, высокой безопасности и устойчивости к утечкам, упомянутым выше. Кроме того, все наши структуры являются универсальными. Это означает, что фактическая структура модульно определяется и объясняется с использованием более простых блоков, и ее защита от утечек ключа также доказана вне зависимости от того, как эти более простые блоки (надежно) реализованы. Однако, в отличие от прежних общих структур, которые не имеют каких-либо известных эффективных экземпляров (по крайней мере, с желаемой безопасностью и устойчивостью, которую мы ищем), наши структуры еще более общие, что позволит нам получить несколько эффективных экземпляров. Учитывая этот факт, не удивительно, что наши достижения можно примерно разделить на две категории: «концептуальные», позволяющие нам получить более общие (и, тем не менее, концептуально более простые) структуры, устойчивые к утечкам, и «конкретные», позволяющие нам реализовать наши общие схемы эффективно.

Концептуальные достижения

Как мы увидим, существующие алгоритмы (например, подписи или CCA-шифрования) могут быть в значительной мере разделены на две категории: потенциально эффективные алгоритмы, с некоторыми присущими ограничениями, не позволяющими им достичь приближения относительной утечки к (что также мешает нам использовать эти идеи в наших целях), и более теоретические алгоритмы [2] [4] , aобладающие хорошей относительной утечкой, но опирающихся на ss-NIZK [13] . Неформально, ss-NIZK доказательства остаются надежными, даже если злоумышленник сможет увидеть поддельные доказательства произвольных (даже ложных) утверждений. К сожалению, существующая криптографическая техника не позволяет нам реализовать нетривиальные ss-NIZK доказательства эффективно. С другой стороны, недавний выдающийся результат Грот-Сахаи [14] показал, что можно получить эффективные ss-NIZK доказательства для нетривиального класса языков. В то время как методы [15] могли быть применены к Грот-Сахаи доказательствам, чтобы достичь ss-NIZK, это нетривиальная «реализация», и полученные доказательства значительно менее эффективны, так как структура включает ИЛИ-доказательства для Грот-Сахаи языков. Таким образом, наша первая мысль состояла в том, чтобы полностью обобщить существующие структуры, делая их опирающимися на регулярные NIZK, в надежде, что такие NIZK могут быть обработаны с использованием мощных методов Грот-Сахаи.


В конце концов, это было именно то, что мы осознали. Однако, в процессе мы также абстрагировались от отличного понятия независимого интереса: «true-simulation extractable» (tSE) NIZK. Оно схоже с понятием ss-NIZK, [15] , но также включает в себя небольшое, но важное отличие: может ли злоумышленник иметь оракульный доступ к поддельным доказательствам произвольных (даже ложных) утверждений, или только к истинным. Интуитивно, как устойчивый к утечкам алгоритм CCA-шифрования Наор-Сегева [2] , так и устойчивый к утечкам алгоритм подписи Катц-Вайкунтанатан [4] , используют метод шифрования свидетеля для некого отношения , а затем доказывают ss-NIZK доказательство что шифртекст действительно содержит зашифрованное значение . Основная причина использования этого метода состоит в том, чтобы снизить извлечения настоящего свидетеля из любой «новой» пары , созданной злоумышленником (который видел множество подобных пар раньше). В этой статье мы будем абстрагироваться от этого свойства в понятии tSE, описанного выше (в котором пара составляет единое tSE-NIZK доказательство). Более того, мы покажем, что tSE определенно верная идея для обобщения и доказательства безопасности предыдущих структур. Это имеет два положительных момента. Во-первых, это делает общие структуры CCA-шифрования и подписей более интуитивно понятными, как для доказательства, так и для понимания. Например, традиционная парадигма двойного шифрования Наор-Юнга [16] для проектирования CCA-безопасных алогритмов из CPA-безопасных алгоритмов, также используемая [2] в контексте утечек ключа, может быть определена как «CPA-шифрование сообщения двумя ключами и доказательство эквивалентности шифртекста». Используя наш более общий «simulation-extractability» подход, теперь это трактуется как «CPA-шифрование и доказательство, что кто-то знает открытый текст». Мы считаем, что последняя точка зрения является не только более общей, но и также более интуитивно понятной в качестве объяснения трансформации «CPA-to-CPA». Она также придерживается изначальных знаний Ракоф и Саймон [17] , которые объединили CPA-шифрование с NIZK-POK для достижения CCA-шифрования, но в моделе, где отправитель также знает секретный ключ. Подобное обсуждение справедливо и для наших моделей сигнатур.

Во-вторых, мы показали общий способ построения tSE-NIZK, который позволяет избежать использование (дорого) ss-NIZK. Вместо этого, наш метод использует регулярные NIZK и любой CCA-безопасный алгоритм шифрования. Возможно удивительно, учитывая нынешнее развитие NIZK и CCA-шифрования, комбинация «CCA + NIZK» представляется гораздо более эффективным на практике, чем комбинация «CCA + ss-NIZK». В результате, мы смогли обеспечить общую основу для построения устойчивых к утечкам подписей и CCA-безопасных алгоритмов шифрования, наконец позволив нам эффективно реализовать наши алгоритмы (избежав использования ss-NIZK). Мы резюмируем наши результаты для алгоритмов подписи и CCA-безопасных алгоритмов в Таблицах 1 и 2, также сравнивая их с лучшими предыдущими моделями. Во всех этих таблицах «субоптиматьные» записи (для эффективности, безопасности, модели или относительной утечке предыдущих моделей) выделены курсивом, а большинство предшествующих строк также объясняются в работе в секции 1.2. Подчеркнем, что для подписей не было известно эффективной конструкции в стандартной модели до нашей работы, для любого нетривиального значения относительной утечки (не говоря уже о 1).

Как только мы получили эффективные устойчивые к утечкам алгоритмы подписей, мы смогли получить ID и AKA алгоритмы с такими же свойствами. Основанный на подписях AKA протокол не отрицаемый. Однако, мы также построили отрицаемый AKA протокол, основанный на нашей модели устойчивого к утечкам CCA-безопасного алгоритма шифрования. Мы резюмируем наши результаты для ID алгоритмов в Таблице 3, и для AKA протоколов в Таблице 4. Для подробной информации смотрите раздел 6.


Таблица 1. Предыдущие работы об устойчивых к утечкам подписях и их результаты
Ссылка Неподдельность Модель Утечка Эффективна?
[3] Экзистенциальная Случайный оракул 1/2 Да
[3] Энтропийная Случайный оракул 1/6 Да
[4] Экзистенциальная Стандартная 1 Нет
Данная работа Экзистенциальная Стандартная 1 Да
Таблица 2. Предыдущие работы об устойчивых к утечкам алгоритмах шифрования и их результаты
Ссылка Атака Модель Утечка Эффективна?
[1] [2] CPA Стандартная 1 Да
[2] CCA Стандартная 1/6 Да
[2] CCA Стандартная 1 Нет
Данная работа CCA Стандартная 1 Да
Таблица 3. Предыдущие работы об устойчивых к утечкам алгоритмах идентификации (ID) и их результаты
Ссылка Безопасность Модель Утечка Эффективна?
[3] Pre-Impersonation Стандартная 1 Да
[3] [4] Anytime Стандартная 1/2 Да
[4] (неявно) Anytime Стандартная 1 Нет
Данная работа Anytime Стандартная 1 Да
Таблица 4. Предыдущие работы об устойчивых к утечкам AKA протоколам и их результаты
Ссылка Модель Утечка Спорный? Эффективный?
[3] Случайный оракул 1 Нет Да
[3][4] Стандартная 1 Нет Да
Данная работа Стандартная 1 Нет/Да* Да
 * Наш первый AKA протокол не отрицаемый; а второй - отрицаемый

Конкретные достижения

Как мы объяснили выше, мы обычно сводили вопрос о построении эффективных устойчивых к утечкам ID алгоритмов и AKA протоколов к вопросу об эффективном реализации нашего устойчивого к утечкам алгоритму подписи и/или алгоритму шифрования. Такие экземпляры приведены в разделе 5. Мы также объяснили, как последние реализации стали возможными в нашей работе, так как мы дали обобщенную модель обоих примитивов, основанных на новом представлении о tSE-NIZK, а затем показали, что удовлетворение этого понятия может быть возможным при использовании обычных NIZK для соответствующих языков, не полагаясь на дорогие ss-NIZK. К сожалению, эффективные модели (даже обычных) NIZK, согласно Грот и Сахаи [14] , известны только для ограниченного класса языков в билинейных группах. Таким образом, получение конкретной эффективной реализации все еще требует довольно значительных усилий.

В частности, все блоки должны быть реализованы эффективно, и выражены в такой форме, что результирующее NP отношение удовлетворяет серьезным ограничениям, наложенными Groth-Sahai NIZK. К примеру, для постройки устойчивого к утечкам алгоритма CCA-шифрования необходимо иметь эффективный устойчивый к утечкам алгоритм CPA, поддерживаемые метки CCA-шифрования и алгоритм одноразовой подписи, соединенные вместе эффективным NIZK для сложного отношения «равенства открытого текста». Точно так же, для устойчивых к утечкам алгоритмов подписи нам нужно эффективное устойчивое к атакам нахождения второго прообраза (SPR, см. Определение 1) отношение и поддерживаемые метки CCA-шифрования, снова соединенные вместе эффективным NIZK для комплексного отношения. Неудивительно, что такие задачи обычно не могут быть реализованы простым сочетанием имеющихся алгоритмов из литературы. В лучшем случае, это потребует очень тщательного выбора параметров, чтобы все подходило, после чего последует цикл дальнейшей оптимизации эффективности. Обычно, однако, это требует разработки новых примитивов, чтобы обеспечить эффективный NIZK. К примеру, в этой работе, мы разработали два новых SPR отношения (см. Раздел 5), так как предыдущие SPR отношения плохо стыкуются с нашими алгоритмами CCA-шифрования. Чтобы подчеркнуть важность новых SPR отношений, отметим, что объединение предыдущих моделей с доказательствами Groth-Sahai потребует фиксирования «witness» побитово, чтобы добиться полной эктрагируемости.

В целом, мы получаем две разные эффективные реализации устойчивых к утечкам алгоритма подписи и алгоритма CCA-шифрования в стандартной модели, основанных на стандартных предположениях в билинейных группах (статических и «фиксированной длины»), называемых SXDH и DLIN. Высшая идея этих алгоритмов, как и их эффективность, описана в Разделе 5. Фактические низкоуровневые детали о том, как «объединить все воедино» наиболее эффективным способом, описано в полной версии [18].

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

Устойчивость к утечкам и атаки на память

Наша модель утечек, иногда называемая «атаками на память», была впервые предложена Акавиа и др. [1] , которые также построили CPA безопасные PKE и IBE алгоритмы в этой моделе по LWE предположению. Позже Наор и Сегев [2] обобщили основные идеи, стоящие за этими моделями, чтобы показать, что все алгоритмы, основанные на системах с доказательством хэша (см. [19] ) являются устойчивыми к утечкам. В частности, это привело к эффективным моделям, основанным на DDH и K-линейных предположениях, где относительная утечка секретного ключа могла быть сведена к 1. Более того, [2] показало также как достичь CCA-безопасности в этой или (1) опираясь на общую (и неэффективную) парадигму Наор-Юнг, где уровень утечки может быть сведен к или (2) используя эффективные системы с доказательством хэша с уровнем утечки приближенной к .К сожалению, кажется, что подход построения CCA-шифрования с системами с доказательством хэша по сути ограничивает уровень утечки ниже  : потому что секретный ключ состоит из двух компонент (один для проверки, что шифртекст правильно сформирован и один для расшифровки) и доказательства проваливаются, если один из компонентов утек в полном объеме. Работа [12] обобщает [2] еще и тем, что показывает, как построить устойчивый к утечкам IBE алгоритм, обычно основывающийся на ID системах с доказательствами хэша с несколькими реализациями.

Устойчивые к утечкам алгоритмы подписей в модели атаки на память мыли построены в модели случайного оракула [4] [3] , и в стандартной модели [4] . ]. Алгоритмы на основе случайных оракулов очень эффективны, но страдают от двух ограничений. Во-первых, они основаны на Фиат-Шамир [20] преобразовании, которое безопасно только в модели случайного оракула и ненадежно в общем случае [21] . Во-вторых, алгоритмы могут только переносить только утечки, которые достигают секретного ключа. С другой стороны, стандартные алгоритмы позволяют относительную утечку, стремящуюся к 1, но они основаны на общих ss-NIZK и не имеют эффективной реализации.

Работа [3] также строит ID алгоритмы и AKA протоколы. Для ID алгоритмов были рассмотрены два понятия безопасности: менее строгое понятие называется «pre-impersonation» устойчивость к утечкам, а более строгое называется полная устойчивость к утечкам. Несмотря на то, что эффективные алгоритмы в стандартных моделях были даны для обеих понятий, устойчивость к утечкам может быть сведена к 1 только для «pre-impersonation» устойчивости к утечкам, в то время как для другой данные алгоритмы могут переносить уровень утечки лишь . Для AKA алгоритмов построение было основанным на устойчивых к утечкам подписям (требующих только ослабленное понятие безопасности под названием энтропийно-неподдельные). Использование соответствующих алгоритмов подписи дало два типа моделей: эффективные модели в моделе случайного оракула и общие, но неэффективные модели в стандартной моделе (в обеих из которых утечка приближается к 1).

Другие модели устойчивости к утечкам

В литературе появились некоторые другие модели устойчивости к утечкам. Они отличаются от модели, описанной нами в том, что они ограничивают тип, а также количество информации, которую злоумышленник может узнать. К примеру, экспозиционно устойчивая криптография [22] [23] [24] изучает случай, когда злоумышленник может узнать только некоторое небольшое подмножество физических бит секретного ключа. Точно также [25] изучает как реализовать произвольное вычисление в условиях, когда злоумышленник может узнать небольшое подмножество физических проводов в сети. Совсем недавно, [26] изучали похожую проблему, когда злоумышленник мог увидеть несложную функцию проводов (например, ). К сожалению, эти модели не в состоянии овладеть многими значимыми атаками по сторонним каналам, такие как изучение веса Хэмминга битов или их соотношения.

В своей плодотворной работе, Микали и Рейзин [27] инициировали официальное моделирование атак по сторонним каналам под аксиомой, что «только вычисления позволяют информации утечь» (OCLI), где каждый вызов криптографического примитива позволяет утечь лишь битам, которые были доступны в этом вызове. Несколько примитивов были реализованы в этих условиях, включая потоковые шифры [28] [29] и подписи [30] . Совсем недавно, [31] построили общий компилятор, который может обеспечить безопасность всех примитивов в этих условиях, предполагая использование некоторых ограниченных компонентов без утечек и существование полностью гомоморфного шифрования. С положительной стороны, модель OCLI накладывает ограничения только на количества информации, полученной во время каждого вызова примитива, но не на общую информацию, которую злоумышленник может получить в течение службы системы. С другой стороны, эта модель не в состоянии обхватить многие атаки с использованием утечек, такие как атака методом холодной перезагрузки [11] , когда все содержимое памяти содержит утечки информации, даже если они никогда не были доступны.

Наконец, отметим модели устойчивости к утечкам, которые строго сильнее, чем модели атаки на память. Во-первых, ограниченная поисковая модель [32] [33] [3] [12] накладывает дополнительное требование на устойчивые к утечкам алгоритмы, настаивая, чтобы они обеспечивали способ увеличения секретного ключа (возможно до нескольких гигабайт), чтобы пропорционально увеличивать объем переносимой утечки, но без увеличения размеров публичного ключа, вычислений, эффективности алгоритма, длин шифртекстов или подписей. Работа [3] строит «энтропийные» алгоритмы подписи, ID и AKA протоколов данных условиях, в то время как работа [12] строит PKE и IBE алгоритмы в этой моделе. Другим укреплением является вспомогательная входная модель [34] [35] где утечка не обязательно ограничивается по длине, однако считается вычислительно трудно восстановить секретный ключ от утечки. Работа [34] строит симметричную шифрование в этой моделе, для укрепления LPN предположения, в то время как [35] строит симметричное шифрование для DDH и LWE предположений. Еще одно усиление модели атаки на память, предложенная [36] , требует только один алгоритм (параметризованный только параметрами безопасности), который может переносить по сути любое количество относительной утечки. В этой моделе, [29] строят симметричный алгоритм шифрования.


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

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

TemplateDifinitionIcon.svg Определение « Определение 1 (Устойчивые к утечкам строгие отношения) »
Отношение с рандомизированным PPT алгоритмом выборки является -устойчивым к утечке строгим отношением, если:
  • Для любого , имеем
  • Существует полиномиальный алгоритм, который определяет, что
  • Для всех PPT злоумышленник с доступом к оракулу утечки  :

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


TemplateDifinitionIcon.svg Определение « Определение 2 (Устойчивые к утечкам подписи) »
Алгоритм подписи -устойчив к утечкам, если PPT имеем в следующей игре:
  1. Генерация ключа: претендент запускает и дает
  2. Запросы подписи и утечки: дан доступ к оракулу утечки и оракулу подписи . Запрос к оракулу подписи состоит из сообщений к которому оракул отвечает .
  3. выводит и выигрывает, если и не дано в качестве запроса подписи.


TemplateDifinitionIcon.svg Определение « Определение 3 (устойчивый к утечкам CCA-безопасный алгоритм шифрования) »
Мы говорим, что алгоритм шифрования -устойчивый к утечкам CCA-безопасный алгоритм, если PPT имеем в следующей игре:
  1. Генерация ключа : претендент запускает и дает
  2. Запросы расшифровки и утечки : дан доступ к оракулу утечки и оракулу расшифровки . Запрос к оракулу расшифровки состоит из шифртекста , на который оракул отвечает .
  3. Генерация запроса : посылает открытые тексты претенденту. Претендент выбирает , и отправляет .
  4. Запросы расшифровки : дан доступ к оракулу расшифровки с ограничением, что не может отправить в качестве запроса расшифровки. Отметим также, что не дан доступ к оракулу утечки .
  5. выводит , и выигрывает, если

Мы относим 0-устойчивые к утечкам CCA-безопасные алгоритмы к просто CCA-безопасным

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


TemplateDifinitionIcon.svg Определение « Определение 4 (устойчивый к утечкам CPA-безопасный алгоритм шифрования) »
Мы говорим, что алгоритм шифрования -устойчивый к утечкам CPA-безопасный алгоритм, если PPT имеем в описанной выше игре с той лишь модификацией, что не имеет доступа к оракулу расшифровки. . Если алгоритм шифрования 0- устойчивый к утечкам CPA-безопасный алгоритм шифрования, мы просто называем его CPA-безопасным.


Моделирование экстрагируемости

Начнем с краткой ссылки на понятие NIZK [37] . Для наших целей будет немного более удобно использовать понятие NIZK аргумента из [38] . Заметим, однако, что определения и модели, данные в этом разделе могут быть расширены на случай NIZK доказательств.

Пусть будет NP отношением на парах с соответствующим языком . Аргумент NIZK для отношения состоит из трех алгоритмов с синтаксисом:

  •  : Создает CRS и ключ лазейки для CRS.
  •  : Создает аргумент такой, что
  •  : Проверяет, является ли аргумент корректным.


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

Комплектность : Для любого , если , то .

Обоснованность : Для любого PPT злоумышленник , где вероятность берется по .

Компонуемое нулевое разглашение : Существует PPT симулятор такой, что для любого PPT злоумышленника имеем в следующей игре:

  • Претендент определяет и дает .
  • выбирает и отдает претенденту.
  • Претендент определяет и дает .
  • выводит бит и выигрывает если .

Мы возвращаемся к понятию tSE-NIZK аргументов [39] [40] [41] [42] [15] , и определим новые примитивы, называемые tSE-NIZK аргументы. Кроме удовлетворения описанных выше свойств, NIZK аргумент является моделируемо извлекаемым, если существует PPT экстрактор который получает дополнительную лазейку в CRS, извлекает свидетеля из любого доказательства производимого с помощью вредоносной доказывающей стороны , даже если ранее видел некоторые смоделированные доказательства для других утверждений.Сделаем важное различие между нашим новым определением истинного моделирования экстрагируемости, где видит все доказательства только истинных утверждений , и более строгого понятия полного моделирования экстрагируемости, где может также видеть ложные утверждения. Как мы увидим, упомянутое выше понятие часто проще построить и его достаточно в наших приложениях.

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

Начнем с определения оракула симуляции . Запрос к оракулу симуляции состоит из пары и метки . Оракул проверяет, что . Если это так, то он игнорирует и выводит смоделированный аргумент , иначе выводит . Теперь дадим формальное определение истинного моделирования экстрагирумости.

TemplateDifinitionIcon.svg Определение « Определение 5 (f-экстрагируемость истинного моделирования) »
Пусть f есть фиксированная эффективная вычислимая функция и пусть есть NIZK аргумент для отношения , , удовлетворяющий свойствам полноты, надежности и нулевому разглашению, описанных выше. Говорим, что есть f- экстрагируемость истинного моделирования (f-tSE) с метками, если:
  • Помимо вывода CRS и ключа лазейки, также выводит ключ извлечения: .
  • Существует РРТ алгоритм такой, что для всех в следующей игре:
  1. Генерация ключа : Претендент запускает и отдает CRS .
  2. Запросы симуляции: дан доступ к оракулу симуляции , к которому он может адаптивно обращаться.
  3. Вывод злоумышленника : выводит кортеж .
  4. Извлечение : Претендент запускает .
  5. выигрывает, если (a) пара не является частью запроса симуляции, (b) , и (c) для всех таких, что имеем .

В случае, когда f является функцией идентичности, мы просто говорим, что есть экстрагируемость истинного моделирования (tSE).

Приведем несколько вариаций этого нового примитива. Во-первых, мы определяем одноразовую экстрагируемость моделирования, в которой злоумышленник дает только один запрос к оракулу симуляции . Во-вторых, определим понятие строгой экстрагируемости моделирования путем измененияswazzsaazzzssssssssssssa победного состояния так, что теперь необходимо вывести новую пару утверждение/аргумент вместо нового утверждения. Более формально, состояние 5а становится: новым кортежем , или , если не часть запроса симуляции, или, если является, аргумент становится отличным от однажды данного . Заметим, что мы можем в общем случае построить строгие f-tSE NIZK аргументы из (стандартных) f-tSE NIZK аргументов, если дополнительно использовать очень безопасную одноразовую подпись. В частности, доказывающая сторона теперь вычисляет стандартный f-TSE аргумент, подписывает его и прикрепляет проверочный ключ к публичной метке. Чтобы проверить, мы сначала проверяем, что подпись валидна и затем проверяет f-tSE аргумент.

Наконец, говорим о том, что NIZK аргумент f-экстрагируем при полном моделировании (f-aSE) (по аналогии с понятием ss-экстрагируемости в [15] ), если злоумышленник имеет доступ к модифицированному оракулу симуляции который отвечает на все запросы моделирования без проверки (и, следовательно, может также дать смоделированные аргументы ложных утверждений). В этой работе мы не будем пользоваться этой вариацией, но покажем его здесь, потому что, как мы увидим, это определение неявно используется в предыдущих работах. Однако, f-aSE более строгое утверждение, чем f-tSE, и оно не требуется, как мы увидим далее, так как f-tSE достаточно для построения устойчивых к утечкам подписей и CCA-безопасного шифрования.


Общие модели

В этом разделе мы покажем общие модели устойчивых к утечке строгих отношений, подписей и CCA-безопасных алгоритмов. В последних двух мы используем f-tSE NIZK примитив, который определен в Разделе 3. Наконец, мы покажем модель f-tSE NIZK аргументов.

Строгие отношения, устойчивые к утечкам

Начнем с показа того, как в общем случае построить устойчивое к утечкам строгое отношение из SPR отношения. Неформально, мы скажем о том, что отношение есть STR-отношение, если дана случайная пара и достаточно трудно найти такой, что . Формализируем это в следующем определении.

TemplateDifinitionIcon.svg Определение « Определение 6 (SPR отношение)»
Отношение с рандомизированным PPT алгоритмом выборки есть SPR, если:
  • Для всех , имеем .
  • Существует полиномиальный алгоритм, который определяет, что .
  • Для любого PPT алгоритма , где вероятность берется по .

Мы определяем прообраз энтропии в среднем случае для SPR отношения как , где случайные величины распределяются в соответствии с . (Мы отсылаем читателя к полной версии [18] для определения .)


TemplateTheoremIcon.svg Теорема Теорема 1
Если является SPR отношением, то оно также является -устойчивым к утечке строгим отношением для , где есть параметр безопасности.
Доказательство
Без доказательства.


Устойчивые к утечкам подписи

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

  •  : Вывод и , где .
  •  : Вывод , где . (Отметим, что - метка.)
  •  : Вывод .


TemplateTheoremIcon.svg Теорема Теорема 2
Если есть -устойчивое к утечкам строгое отношение и есть помеченный tSE-NIZK аргумент для , то алгоритм выше есть -устойчивый к утечкам алгоритм подписи.
Доказательство
Без доказательства.


Устойчивое к утечкам CCA-безопасное шифрование

Мы дадим общую модель устойчивого к утечкам CCA-безопасного шифрования из устойчивых к утечкам CPA-безопасного шифрования и строгих f-tSE NIZK аргументов. Пусть есть -LR-CPA-безопасный алгоритм шифрования и пусть – будет одноразовым строгим аргументом f-tSE NIZK для отношения , где (т.е. экстрактор нужен только для извлечения сообщения , но не для случайности шифрования). Покажем, как использовать для создания -LR-CCA-безопасного алгоритма шифрования. . Определим как:

  •  : Вывод , где .
  • : Вывод , где .
  •  : Разбор . Если проверяет, выводит , иначе выводит .


TemplateTheoremIcon.svg Теорема Теорема 3
Предположим, что является -LR-CPA-безопасным, а П есть строгий одноразовый f-tSE NIZK аргумент для отношения где для любого свидетеля мы определим . Тогда алгоритм описанный выше является -LR-CCA-безопасным.
Доказательство
Без доказательства.


Отметим, что если построение tSE NIZK допускает метки, то мы, естественно, можем расширить нашу модель, указанную выше до -LR-CCA-безопасного шифрования с метками просто положив метки шифрования в доказательства NIZK (и используя их, чтобы проверить доказательства).


f-tSE NIZK

Пусть будет любой эффективно вычислимой функцией, и пусть be an NP relation. будет NP отношением. Мы покажем, как построить f-tSE NIZK аргумент из любого CCA-безопасного алгоритма с метками и (стандартных) NIZK аргументов. Пусть есть CCA-безопасный алгоритм шифрования с метками и пусть есть NIZK аргумент для отношения . Определим f-tSE NIZK аргумент (с поддержкой меток) как:

  • : Вывод , где .
  •  : Вывод , где .
  •  : Разбор и запуск .


TemplateTheoremIcon.svg Теорема Теорема 4
Если есть CCA-безопасный алгоритм шифрования с метками и есть NIZK аргумент для отношения , то то есть f-tSE NIZK аргумент для отношения
Доказательство
Без доказательства.


Сравнение наших общих моделей с предыдущими работами

Идея использования SPR отношения для создания устойчивого к утечкам строгого отношения была присуща [3] [4] , и подробно описана в [43] для случая устойчивых к утечкам односторонних функций.

Наши модели устойчивого к утечкам CCA-безопасного шифрования и подписей из tSE NIZK имеют существенное сходство с предыдущими конструкциями. В частности, мы видим, что альтернативное построение tSE NIZK может быть достигнуто с помощью алгоритма CPA-шифрования вместо CCA-шифрования, и ss-NIZK аргумента системы [13] вместо стандартного. На самом деле, получающаяся модель даст экстрагируемый аргумент NIZK полного моделирования (aSE NIZK). Эта реализация aSE NIZK неявно используется [4] в их моделе устойчивых к утечкам подписей. Это также неявно используется парадигме Наор-Юнга «двойного шифрования» [16] [17] [13] [44] для CCA-безопасности, которая позже была использована в [4] для построения устойчивого к утечкам CCA-шифрования. Однако, как мы видели, tSE является достаточным для построения как устойчивых к утечкам подписей, так и устойчивых к утечкам CCA-безопасных алгоритмов, таким образом, более строгое понятие aSE не требуется. Кроме того, учитывая текущее состояние эффективных алгоритмов шифрования и NIZK, разница в эффективности между ss-NIZK и стандартной NIZK значительно больше разницы между CCA и CPA-безопасного алгоритма шифрования, поэтому tSE превосходит как в простоте, так и в эффективности.

Отметим, что наша конструкция tSE NIZK (на основе CCA-шифрования и стандартного NIZK) неявно используется [15] для построения подписей элементов группы, и [45] для построения эффективного CCA-шифрования с сообщением, зависящего от ключа (KDM) из KDM-безопасного CPA-шифрования. Тем не менее, абстракция tSE не была четко определена в предыдущих работах, несмотря на кажущуюся полезность.


Реализации

Предположения

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

DDH. Пусть - группа простого порядка . Пусть и . DDH утверждает, что следующие два распределения являются вычислительно неотличимыми: и .

Пусть - группы простого порядка и пусть  : невырожденное эффективно вычислимое биективное отображение.


SXDH [46] [47] [48] [49] [50] . SXDH состоит в том, что проблема DDH сложна в обеих группах и . Предположение явно недействительно для симметричных пар (когда = )), но считается, что оно сохраняется, когда нет эффективно вычислимого отображения между и .

K-линейное [51] [52] и DLIN [47].

Пусть – группа простого порядка и пусть есть константа. Пусть и . K-линейное предположение гласит, что следующие два распределения вычислимо неотличимы: , и , с . Отметим, что для , К-линейность есть то же самое, что и DDH, и это не сохраняется при работе с симметричными парами. В этих условиях, 2-линейное предположение обычно сохраняется, и часто упоминается как DLIN. В этой статье мы предполагаем, что K-линейное предположение выполняется в обеих группах и ,в случае, когда работа идет с симметричными парами, и немного неправильно употребляется при , и SXDH сохраняется в этом случае.


Наши реализации

Мы покажем эффективные реализации устойчивых к утечкам подписей и CCA-безопасного шифрования, описанные в Разделе 4. Для каждого из алгоритмов, мы дадим две реализации на основе билинейных отображений: одну с безопасностью по SXDH предположению, и вторую, безопасную по DLIN предположению. Первая может быть использована с асимметричными парами, в то время как вторая относится к случаю симметричных пар. Мы дадим подробную информацию обо всех реализациях в полной версии [18] , но дадим высокоуровневое представление ниже.

Подписи

Напомним, что для создания экземпляра алгоритма подписи из Раздела 4, нам нужно устойчивое к утечкам строгое отношение (которое мы выведем из SPR отношения), и tSE NIZK аргумент, который мы построим из CCA-безопасного шифрования и стандартного NIZK аргумента для отношения . Мы покажем наш выбор экземпляров для следующих компонентов:

  • CCA-безопасное шифрование: При каждом из утверждений SXDH и DLIN мы используем эффективный алгоритм шифрования в стиле Крамера-Шупа [53][52].
  • NIZK аргумент: Мы используем ситему доказательств Грот-Сахаи [14] , которая может быть создана как для SXDH, так и для DLIN.
  • SPR отношение: Предыдущие реализации устойчивых к утечкам примитивов использовали SPR функцию . Однако, эта функция имеет недостаток в том, что свидетель находится в показателе. Это означет, что мы не можем комбинировать его с алгоритмом шифрования для элементов в (если каждый свидетель фиксируется побитово и, среди прочего, результаты доказательств растут линейно с параметром безопасности), и, к сожалению, алгоритмы шифрования для сообщений в не могут быть объединены с системой Грот-Сахаи. Поэтому мы строим два новых SPR отношения, основанные на попарных отождествлениях. Для нашей реализации SXDH мы используем отношение , где есть генератор . . Мы докажем, что это отношение является SPD при SXDH предположении. В случае DLIN, мы используем: , где есть генератор . Мы докажем, что это отношение является SPR при DLIN предположении. Для достижения уровня утечки , положим, что (количество компонент свидетелей) в SPR отношении будет обратно пропорционально к .


TemplateTheoremIcon.svg Теорема Теорема 5
Пусть , есть группы простого порядка . Для всех , существует -устойчивый к утечкам алгоритм, при SXDH предположении, использующий подписи, состоящие из элементов группы и элементов в . Аналогично, для всех , существует -устойчивый к утечкам алгоритм, при DLIN предположении, использующий подписи, состоящие из элементов группы и элементов в .
Доказательство
Без доказательства


CCA-безопасное шифрование

Напомним, что для устойчивого к утечкам шифрования на необходим CPA-безопасный устойчивый к утечкам алгоритм шифрования, стандартный CCA-безопасное шифрование и строгое tSE NIZK, которое мы можем получить комбинацией регулярного tSE NIZK с строгой одноразовой подписью. Мы построим регулярный tSE NIZK из CCA-безопасного шифрования и регулярного NIZK. Мы опишем наш выбор для каждого из них ниже.

  • LR-CPA-безопасное шифрование: Мы построим новый устойчивый к утечкам CPA-безопасный алгоритм шифрования для наших целей в стиле Эль-Гамеля (по аналогии с используемым в [2] [45] но сделаем его более эффективным). Утечка, которую наше новое CCA-безопасное шифрование переносит точно такая же, как и в случае с CPA-безопасным шифрованием. Неформально, мы достигаем коэффициента утечки в CPA-безопасном алгоритме шифрования при увеличении количества генераторов, используемых в публичном ключе и шифртексте. Это число обратно пропорционально .
  • CCA-Безопасное шифрование: При каждом из утверждений SXDH и DLIN мы используем эффективный алгоритм шифрования в стиле Крамера-Шупа [53][52].
  • NIZK Аргумент: Мы используем систему доказательств Грот-Сахаи [14] , которая может быть создана как для SXDH, так и для DLIN.
  • Одноразовая подпись: Заметим, может быть использована что любая строгая одноразовая подпись безопасна при этих предположениях. Здесь мы выбираем алгоритм [15] , в предположении дискретного логарифмирования (подразумеваемую как в SDXH, так и в DLIN), поскольку размер подписи мал, а именно элемента в .


TemplateTheoremIcon.svg Теорема Теорема 6
Пусть , есть группы простого порядка . Для всех , существует -устойчивый к утечкам алгоритм, при SXDH предположении, использующий шифртексты, состоящие из элементов группы и элементов в . Аналогично, для всех , существует -устойчивый к утечкам алгоритм, при SXDH предположении, использующий шифртексты, состоящие из элементов группы и элементов в .
Доказательство
Без доказательства


Другие применения

Как только мы получили эффективный устойчивый к утечкам алгоритм, мы видим, что стандартный ID алгоритм, основанный на подписях, где проверяющий запрашивает подпись случайного сообщения , легко расширяется с параметрами утечки. Более того, получившийся ID алгоритм наследует свою относительную утечку из соответствующего алгоритма подписи, и удовлетворяет строгому понятию “anytime-leakage” [3], где утечка может произойти даже при атаке заимствовании прав. Хотя наш метод довольно прост, отметим, что другие два популярных метода построения ID алгоритма — использование -протоколов для строгих отношений, анализируемое в [3] (см. первые две строки в Таблице 3), и использование CCA-безопасного шифрования (где проверяющий расшифровывает случайный шифртекст) — по своей сути не позволяют нам получить оптимальные результаты, даже при реализации с устойчивым к утечкам строгого отношения или CCA-безопасного алгоритмов.

Наконец, мы получили два эффективных устойчивых к утечкам AKA протоколов. Во-первых, аналогично со случаем с ID алгоритмами, мы можем получить устойчивый к утечкам АКА алгоритм из устойчивой к утечкам алгоритма подписи, как формально показано в [3]. Идея состоит в основе подписи стандартного DH-основанного протокола, но с устойчивым к утечкам алгоритмом подписи. Отметим, однако, что получившийся протокол не отрицаемый. А именно, расшифровка протокола оставляет неопровержимые доказательства, что протокол имеет место. Руководствуясь этим недостатком, мы разрабатываем другой общий AKA протокол на основе CCA-безопасного шифрования. Подробности даны в полной версии [18], однако, интуитивно, стороны шифрования потоков стандартного DH-основанного протокола, эффективно доказывающий их идентичность успешной повторной шифровки соответствующих потоков. Хотя мы не формализируем это, этот протокол отрицаемый, поскольку расшифровка протокола может быть смоделирована без знания частей секретных ключей. Насколько нам известно, этот протокол не был предложен и анализирован даже в условиях отсутствия утечки. Здесь мы на самом деле показали, что наши (новые) отрицаемые АКА протоколы работают даже в условиях утечки.


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

Мы хотели бы поблагодарить Виктора Шупа за полезные дискуссии, а также анонимных рецензентов за их полезные предположения.


Авторы

  1. New York University, E-mail: dodis@cs.nyu.edu
  2. New York University, E-mail: kkh@cs.nyu.edu
  3. New York University, E-mail: lopez@cs.nyu.edu
  4. New York University, E-mail: wichs@cs.nyu.edu


Ссылки

  1. 1,0 1,1 1,2 1,3 A. Akavia, S. Goldwasser, and V. Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In O. Reingold, editor, TCC, volume 5444 of LNCS, pages 474–495. Springer, 2009.
  2. 2,00 2,01 2,02 2,03 2,04 2,05 2,06 2,07 2,08 2,09 2,10 2,11 M. Naor and G. Segev. Public-key cryptosystems resilient to key leakage. In Halevi, pages 18–35.
  3. 3,00 3,01 3,02 3,03 3,04 3,05 3,06 3,07 3,08 3,09 3,10 3,11 3,12 3,13 3,14 J. Alwen, Y. Dodis, and D. Wichs. Leakage-resilient public-key cryptography in the bounded-retrieval model. In Halevi, pages 36–54.
  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 J. Katz and V. Vaikuntanathan. Signature schemes with bounded leakage resilience. In M. Matsui, editor, ASIACRYPT, volume 5912 of LNCS, pages 703–720. Springer, 2009.
  5. P. C. Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In N. Koblitz, editor, CRYPTO, volume 1109 of LNCS, pages 104–113. Springer,1996.
  6. D. Boneh, R. A. DeMillo, and R. J. Lipton. On the importance of checking cryptographic protocols for faults (extended abstract). In W. Fumy, editor, EUROCRYPT, volume 1233 of LNCS, pages 37–51. Springer, 1997.
  7. E. Biham and A. Shamir. Differential fault analysis of secret key cryptosystems. In B. S. K. Jr., editor, CRYPTO, volume 1294 of LNCS, pages 513–525. Springer, 1997.
  8. P. C. Kocher, J. Jaffe, and B. Jun. Differential power analysis. In M. J. Wiener, editor, CRYPTO, volume 1666 of LNCS, pages 388–397. Springer, 1999.
  9. J.-J. Quisquater and D. Samyde. Electromagnetic analysis (ema): Measures and countermeasures for smart cards. In I. Attali and T. P. Jensen, editors, E-smart, volume 2140 ofLNCS, pages 200–210. Springer, 2001.
  10. K. Gandolfi, C. Mourtel, and F. Olivier. Electromagnetic analysis: Concrete results. In C¸ etin Kaya Koc¸, D. Naccache, and C. Paar, editors, CHES, volume 2162 of LNCS, pages 251–261. Springer, 2001.
  11. 11,0 11,1 J. A. Halderman, S. D. Schoen, N. Heninger, W. Clarkson, W. Paul, J. A. Calandrino, A. J. Feldman, J. Appelbaum, and E. W. Felten. Lest we remember: cold-boot attacks on encryption keys. Commun. ACM, 52(5):91–98, 2009.
  12. 12,0 12,1 12,2 12,3 J. Alwen, Y. Dodis, M. Naor, G. Segev, S. Walfish, and D. Wichs. Public-key encryption in the bounded-retrieval model. In Gilbert, pages 113–134.
  13. 13,0 13,1 13,2 A. Sahai. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In FOCS, pages 543–553, 1999.
  14. 14,0 14,1 14,2 14,3 J. Groth and A. Sahai. Efficient non-interactive proof systems for bilinear groups. In N. P. Smart, editor, EUROCRYPT, volume 4965 of LNCS, pages 415–432. Springer, 2008.
  15. 15,0 15,1 15,2 15,3 15,4 15,5 J. Groth. Simulation-sound nizk proofs for a practical language and constant size group signatures. In X. Lai and K. Chen, editors, ASIACRYPT, volume 4284 of LNCS, pages 444–459. Springer, 2006.
  16. 16,0 16,1 M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In STOC, pages 427–437. ACM, 1990.
  17. 17,0 17,1 C. Rackoff and D. R. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In J. Feigenbaum, editor, CRYPTO, volume 576 of LNCS, pages 433–444. Springer, 1991.
  18. 18,0 18,1 18,2 18,3 Y. Dodis, K. Haralambiev, A. Lopez-Alt, and D. Wichs. Efficient public-key cryptography in the presence of key leakage. Cryptology ePrint Archive, Report 2010/154, 2010.
  19. R. Cramer and V. Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In L. R. Knudsen, editor, EUROCRYPT, volume 2332 of LNCS, pages 45–64. Springer, 2002.
  20. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In A. M. Odlyzko, editor, CRYPTO, volume 263 of LNCS, pages 186–194. Springer, 1986.
  21. S. Goldwasser and Y. T. Kalai. On the (in)security of the fiat-shamir paradigm. In FOCS, pages 102–.
  22. R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz, and A. Sahai. Exposure-resilient functions and all-or-nothing transforms. In B. Preneel, editor, EUROCRYPT, volume 1807 of LNCS, pages 453–469. Springer, 2000.
  23. Y. Dodis, A. Sahai, and A. Smith. On perfect and adaptive security in exposure-resilient cryptography. In Pfitzmann, pages 301–324.
  24. J. Kamp and D. Zuckerman. Deterministic extractors for bit-fixing sources and exposureresilient cryptography. In FOCS, pages 92–101.
  25. Y. Ishai, A. Sahai, and D. Wagner. Private circuits: Securing hardware against probing attacks. In D. Boneh, editor, CRYPTO, volume 2729 of LNCS, pages 463–481. Springer, 2003.
  26. S. Faust, T. Rabin, L. Reyzin, E. Tromer, and V. Vaikuntanathan. Protecting circuits from leakage: the computationally-bounded and noisy cases. In Gilbert, pages 135–156.
  27. S. Micali and L. Reyzin. Physically observable cryptography (extended abstract). In M. Naor, editor, TCC, volume 2951 of LNCS, pages 278–296. Springer, 2004.
  28. S. Dziembowski and K. Pietrzak. Leakage-resilient cryptography. In FOCS, pages 293–302. IEEE Computer Society, 2008.
  29. 29,0 29,1 K. Pietrzak. A leakage-resilient mode of operation. In Joux, pages 462–482.
  30. S. Faust, E. Kiltz, K. Pietrzak, and G. N. Rothblum. Leakage-resilient signatures. In Micciancio, pages 343–360.
  31. A. Juma and Y. Vahlis. Protecting cryptographic keys against continual leakage. In T. Rabin, editor, CRYPTO, volume 6223 of LNCS, pages 41–58. Springer, 2010
  32. G. D. Crescenzo, R. J. Lipton, and S. Walfish. Perfectly secure password protocols in the bounded retrieval model. In Halevi and Rabin, pages 225–244.
  33. S. Dziembowski. Intrusion-resilience via the bounded-storage model. In Halevi and Rabin, pages 207–224.
  34. 34,0 34,1 Y. Dodis, Y. T. Kalai, and S. Lovett. On cryptography with auxiliary input. In M. Mitzenmacher, editor, STOC, pages 621–630. ACM, 2009.
  35. 35,0 35,1 Y. Dodis, S. Goldwasser, Y. T. Kalai, C. Peikert, and V. Vaikuntanathan. Public-key encryption schemes with auxiliary inputs. In Micciancio, pages 361–381.
  36. S. Goldwasser, Y. Kalai, C. Peikert, and V. Vaikuntanathan. Robustness of the learning with errors assumption. In Innovations in Computer Science (ICS), 2010.
  37. M. Blum, P. Feldman, and S. Micali. Non-interactive zero-knowledge and its applications (extended abstract). In STOC, pages 103–112. ACM, 1988.
  38. A. D. Santis, G. D. Crescenzo, R. Ostrovsky, G. Persiano, and A. Sahai. Robust noninteractive zero knowledge. In J. Kilian, editor, CRYPTO, volume 2139 of LNCS, pages 566–598. Springer, 2001.
  39. A. D. Santis and G. Persiano. Zero-knowledge proofs of knowledge without interaction (extended abstract). In FOCS, pages 427–436. IEEE, 1992.
  40. R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In STOC, pages 494–503, 2002.
  41. R. Pass and A. Rosen. Concurrent non-malleable commitments. In FOCS, pages 563–572. IEEE Computer Society, 2005.
  42. R. Pass and A. Rosen. New and improved constructions of non-malleable cryptographic protocols. In H. N. Gabow and R. Fagin, editors, STOC, pages 533–542. ACM, 2005.
  43. J. Alwen, Y. Dodis, and D. Wichs. Survey: Leakage resilience and the bounded retrieval model. In ICITS, 2009.
  44. Y. Lindell. A simpler construction of cca2-secure public-keyencryption under general assumptions. J. Cryptology, 19(3):359–377, 2006.
  45. 45,0 45,1 J. Camenisch, N. Chandran, and V. Shoup. A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In Joux, pages 351–368.
  46. M. Scott. Authenticated id-based key exchange and remote log-in with simple token and pin number. Cryptology ePrint Archive, Report 2002/164, 2002.
  47. 47,0 47,1 D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In M. K. Franklin, editor, CRYPTO, volume 3152 of LNCS, pages 41–55. Springer, 2004.
  48. L. Ballard, M. Green, B. de Medeiros, and F. Monrose. Correlation-resistant storage via keyword-searchable encryption. Cryptology ePrint Archive, Report 2005/417, 2005.
  49. S. D. Galbraith and V. Rotger. Easy decision-diffie-hellman groups. LMS Journal of Computation and Mathematics, 7:2004, 2004.
  50. E. R. Verheul. Evidence that xtr is more secure than supersingular elliptic curve cryptosystems. J. Cryptology, 17(4):277–296, 2004.
  51. D. Hofheinz and E. Kiltz. Secure hybrid encryption from weakened key encapsulation. In A. Menezes, editor, CRYPTO, volume 4622 of LNCS, pages 553–571. Springer, 2007.
  52. 52,0 52,1 52,2 H. Shacham. A cramer-shoup encryption scheme from the linear assumption and from progressively weaker linear variants. Cryptology ePrint Archive, Report 2007/074, 2007.
  53. 53,0 53,1 R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In H. Krawczyk, editor, CRYPTO, volume 1462 of LNCS, pages 13–25. Springer, 1998.