Криптография и память, подверженная искажениям и утечкам

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:54, 17 декабря 2015.
Криптография с утечкой памяти и памятью, подверженной вмешательству
Leaky Tamper.jpg
Авторы Yael Tauman Kalai[@: 1]

and
Bhavana Kanukurthi[@: 2] and
Amit Sahai[@: 3]

Опубликован 2011 г.
Сайт Department of Computer Science
Перевели Potapov Yaroslav
Год перевода 2015 г.
Скачать оригинал
Аннотация. Большой и растущий объем исследований стремится обеспечить безопасность криптографических систем на фоне физических атак. Руководствуясь большим разнообразием реальных физических атак на память, важное направление работы было инициировано Akavia, Goldwaser и Vaikuntanathan[1], где безопасность искали в предположении, что: вся память допускает утечку информации, и утечка может быть в произвольно выбранной функции памяти.
Однако, физические атаки на память не ограничены ее утечкой через сторонние каналы, но также могут включать поддельные атаки через множество физических атак, таких как тепловое воздействие и электромагнитное излучение. Тем не менее, защита от аналогичной модели вмешательства в память - где вся память уязвима к вмешательству, и где вмешательство может быть произвольно выбрано (эффективно) функцией, применяемой к памяти - осталось недостижимой целью, не смотря на значительные усилия в решении вопросов, связанных с вмешательством. В этой работе мы занимаемся этим вопросом, рассматривая модель, где мы предполагаем, что обе из этих пар заявлений верны – что вся память подвержена и утечки и (произвольному) вмешательству. Кроме того, мы предполагаем, что эти утечки и вмешательства могут происходить неоднократно и все время (расширяющий модель [2] [3] в контексте утечки). Мы строим схему подписи и схему шифрования, которые доказуемо безопасны против таких нападениях, предполагая, что память может быть рандомно обновлена между эпизодами вмешательства и утечки. В обеих схемах мы полагаемся на линейное предположение по билинеарным группам.
Мы также отдельно рассматриваем модель, в которой возможно только непрерывные и повторные вмешательства (но только ограниченная утечка), и мы в состоянии получить положительные результаты, предполагающие только то, что “самоликвидация” возможна, без необходимости в обновлениях памяти.
Наши результаты также улучшают предыдущие результаты в непрерывном режиме утечки без вмешательств [2] [3]. Принимая во внимание, что предыдущие схемы, безопасные против непрерывной утечки (произвольных ограниченных функций секретного ключа), могли терпеть только уровень утечки между ключевыми обновлениями под линейным предположением по билинеарным группам, наши схемы могут терпеть уровень утечки между ключевыми обновлениями под тем же самым предположением.

Введение

Большой и растущий объем исследований стремится обеспечить безопасность криптографических систем на фоне физических атак(к примеру [4] [5][6] [7][8] [9][10] [1][11] [12][13] [14][15] [16][17]. Руководствуясь большим разнообразием реальных физических атак на память[18][19][20][21][22], важное направление работы было инициировано Akavia, Goldwaser и Vaikuntanathan[1], где безопасность искали в предположении, что: вся память допускает утечку информации, и утечка может быть в произвольно выбранной функции памяти.

Однако, физические атаки на память не ограничены ее утечкой через сторонние каналы, но также могут включать поддельные атаки через множество физических атак, таких как тепловое воздействие и электромагнитное излучение[23][24][25]. Тем не менее, защита от аналогичной модели вмешательства в память - где вся память уязвима к вмешательству, и где вмешательство может быть произвольно выбрано (эффективно) функцией, применяемой к памяти - осталось недостижимой целью, не смотря на значительные усилия в решении вопросов, связанных с вмешательством(к примеру [26][7][8][27][28]. В этой работе мы занимаемся этим вопросом, рассматривая модель, где мы предполагаем, что обе из этих пар заявлений верны – что вся память подвержена и утечки и (произвольному) вмешательству. Кроме того, мы предполагаем, что эти утечки и вмешательства могут происходить неоднократно и все время (расширяющий модель [2] [3] в контексте утечки). Мы показываем сильные положительные результаты для шифровальных задач, включая подписи и декодирование, предполагая, что память может быть обновлена рандомизированным способом между эпизодами вмешательства и утечки. Мы отмечаем, что рассматриваем только вмешательство в память и не рассматриваем вопроса вмешательства во время вычисления (который мог бы произойти, например, в следствии неудачных атак [29][30][21]).

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

Фон. Прежде, чем объяснить наши результаты более подробно, давайте сначала вспомним результаты [2] [3], который мы усиливаем. Эти результаты строят различные шифровальные схемы (такие как шифрование и схемы подписи), которые остаются безопасными, даже если секретный ключ все время подвержен утечке. В этой непрерывной модели утечки каждый период злоумышленник может сделать запрос утечки , где - полиразмерное кольцо, и получить в ответ . Понятно, что для того, чтобы получить безопасность при непрерывной утечке, каждый должен связать функцию утечки в некотором роде, с тех пор если, например, - функция идентичности, безопасность ясно нарушена. Обе работы [2] [3] позволяют быть любой функцией утечки сокращения; например, любой , такой что, что . В более общем смысле, они представляют любую функцию утечки таким образом, что sk имеет “достаточную” минимальную энтропию, обусловленную на . Мы отмечаем, что несколько более ранних непрерывных моделей утечки были рассмотрены в литературе, к примеру, Micali и Reyzin[6], которые рассматривают только предположение информации об утечках вычисления, или Ishai, Sahai и Wagner[5], кто считают только утечку отдельных битов, произшедшей во время честного вычисления. Мы уточняем эти связанные работы, а также других, указанных в Разделе 1.3.

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

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

Наша CTL модель

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

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

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

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

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

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

В дальнейшем мы представляем неофициальные заявления наших результатов.

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


TemplateTheoremIcon.svg Теорема Теорема 2
Под линейным предположением в главной группе G заказа, существует схема подписи, которая является экзистенциально нековкой при адаптивных выбранных сообщениях атаки в модели CTL, терпя утечку в каждом периоде времени.
Доказательство
Доказательство теоремы приведено в полной версии


TemplateTheoremIcon.svg Теорема Теорема 3
Учитывая схему подписи, которая является экзистенциально нековкой в ограниченной модели утечки, существует эффективное преобразование в схему подписи, которая является экзистенциально нековкой в непрерывном вмешательстве и ограниченной модели утечки.
Доказательство
Доказательство теоремы приведено в полной версии


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

Работа над признанием утечки была начата Rivest и Boyko [31] [32] в контексте увеличения затрат на brute-force атаки на блочные шифры и проблемы эффективности. Идеи там были применены к контексту утечки многочисленными работами над эластичным воздействием криптографией [4] [33][5]. Эти работы рассматривают простые функции утечки, которые показывают подмножество частей секретного ключа или внутренней памяти о шифровальном устройстве. Эта линия исследования достигла высшей точки в работе Ishai, Sahai и Wagner[5], которая показывает, как “собрать” любой шифровальный алгоритм в тот, который терпит такие типы утечки.

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

Ограниченные Модели Утечки. Это направление работы рассматривает модель утечки, которая позволяет злоумышленнику получать продукцию применения любой эффективно вычислимой функции , его выбора, для секретного ключа . Это допускается, пока выход не показывает весь секретный ключ. Это последнее условие было формализовано многими различными способами, начинающимися с работы Akavia, Goldwasser и Vaikuntanathan[1] , где они ограничивают функцию утечки , чтобы получить длину и впоследствии представлено в работах Naor и Segev[11]и Dodis, Калай и Ловетт [13]. Строительство криптосистем, удовлетворяющих одно или более этих определений, может быть найдено в различных работах (например [1] [11] [13] [12] [14]).

Непрерывные Модели Утечки. Эта направление работы рассматривает случай, где утечка непрерывна, т.е. ограниченная сумма информации о секретном ключе утекает в каждом периоде времени, но полная утечка во всем жизненном цикле секретного ключа неограниченна. Легко видеть, что, чтобы гарантировать любую безопасность в этой модели, секретный ключ должен обязательно быть обновлен между периодами времени. Micali и Reyzin [6] предложили изучить безопасность против непрерывной утечки под предположением, что только вычисление пропускает информацию. Другими словами, утечка информации может произойти в любое время, вычисление имеет место; однако, предположение заключается в том, что части памяти, которые не вовлечены в вычисление во время определенного периода времени, не подвергаются утечке во время того периода времени. Много работ (например [17][9][10][34][16]) проектируют шифровальные схемы, которые эластичны к утечке под этим предположением.

Совсем недавно, Dodis, Haralambiev, Lopez-Alt и Wichs[2] и Brakerski, Kalai, Katz и Vaikuntanathan [3]построили шифровальные схемы (такие как схемы подписи и схемы шифрования) в непрерывной модели утечки без предположения, что только вычисление подвержено. Наш основной результат полагается на результат Brakerski и др.

Модели вмешательств. Несколько моделей безопасности против вмешательства рассмотрели в прошлом, однако, все они отличаются существенно от нашего. Понятие алгоритмической защищенной безопасности от несанкционированного использования было предложено Gennaro, Lysyanskaya, Malkin, Micali и Rabin [7], в котором у устройств есть обе защищенной от несанкционированного использования, но полностью утекаемой памяти (которая может быть запрограммирована с ключевой информацией, уникально настроенной каждому пользователю), наряду с памятью, подверженной вмешательству, которая может все время вмешиваться с использованием произвольных многочленно-разовых функций вмешательства. (Напротив, наша модель позволяет всей памяти произвольно вмешиваться) Безопасность против связано-ключевых нападений была формализована Bellare и Kohno [27] в контексте безопасности блочного шифра, но может быть замечена как касающийся модели, где в ключ можно вмешаться. Однако это напрвление работы (см. [26] и ссылки там) имеет дело с ограниченными видами функций вмешательства, таких как функции XOR ключ с постоянным значением или аффинными линейными преобразованиями. Недавняя работа над негибкими кодами [28] выглядит также как ограничивающиеся вмешивающиеся функции. (Напротив, наша модель позволяет произвольные многочленно-разовые функции вмешательства.) Наконец, работа Ishai, Prabhakaran, Sahai и Wagner [8] рассматривает еще более слабые функции вмешательства, которые только позволяют отдельным битам переключаться или устанавливать в определенную стоимость. Однако в отличие от нашей работы, Ishai и др. также позволяют вмешивание, чтобы затронуть вычисление, а не только память, которая выходит за рамки нашей работы.

Обзор

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

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

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

TemplateLemmaIcon.svg Лемма «Лемма 1»
Пусть случайное подпространство измерения , где . Пусть и . Тогда для любой функции утечки , выбранной из , , при


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

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

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

Эта работа. В этой работе мы позволяем злоумышленнику и просачиваться и вмешиваться в секретный ключ. А именно, злоумышленник может изменить секретный ключ с на . Обратите внимание на то, что вышеупомянутая идея доказательства не может использоваться с вмешательством, так как процедура обновления обновляет (вмешавшийся) секретный ключ, возводя его в степень , т.е., обновляет на . Начиная с того, как функция вмешательства выбрана соперническим образом, мы не можем больше полагаться на предположение DDH, и таким образом не можем использовать Лемму 1. Действительно, мы не можем доказать, что схема [3] безопасна против вмешательства. Вместо этого мы немного изменяем их схемы.

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

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

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

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

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

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

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

Наша CTL модель

Наша CTL модель обобщает непрерывную модель утечки памяти [2] [3], чтобы позволить злоумышленнику (все время) вмешиваться в секретное состояние, а также (все время) использовать утечки. В дальнейшем мы определяем схему шифрования в модели CTL.

Схемы шифрования в модели CTL. Определение схемы шифрования в модели CTL очень подобно определениям, данным в [2] [3], за исключением следующего различия. В нашем определении мы делим алгоритм генерации ключа на две части. Первая часть - алгоритм генерации общедоступного параметра, обозначенный ppGen. Этот алгоритм берет в качестве входа параметр безопасности и производит общедоступный параметр .

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

Формально, схема шифрования в модели CTL состоит из пяти PPT алгоритмов:

  • Алгоритм ppGen генерации общедоступного параметра, который принимает на вход параметр безопасности , ина выходе получает общедоступный параметр . Мы обозначаим это .
  • Алгоритм Gen генерации ключа, который принимает на вход параметр безопасности и общедоступные параметры , и генерирует пару секретных и открытых ключей . Мы обозначаим это .
  • Шифрование. Берет в качестве входа общедоступные параметры , открытый ключ и сообщение из множества сообщений , и генерирует зашифрованный текст . Мы обозначим это .
  • Декодирование. Берет в качестве входа общедоступные параметры , секретный ключ и зашифрованный текст , и генерирует сообщение . Мы обозначаим это .
  • Ключевое обновление. Берет в качестве входа общедоступные параметры , секретный ключ , и генерирует обновленный секретный ключ , таким образом что . Мы обозначаим это .

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

Мы затем определяем семантическую безопасность в модели CTL. Мы используем определение из [3] и увеличиваем его, допуская вмешательство вопросов. Формально, утечка в этой модели связана с тремя параметрами утечки , где ограничивает темп утечки от процесса ключевого поколения, ограничивает темп утечки от процесса обновления, и - глобальная (относительная) утечка памяти, которая происходит между обновлениями ключей. Ради простоты мы определяем безопасность для особого случая, когда . Это упрощает определение и допускает более чистую толкование. Результат [3], может использоваться, чтобы показать, что любая схема, которая безопасна против непрерывной утечки, может терпеть утечек от каждого процесса обновления, и таким образом и наша схема может терпеть такую утечку.

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

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

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

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

– Вопросы вмешательства , где - схема. Претендент устанавливает .

– Вопросы утечки , где - схема. Если , тогда претендент возвращает подделывателю и устанавливает. Иначе, аварийное прекращение работы претендента.

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

4. Конец. Злоумышленник получает предположение .

Противник преуспевает, если .

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

Главная Лемма

Интуитивно, главная лемма заключается урегулирование, где случайный вектор выбран и все время обновляется добавлением к нему любого случайного элемента из маленького подпространства или случайный элемент из большего подпространства. Между каждыми двумя обновлениями в случайный вектор можно вмешаться, и воспользоваться частичной утечкой, много раз, пока общая сумма утечки ограничена. Утверждение состоит в том, что трудно различить случай, где обновления были от маленького подпространства, а где от большого подпространства, принимая на вход функции утечки эти векторы “в экспоненте”. Более определенно, мы считаем случайную матрицу , состоящую из строк, где . Случайный вектор обновлен или добавлением к нему случайного элемент из “в экспоненте”, или добавлением к нему случайного элемент в “в экспоненте”, где является случайным d-размерным подпространством . Первый называют идеальной игрой, последний называют реальной игрой. Утверждение состоит в том, что в вычислительном отношении трудно различить эти два вектора, даже при данном .

TemplateLemmaIcon.svg Лемма «Лемма 2»
Для любого безопасного параметра , пусть будет группой порядка , где - главный k-бит, такой, что линейное предположение содержится в . Пусть многочлены с параметрами , и пусть . Тогда для любого PPT злоумышленника

пока , удовлетворяет , где и определены ниже.

Эксперимент . В претендент взаимодействует с злоумышленником следующим образом:

1. выбирает случайную матрицу и случайный вектор . Он устанавливает и предоставляет в .

2. выбирает случайное d-размерное подпространство такой, что . Для :

(a) определяет вопрос утечки и функцию вмешательства .

(b) предоставляет в . Кроме того, он выбирает , устанавливает , и устанавливает .

3. Наконец, дает злоумышленнику подпространства , и дает на выходе или 0 или 1.

Таким образом, во время этого эксперимента становится

,

при и для


Эксперимент . Этот эксперимент то же самое, что и за исключением того, что . Ради ясности мы будем использовать примечание , чтобы обозначить обновления в идеальной игре (в противоположность в реальной игре). Таким образом, в идеальной игре устанавливает в Шаге 2b выше.

Таким образом, во время этого эксперимента становится

,

при и для .

Мы оставили доказательство Леммы 2 в полной версии.

Схемы шифрования в модели CTL

В этой секции, мы строим схему шифрования, которая безопасна в модели CTL. Наша схема шифрования определена в рисунке 1.

Схема шифрования

Генерация общедоступного параметра. Генерация общедоступного параметра алгоритмом ppGen, который принимает на входе параметр безопасности , и работает следующим образом:

  • Выбираются случайные и такие, что (т.е. оба столбца из случайно выбраны в ).

На выходе .

Генерация ключа. Алгоритм генерации ключа Gen принимает на входе параметр безопасности и публичный параметр , и выполняется следующее:

  • Выбирается случайный вектор (т.е. ).
  • Принимается и

На выходе пара (sk,pk) секретного и публичного ключа.

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

  • Если , выбирается случайный вектор , а на выходе
  • Если , выбирается случайный вектор и случайный элемент , а на выходе

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

  • Если , тогда на выходе будет . Иначе, на выходе .

Обновления. Процедура обновления Update принимает на вход публичные параметры и секретный ключ , он выбирает и на выходе выдает

Рис.1 Схема шифрования в модели CTL

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


Схемы подписи в модели CTL

В этом разделе мы покажем, как преобразовать любую схему шифрования, которая безопасна в модели CTL, в схему подписи, которая безопасна в модели CTL. Наше преобразование следует из парадигмы Katz-Vaikuntanathan [25] и использует следующие стандартные блоки:

  • Схема шифрования семантически безопасна в модели CTL с уровнем утечки . Мы предполагаем, что у схемы шифрования есть детерминированный предикат такой, что , если и только если - “допустимое” соответствие секретного ключа (т.е., если правильно дешифрует шифрованные тексты, зашифрованные с использованием с большой вероятностью).
  • Адаптивная звуковая моделированная система доказательства NIZK (как определено Sahai [35]) для следующего языка :

  • Обычная семантическая безопасная схема шифрования (без утечки или вмешательств).

Наша схема подписи определена на рисунке 2, а результаты представлены в следующей теореме:

TemplateTheoremIcon.svg Теорема Теорема 5
Схема подписи , описанная на рисунке 2, экзистенциально неподделываемая под адаптивно выбранным сообщением при атаке на модель CTL, с уровнем утечки , где и . В частности при помощи схемы шифрования, описанной на рисунке 1, мы получаем схему подписи , которая является экзистенциально неподделываемой под адаптивно выбранным сообщением при атаке на модель CTL, с уровнем утечки
Доказательство
Доказательство теоремы приведено в полной версии


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

Схема подписи

Генерация общедоступного параметра. Генерация общедоступного параметра алгоритмом ppGen, который принимает на входе параметр безопасности , и работает следующим образом:

  • Выбирается .
  • Выбирается публичный ключ для обычной схемы шифрования .
  • Выбирается случайная строка

На выходе как публичные параметры.

Генерация ключа. Алгоритм генерации ключа Gen принимает на входе параметр безопасности и публичные параметры , генерирует. На выходе пара (sk,pk) секретного и ключа проверки.

Подписание. С полученными сообщением , публичными параметрами и секретным ключом выполняется следующее:

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

А именно, вычисляем

На выходе как подпись для .

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

Обновления. Процедура обновления Update идентична . В частности она берет принимает на вход публичные параметры и секретный ключ и обновление секретный ключ, вычисляя

Рис.2 Схема подписи в модели CTL

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

- схема подписи защищает в ρ-ограниченной модели утечки, т.е. экзистенциально неподделываемая, даже если злоумышленник получает утечку его выбора, таким образом, что . Мы предполагаем, что у есть свойство, что , и что существует PPT алгоритм pkGen такой, что (который удовлетворен [1]).

- Генератор псевдо-рандомных чисел

- Единственная теорема адаптивного “короткого” модуляционного звука (SS) NIZK POK для языка , где длина доказательства - полиномиальна в длине свидетеля.

TemplateTheoremIcon.svg Теорема Теорема 6
Схема подписи , представленная на рисунке 3 экзистенциально неподделываемая в непрерывном вмешательстве и -ограниченной модели утечки, где
Доказательство
Доказательство теоремы приведено в полной версии


Схема подписи

Генерация общедоступного параметра. Генерация общедоступного параметра алгоритмом ppGen, который принимает на входе параметр безопасности , и работает следующим образом:

  • Выбирается строка

На выходе .

Генерация ключа. Алгоритм генерации ключа Gen' принимает на входе параметр безопасности и публичный параметр , и выполняется следующее:

  • Выбирается
  • Устанавливается и выбирается .
  • Вычисляется короткое SS NIZK POK для , w.r.t. crs, где

А именно, .

  • Устанавливается

На выходе пара , состоящая из секретного ключа и ключа проверки.

Подписание. С полученным сообщением , публичными параметрами и секретным ключом выполняем следующее:

  • Проверяем является ли действительным для по отношению к обычной случайной строке . А именно, проверяется .Если нет, то самоуничтожается.
  • Вычисляется (где Sign оригинальная утечка эластичного алгоритма подписания).

На выходе как подпись для .


Проверка. Для проверки подписи сообщения w.r.t. ключ проверки , запускает и выводит, независимо от того, что получилось.

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

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

  1. Microsoft Research
  2. Boston University
  3. University of California(UCLA)

Литература

  1. 1,0 1,1 1,2 1,3 1,4 1,5 1,6 Adi Akavia, Shafi Goldwasser, and Vinod Vaikuntanathan. Simultaneous hardcore bits and cryptography against memory attacks. In TCC, pages 474–495, 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 2,12 2,13 2,14 Yevgeniy Dodis, Kristiyan Haralambiev, Adriana Lopez-Alt, and Daniel Wichs.Cryptography against continuous memory attacks. In FOCS, 2010.
  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 3,15 3,16 3,17 3,18 3,19 3,20 Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, and Vinod Vaikuntanathan. Overcoming the hole in the bucket: Public-key cryptography resilient to continual memory leakage. In FOCS, pages 335–359, 2010.
  4. 4,0 4,1 Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, and Amit Sahai. Exposure-resilient functions and all-or-nothing transforms. In EUROCRYPT, pages 453–469, 2000.
  5. 5,0 5,1 5,2 5,3 Yuval Ishai, Amit Sahai, and David Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO, pages 463–481, 2003.
  6. 6,0 6,1 6,2 6,3 Silvio Micali and Leonid Reyzin. Physically observable cryptography (extended abstract). In TCC, pages 278–296, 2004.
  7. 7,0 7,1 7,2 Rosario Gennaro, Anna Lysyanskaya, Tal Malkin, Silvio Micali, and Tal Rabin. Algorithmic tamper-proof (atp) security: Theoretical foundations for security against hardware tampering. In TCC, pages 258–277, 2004.
  8. 8,0 8,1 8,2 Yuval Ishai, Manoj Prabhakaran, Amit Sahai, and David Wagner. Private circuits ii: Keeping secrets in tamperable circuits. In EUROCRYPT, pages 308–327, 2006.
  9. 9,0 9,1 Stefan Dziembowski and Krzysztof Pietrzak. Leakage-resilient cryptography. In FOCS, pages 293–302, 2008.
  10. 10,0 10,1 Krzysztof Pietrzak. A leakage-resilient mode of operation. In EUROCRYPT, pages 462–482, 2009.
  11. 11,0 11,1 11,2 Moni Naor and Gil Segev. Public-key cryptosystems resilient to key leakage. In CRYPTO, pages 18–35, 2009.
  12. 12,0 12,1 Jonathan Katz and Vinod Vaikuntanathan. Signature schemes with bounded leakage resilience. In ASIACRYPT, pages 703–720, 2009.
  13. 13,0 13,1 13,2 Yevgeniy Dodis, Yael Tauman Kalai, and Shachar Lovett. On cryptography with auxiliary input. In STOC, pages 621–630, 2009.
  14. 14,0 14,1 Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert, and Vinod Vaikuntanathan. Public-key encryption schemes with auxiliary inputs. In TCC, pages 361–381, 2010.
  15. Sebastian Faust, Eike Kiltz, Krzysztof Pietrzak, and Guy N. Rothblum. Leakageresilient signatures. In TCC, pages 343–360, 2010.
  16. 16,0 16,1 Ali Juma and Yevgeniy Vahlis. Protecting cryptographic keys against continual leakage. In CRYPTO, pages 41–58, 2010.
  17. 17,0 17,1 Shafi Goldwasser and Guy Rothblum. How to play mental solitaire under continuous side-channels: A completeness theorem using secure hardware. Manuscript,2010.
  18. J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, and Edward W.Felten. Lest we remember: Cold boot attacks on encryption keys. In USENIX Security Symposium, pages 45–60, 2008.
  19. 19,0 19,1 Sudhakar Govindavajhala and Andrew W. Appel. Using memory errors to attack a virtual machine. In IEEE Symposium on Security and Privacy, pages 154–165, 2003.
  20. Paul C. Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In CRYPTO, pages 104–113, 1996
  21. 21,0 21,1 Paul C. Kocher, Joshua Jaffe, and Benjamin Jun. Differential power analysis. In CRYPTO, pages 388–397, 1999.
  22. Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks and countermeasures: The case of aes. In CT-RSA, pages 1–20, 2006.
  23. Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic analysis: Concrete results. In CHES, number Generators, pages 251–261, 2001.
  24. Josyula R. Rao and Pankaj Rohatgi. Empowering side-channel attacks. Cryptology ePrint Archive, Report 2001/037, 2001. http://eprint.iacr.org/.
  25. Jean-Jacques Quisquater and David Samyde. Electromagnetic analysis (ema):Measures and counter-measures for smart cards. In E-smart, pages 200–210, 2001
  26. 26,0 26,1 Benny Applebaum, Danny Harnik, and Yuval Ishai. Semantic security under related-key attacks and applications. Cryptology ePrint Archive, Report 2010/544, 2010. http://eprint.iacr.org/.
  27. 27,0 27,1 Mihir Bellare and Tadayoshi Kohno. A theoretical treatment of related-key attacks: Rka-prps, rka-prfs, and applications. In EUROCRYPT, pages 491–506, 2003.
  28. 28,0 28,1 Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs. Non-malleable codes. In ICS, pages 434–452, 2010.
  29. Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. On the importance of checking cryptographic protocols for faults. In EUROCRYPT, pages 37–51, 1997.
  30. Eli Biham and Adi Shamir. Differential fault analysis of secret key cryptosystems.In CRYPTO, 1997
  31. Ronald L. Rivest. All-or-nothing encryption and the package transform. In FSE, pages 210–218, 1997.
  32. Victor Boyko. On the security properties of oaep as an all-or-nothing transform. In CRYPTO, pages 503–518, 1999.
  33. Yevgeniy Dodis, Amit Sahai, and Adam Smith. On perfect and adaptive security in exposure-resilient cryptography. In EUROCRYPT, pages 301–324, 2001.
  34. Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, and Vinod Vaikuntanathan. Protecting against leakage: the computationally bounded and noisy cases. In Eurocrypt, pages 135–156, 2010.