Эффективная Аутентификация на основе Трудно Обучаемых Проблем

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:48, 27 сентября 2015.
Efficient Authentication from Hard Learning Problems
Efficient Authentication from hard Learning Problems.PNG
Авторы Eike Kiltz,[@: 1],
Krzysztof Pietrzak,[@: 2],
David Cash,[@: 3]
Abhishek Jain,[@: 4]
and Daniele Venturi[@: 5]
Опубликован 2011 г.
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


Аннотация. Мы строим эффективные протоколы аутентификации и коды аутентификации сообщений (КАСы), чью надежность можно свести к проблеме обучения четности с шумом (LPN). Несмотря на большой объем работы - начиная с протокола Хоппера и Блума (ХБ) в 2001 - до настоящего момента оставалось неизвестным даже то, как из LPN построить эффективный протокол аутентификации, устойчивый к атакам типа человек посередине (MIM). КАС предполагает такой протокол (двухораундовый).

__NUMBEREDHEADINGS__

Введение

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

Стремлние к LPN-аутентификации обусловлено двумя несвязанными причинами, одной теоретической и одной практической. С теоретической стороны, проблема LPN предоставляет привлекательный базис для доказательной надежности [2] [3] [4] [5] [6] [7]. Она тесно связана с хорошо изученной проблемой расшифровки случайных линейных кодов и, в отличие от большинства числовых теоретических проблем, используемых в криптографии, проблема LPN не поддается известным квантовым алгоритмам. На практике же LPN-алгоритмы поразительно эффективны и требуют сравнительно мало операций с битами. В самом деле, в своих начальных тезисах Хоппер и Блум [6] предположили, что люди смогут выполнять вычисления по доказательно надежной схеме даже с реалистичными параметрами. Эффективность LPN-схем также делает их подходящими для слабых устройств, вроде RFID-тэгов, где оценка блочных шифров может быть запрещена.

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

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

Протоколы аутентификации Протокол аутентификации - это протокол(с разделяемым ключом), в котором проверяемый P аутентифицирует себя проверяющему V (в контексте RFID-применений считаем P "меткой", а V - "считывателем"). Вспомним несколько общих определений надежности против атак с перевоплощением. Пассивная атака происходит в 2 фазы, где в первой фазе злоумышленник следит за несколькими взаимодействиями P и V, а затем пытается заставить V принять его во второй фазе (когда P более не доступен). В активной атаке злоумышленник дополнительно может взаимодействовать с P в первой фазе. Сильнейшая и наиболее реалистичная модель атаки - "человек посередине" (MIM), когда злоумышленник может произвольно взаимодействовать с P и V ( с полиномиальным числом одновременно выполняемых операций) в первой фазе.

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

Более формально, для и вектора определим распределение на с помощью , где равномерно случайно и выбирается согласно , распределению Бернулли над с параметром . Проблема должна отличать оракула, возвращающего случайные модели из , где случайный и фиксированный, от оракула, возвращающего нормальные модели. Блум и др. показали [3], что это эквивалентно поисковой версии LPN, где требуется вычислить , предоставляя оракулу доступ к (см. [8] , Тема 2 для точных границ). Отметим, что поисковый и выборный варинаты разрешимы с линейностью моделей без шума, т.е. когда , и лучшие алгоритмы занимают время когда принимается за константу [9] [4] [10].

Протоколы аутентификации на основе LPN Начиная с работы Хоппера и Блума [6] было предложено несколько протколов аутентификации на основе проблемы LPN. Их первоначальный протокол изящный протокол достаточно прост, чтобы сразу его вспомнить. Разделяемый секретный ключ - это двоичный вектор . Зваимодействие состоит из двух сообщений. Сначала V отправляет случайный вызов , затем P отвечает битом , где выбирается согласно . Наконец, проверяющий признает ответчика, если .

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

Двухраундовый HB-протокол доказательно надежен при пассивных атаках, но известны эффективные активные атаки на него. Это неприемлемо, так как во многих случаях, особенно в RFID, злоумышленник может провести активную атаку. Впоследствии Джулс и Вейс [11] предложили эффективный 3-раундовый вариант HB, названный HB, и доказали его защищенность от активных атак. Ошибку можно снова уменьшить последовательными повторениями, и как показали Катз, Шин и Смит при помощи нетривиального анализа, параллельное повторение тоже работает [12] [13]. Протокол в варианте с параллельными повторениями проиллюстрирован на Рирс. 2.

Несмотря на большой объем дальнейшей работы [прим. 1], не были достигнуты улучшения ни в области сложности раундов, ни в надежности, ни в степени сокращения: 3-раундовые протоколы, достигающие активной надежности (при условии, что LPNсложна) являются вершиной творения. В частности, Гилберт и др. показали [14] , что HB может быть сломан атакой "человек посередине". Было представлено несколько варинатов протоколов, устойчивых к конкретной атаке[14] - HB [15], HB [16], HB-MP [17], - однако все они позже показали свою уязвимость [18] В другой работе [19] был представлен другой вариант, HB, который был доказательно защищен от этой[14] атаки, но впоследствие оказался уязвим для более общей версии атаки "человек посередине" [20].

EAHLP Fig1.PNG
Рис. 1 Протокол HB, защищенный от пассивных атак.
EAHLP Fig2.PNG
Рис. 2 Протокол HB, защищенный от активных атак.

Наш вклад

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

2-раундовая аутентификация с активной защитой

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

Теперь опишем наш протокол. В НВ и его двухраундовом варианте ответчик должен вычислить модель LPN из , где R - запрос,выбранный проверяющим в первом сообщении. Мы используем другой подход. Вместо отправки R мы позволяем проверяющему выбрать случайное подмножество бит из s для использования в качестве сеансового ключа. Это подмножество получается отправкой вектора , выступающего в роли битового селектора секрета s, и мы запишем как подвектор s, полученный путем удаления всех бит из тех позиций s, в которых у v стоят 0 (например, , тогда ). Ответчик выбирает R самостоятельно и вычисляет шумные скалярные произведения вида . Удивительно, но предоставления проверяющему возможности выбора используемых в каждой сессии бит s достаточно для предотвращения активных атак. Нам необходимо лишь добавить немного проверок для v и R, посылаемых активным злоумышленником. Наше доказательство основывается на недавно представленной проблемой подпространства LPN [21]. В противовес доказательству защищенности HB+ от активных атак[13], наше доказательство не использует методы перемотки. Избежание этих методов имеет не менее двух преимуществ. Во-первых, сокращение безопасности становится строгим. Во-вторых, доказательства работают также и для квантовых условий: наш протокол защищен против квантовых злоумышленников при предположении что LPN защищен от таких злоумышленников. Как впервые было показано ван де Граафом[22], классические доказательства с использованием перемотки в общем не применимы для квантовых случаев(см. [23] для наиболее актуально информации). Позвольте подчеркнуть, что это означает лишь то, что нет доказательства защищенности для НВ+ в квантовых условиях, однако мы не знаем, существуют ли такие атаки.

МАС и защита от атаки "человек посередине"

В Разделе 4 мы приводим 2 конструкции кодов аутентификации сообщений(Message Authentcation Code,МАС), которые защищены (формально, неподменимы при атаке на выбранное сообщение) в предположении трудности LPN проблемы. Отметим, что МАС применяет двухраундовый ЧП-защищенный протокол аутентификации: проверяющий выбирает случайное сообщение как запрос, а ответчик возвращает МАС по этому сообщению.

В качестве первой попытки, позвольте нам попытаться представить наш протокол аутентификации в качестве МАСа. То есть, МАС-метки вида: , где функция дифференцирования секретного ключа сначала уникально кодирует сообщение m в веса l и затем возвращает , выбирая l бит из s согласно v. Однако, этот МАС не защищен: получив метку , злоумышленник может отправлять запросы подтверждения, в которых он отдельно зануляет ряды R, пока проверка не провалится: в этом случае если последним был занулен i-й ряд, тогда i-й бит должен быть 1(фактически, главной технической проблемой построения защищенного МАСа из LPN является предотвращение утечки секрета s из запросов подтверждения). Наше решение - рандомизировать отображение f, например, использовать для некой случайности b и вычислить метку как , где попарно независимая перестановка (содержится в секретном ключе). Мы можем доказать, что если LPN проблема трудна, то эта конструкция есть защищенный МАС (ключевой аргумент - с высокой вероятностью все нетривиальные запросы подтверждения являются противоречивыми и ведут к отказу). Однако, сокращение безопасности к LPN проблеме неточное, поскольку необходимо угадать величину v из подмены злоумышленника(в контексте шифрования на основе идентификатора ( identity-based encrytpion, IBE) схожая идея использовалась для перехода от выборочных ID к полной безопасности путем "увеличения сложности"[24]). В нашем случае, однако, это все еще приводит к полиномиальному сокращению безопасности, когда необходимо обращаться к сложности LPN-проблемы на стадии разработки (см. Раздел , первый параграф).

Для получения строгого полиномиального сокращения(без необходимости использовать сложность LPN проблемы),в нашем втором построении мы адаптировали метод, изначально использованный Уотерсом[25] в контексте IBE схем, которые были применены к сигнатурам, основанным на решетках[26] и схемам зашифрования[8]. Конкретно, мы подтверждаем рассмотренный выше МАС с различными функциями дифференцирования секретных ключей , где попарная независимая хэш-функция). Недостатком нашей второй модели является больший размер ключа. Наше сокращение безопасности использует метод из [26][8], основанный на кодировании c полноранговыми отличиями (dull-rank differences, FRD) Крамера и Дамгарда[27]

Эффективность

В Таблице 3 представлены грубые сравнения нашего нового протокола и МАСов с НВ, НВ+ протоколами и, в качестве примечания, также и с классической моделью GGM[1]. Второй ряд в таблице определяет понятие безопасности, которое доказуемо достижимо при предположении . это параметр безопасности, n определяет число "повторений". Типичные параметры: . Сложность вычислений считается как число бинарных операция над . Сложность связи считается как общая длина всех переданных сообщений[прим. 2].Последний ряд в таблице определяет жесткость сокращения безопасности, иными словами, какая конкретно достигается безопасность (игнорируя константы и условия высших порядков) предполагая, что -проблема сложна.

Ответчик и проверяющий в НВ, НВ+ и наших новых протоколах должны выполнить бинарных операций в предположении, что (т.е. LPN с секретом длины l) сложна. Это оптимальный вариант, поскольку операций необходимы для вычисления скалярного произведения, который генерирует псевдослучайный бит. Таким образом, мы будем считать МАС или протокол аутентификации эффективным, если он требует бинарных операций. Отметим, что мы получаем также удваивающий длину ГПЧ при предположении с бинарных операций[28]. С помощью классической GGM модели[1], мы получили псевдослучайную функцию (ПРФ) и, следовательно, МАС. Эта ПРФ, однако, требует операций за вызов (где есть размер области ПРФ), что не очень применимо( вспомним, что ).

Связь против размера ключа

Для всех конструкций, кроме GGM, есть естественный компромисс между связью и размером ключа, где для любой константы с(), мы можем снизить связь на множитель с и увеличить размер ключа на множитель с (см. полную версию [29] для точного объяснения, как это делается). Для первых трех протоколов в таблице выбор с не влияет на вычислительную эффективность, но влияет на наши МАСи: для вычисления или подтверждения метки необходимо оценить попарно независимые перестановки(pairwise independant permutation, PIP) по всей длине метки .


Таблица 1. Сравнение наших новых протоколов аутентификации и МАСов с НВ, НВ+ протоколами и классической GGM моделью. Компромиссный параметр сб и термин PIP будут рассмотрены далее.
Модель Безопасность Сложность связи Сложность вычисления Размер ключа Сокращение
HB[6] пассивная(2-раундовый) (строгое)
НВ+[11] активная(3-раундовый)
активная (2-раундовый) (строгое)
(2-раундовый)
(2-раундовый)
GGM [1] (2-раундовый)
- см. .


стандартный путь построения PIP над - определить для случайных . Таки образом, вычислительная стоимость оценки PIP есть одно умножение m битных величин: PIP в таблице считается для этой сложности. Асимптотически, такое перемножение занимает время [30][31], однако для маленьких m (как в нашей схеме) оно не займет меньше, чем умножение из учебника, которое занимает . Для параметров l=500, n=250 и компромиссного с = n (минимизация длины метки m) получим для (иными словами, плюс несколько статистических параметров безопасности) и для . Следовательно, в зависимости от параметров, оценка PIP может быть узким местом нашего МАСа.

Определения

Обозначения

Мы определяем набор целых по модулю целого в . Мы будем использовать обычные, печатные и большие печатные буквы (, x, X) для обозначения отдельных элементов, векторов и матриц над соответственно. Для положительного целого обозначает множество - пустое множество. Для . Для a вектор xx обозначает длину x; wt(x) обозначает вес вектора x по Хэммингу, т.е. число индексов x x[i]. Побитовый XOR двух двоичных векторов x и y обозначается z=xy, где z[i] = x[i] y[i]. Для v обозначим его инверисю как , то есть для всех i. Для двух векторов v и x определим вектор(длины wt(v)), который получается из x удалением всех бит x[i] для таких i, что v[i]=0. Если X матрица, то X определяет подматрицу, которую получим удалением i-й строки при v[i]=0. Функция бесконечно малая, пишется negl, если она стремится к нулю быстрее, чем инверсия любого полинома в ней. Алгоритм вероятнстный полиномиально-временной (probabilistic polynomial time, PPT) если использует случайность в качестве составляющей(вероятностный) и для любого входа x вычисление (x) выполняется за наибольшее число шагов P(x).

Протоколы аутентификации

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

Пассивные атаки

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

Активные атаки

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

Атаки "человек посередине" (MIM)

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

Коды аутентификации сообщений (Message Authentivation Codes, MAC)

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

  • Генератор ключей. Вероятностный алгоритм генерации ключей KG берет на входе секретный параметр и выдает секретный ключ K.
  • Метки. Вероятностный алгоритм аутентификации TAG получает на входе секретный ключ K и сообщение m и выдает метку аутентификации .
  • Проверка. Детерминистский алгоритм проверки VRFY получает на входе секретный ключ K, сообщение m и метку и выдает {принято, отказ}.

Если алгоритм TAG детерминистский и нет явной необходимости определять VRFY, поскольку он уже определен в алгоритме TAG как VRFY.

Полнота

Мы говорим, что МАС имеет ошибку полноты если для всех и :

.

Безопасность

Стандартное определение безопасности для МАС это неподменяемость при атаке на выбранное сообщение(uf-cma). Мы определяем как преимущество злоумышленника в подмене сообщения при атаке на выбранное сообщение для МАС при использовании параметра . Формально это вероятность того, что следующий эксперимент вернет 1.

TemplateLemmaIcon.svg Лемма «Эксперимент»

Вызовем , который может выполнить до Q запросов к и . На выходе 1, если сделал запрос в , Где

  1. еще не сделал запрос m в .

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


Мы говорим, что МАС защищен против uf-cma злоумышленников, если для любых , выполняющихся за время t в эксперименте выше, имеем .

Трудно обучаемые проблемы

Пусть - распределение Бернулли над с параметром (отклонением) (иными словами, если ). Для определяет распределение над , где каждый вектор состоит из l независимых моделей, взятых из . Зная секрет x и мы пишем для распределения над , модели которого получаются выбором вектора и выводом с . Предположение LPN, формально определенное ниже, гласит, что трудно выделить (со случайным секретом x) из нормального распределения.

TemplateDifinitionIcon.svg Определение «Определение 1(Обучение четности с шумом)»
проблема(с принятием решений) является -трудной если для каждого различителя D, выполняющегося за время t и создающего Q запросов,

Далее мы определим более сильное(на первый взгляд) подпространство LPN предположений (SLPN для краткости), недавно представленное в [21]. Здесь злоумышленник может запросить скалярные произведения не только с секретом x, но даже с , где A и b могут быть выбраны адаптивно, но A должна иметь достаточно высокий ранг. Для минимальной размерности , секрет x и A определим распределение:

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

TemplateDifinitionIcon.svg Определение «Определение 2(Подпространство LPN)»
Пусть , где . проблема (с принятием решений) являетсятрудна если для каждого различителя D, выполняющегося за время t и создающего Q запросов

,

где при входных (A,b) выдает модель если и в противном случае.

Следующее предложение гласит, что отображение подпространства LPN проблемы в размерность d + g почти такое же трудное, как и стандартная LPN проблема с секретной длиной d. Различие в трудности экспоненциально мало в g.

TemplateLemmaIcon.svg Лемма «Предложение 1(Из [21]
Для любых l,d,g, если - проблема сложна, то -проблема сложна, где


Для некоторых из наших конструкций нам понадобятся лишь ослабленные версии -проблемы, которые мы называем подмножеством LPN. Как показывает название, здесь злоумышленник не запрашивает скалярные произведения с для любых A (ранге не меньше d), но только с подмножеством x(размера не меньше d). Это будет удобно для того, чтобы четко определить этот особый случай. Для пусть определяет нулевую матрицу с диагональю v и пусть


TemplateDifinitionIcon.svg Определение «Определение 3 (Подмножество LPN)»
Пусть . -проблема -сложна, если для различителя D, выполняющегося за время t и создающего Q запросов

.

где принимает v при и выдает модель или в противном случае.
TemplateLemmaIcon.svg Лемма «Замечание 1»
Модель имеет форму , где . Для вычисления скалярного произведения необходимо только , остальные биты не имеют значения. Мы используем это наблюдение для улучшения сложности связи(для протоколов) или длины метки (для МАСов), применяя "сжатые" модели вида .


Двухраундоая аутентификация с активной безопасностью

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


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

- длина секретного ключа

параметр ошибочного распределения Бернулли

допустимый порог

число параллельных повторений (нам требуется )

  • Генерация ключа. Алгоритм принимает и возвращает s как секретный ключ.
  • Протокол аутентификации 2-раундовый протокол аутентификации с ответчиком(prover) и проверяющим(verifier) представлен на рисунке 3.
EAHLP Fig4.PNG
Рис. 3 2-раундовый протокол аутентификации AUTH с активной защитой на основе LPN предположения
TemplateTheoremIcon.svg Теорема Теорема 1
Для любой постоянной пусть . Если проблема -сложна, то протокол аутентификации на рис. 3 -защищен от активных злоумышленников, где для постоянных это зависит только от и соответственно:

.

Протокол обладает ошибкой полноты , где зависит только от
Доказательство
Без доказательства


Доказательство полноты

Для любых пусть

определяет вероятность того что n независимых выборок по Бернулли со сдвигом содержат более чем единичных частей. Последнее приравнивание в следует из границы Хефдинга, где константа зависит только от

Теперь мы докажем,что протокол аутентификации имеет ошибку полноты . Проверяющий выполняет две проверки. На первом шаге верификации, проверяющий отказывает в случае, если случайная матрица R имеет не полный ранг. В полной версии [29] мы доказываем, что вероятность такого события . Теперь пусть определяет шум, добавляемый . Теперь, на втором шаге верификации, проверяющий откажет в случае, если . Из равенства мы знаем, что это случится с вероятностью . Этим мы доказали полноту.

Доказательство безопасности

Сначала мы определим некоторые термины, которые будем использовать в дальнейшем. Для постоянной пусть (как в Теореме 1). Пусть обозначает вероятность того, что случайная подстрока длины l из строки длины 2l с весом l по Хэммингу имеет вес по Хэммингу менее d. Используя то, что ожидаемый вес по Хэммингу можно показать, что существует постоянная (зависит только от ) такая, что

Для пусть обозначает вероятность того, что случайная битовая строка имеет вес по Хэммингу . Из границы Хэфдинга следует, что существует постоянная (зависящая только от ) такая, что:

.

Теперь докажем безопасность протокола аутентификации. Примем во внимание оракула , являющегося либо оракулом подмножества LPN либо как в Определении 3. Смоделируем нарушителя который пользуется (который взламывает активную безопасность AUTH с преимуществом ) в манере черного ящика так, что:

и

Таким образом может различать 2 оракулов с преимущество как утверждает Теорема. Ниже мы определим .

Начальные условия. Изначально представляет собой

.

Интуитивный вариант действия следующий. предположим сперва, что - оракул подмножества LPN с секретом x. В первой фазе нам нужно получить ответы (R,z) на запрос при помощи . Симулированные ответы имеют точно такое же распределение, как и ответы честного ответчика , где

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

Если - случайный оракул , то после первой фазы является теоретически скрытой информацией, и следовательно не может выдать подходящую подмену, кроме как с экспоненциально низкой вероятностью. <m Первая фаза. На первой фазе вызывает , который ожидает доступа к . Теперь определим, как определяет модель ответа (R,z) на запрос , посылаемый . Пусть

  1. запрашивает своего оракула n раз на вход u. Если выход оракула (что случается при wt(u) < d), то выдает 0 и останавливается. В противном случае пусть определяют n выходов оракула.
  2. Выбрать и присвоить .
  3. Вернуть и .

Вторая фаза. Когда-нибудь перейдет во вторую фазу активной атаки, ожидая запроса от .

  1. посылает как запрос к .
  2. отвечает некоторыми .
  3. проверяет

и

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

TemplateTheoremIcon.svg Теорема Требование 2
Доказательство
Если не полноранговая, то возвращает ноль по определению. Следовательно, мы считаем что .

Ответы (R,z), получаемые злоумышленником из независимы от (например, однородна если однородна). Поскольку однородно случайна и полноранговая, то вектор

однородно случаен над . Следовательно, вероятность того, что вторая проверка в не провалится .


TemplateTheoremIcon.svg Теорема Требование 3
.
Доказательство
Разделим доказательство на 2 части. Сначала покажем, что выдает 1 с вероятностью если оракул подмножества LPN принимает подмножество произвольно малого размера (и не просто выдает при входном v с wt(v)>d), другими словами,

.

Затем мы поднимем верхнюю границу разрыва между вероятностью того, что выдает 1 в случае выше и того, что выдает 1 при доступе к оракулу, которые интересуют нас в следующем виде:

Тогда требование выполняется из неравенства треугольника из двух требований выше.


Выражение выполняется, если:

  • Ответы (R,z), которые отправляет на запросы в первой фазе атаки имеют в точности такое же распределение, которое получает при взаимодействии с честным ответчиком , и подставной секрет s определяется в .

Чтобы в этом убедиться, вспомним, что на запрос 'v от должен вычислить n моделей SLPN ( и затем отправить сжатую версию этих моделей ( то есть, , где , см. замечание 1). Теперь покажем, что z, вычисляемое , действительно имеет в точности такое же распределение. На первом шаге запрашивает у оракула и получает шумные скалярные произведения с частью , состоящей только из бит x, то есть

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

На третьем шаге генерирует из предыдущих значений, где определяется и . Используя , мы получим

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

Этим доказательство завершается. Остается доказать . Отметим, что ведет себя также, как до тех пор, пока не будет послан запрос v, для которого .

Поскольку , для любых v вероятность того, что есть(по определению) из равенства . Используя границы объединения, мы можем jограничить сверху вероятность для любых Q злоумышленником выбираются разные v в виде

Избежание проверки

Одним недостатком протокола в Таблице 1, в сравнении с HB протоколами, это необходимость проверять сообщение на правильность путем: ответчик проверяет вес вектора v ( он должен быть l), а проверяющий выполняет еще более дорогую проверку на полноранговость R. Устранение таких процедур проверки может быть весьма полезным если, к примеру, ответчик - это чип RFID, где даже простая проверка уже дорогая. Отметим, что возможно устранить это проверки заполняя сообщения v и z, используя случайные векторы и соответственно, как показано на рис. 5. Безопасность и полнота этого протокола в целом такие же, как у протокола на рис.5. Доказательство безопасности также очень похоже и потому опускается.

РИСУНОК 5

Коды аутентификации сообщений

В этом разделе мы построим два протокола аутентификации сообщений (message authentication codes, MAC), чья безопасность сводится к предположению LPN. Наша первая конструкция основана на 2-раундовом протоколе аутентификации из Раздела 3. Мы доказываем, что если LPN-проблема сложна, то ни один злоумышленник, посылающий Q запросов, не может подделать МАС с вероятностью более . Однако, у этой конструкции есть недостаток, заключающийся в необходимости определить сложность LPN-проблемы в момент построения, см. Замечание 2. Наша вторая конструкция не имеет этого недостатка и достигает уровня безопасности в . Эффективность этой конструкции схожа с первой, но требует большего ключа.

Первая конструкция

Вспомним 2-ранудовый протокол аутентификации из Раздела 3. В том протоколе проверяющий выбирает случайное подмножество v. Чтобы превратить этот интерактивный протокол в МАС, мы будем вычислять v' из сообщения m, проходящего аутентификацию, в виде , где h - попарная независимая хэш-функция, - некоторая случайная величина и C - некая схема зашифрования. Код C фиксирован открыт, в то время как функция h - часть секретного ключа. Метка аутентификации вычисляется схожим способом с ответом ответчика в протоколе. Иными словами, мы берем случайную матрицу и вычисляем шумное вектороное произведение , где . Мы отмечаем, что использование (R,z) в качестве метки аутентификации не будет безопасным, и нам необходимо заполнить эти значения. Это делается применением попарных независимых перестановок (ПНП) - которые являются частью секретного ключа - к .

Конструкция

Код аутентификации сообщений с сопутствующим пространством сообщений определяется следующими составляющими.

  • Публичные параметры обладает следующими открытыми параметрами.

аналогично протоколу из раздела 3

длина выхода хэш-функции

длина случайной величины

кодирование, где имеем и

  • Генерация ключа. Алгоритм моделирует , попарную независимую хэш-функцию и попарную независимую перестановку над . Он возвращает в качестве секретного ключа.
  • Метки Получая секретный ключ и сообщение , алгоритм TAG выполняется следующим образом.
  1. Вернуть
  • Проверка Принимая на входе секретный ключ , сообщение и метку , алгоритм VRFY выполняется следующим образом.
  1. Разбор в виде . Если , вернуть отказ
  2. Если вернуть отказ, иначе вернуть принято
TemplateTheoremIcon.svg Теорема Теорема 4
Для , постоянной и , если -проблема -сложна, то -защищен от uf-cma злоумышленников, где

имеет ошибку полноты , где зависит только от
Доказательство


TemplateLemmaIcon.svg Лемма «Вывод 1»
Выбирая так, чтобы в теореме выше, мы получаем . Второе выражение здесь минимально, и решая для получим:


TemplateLemmaIcon.svg Лемма «Замечание 2(о
Отметим, что для достижения заявленной безопасности в выводе 1, нам необходимо выбрать как функцию от Q и так, чтобы для как в выражении . Конечно, мы можем просто зафиксировать Q (как верхнюю границу числа запросов злоумышленника) и (как нашу догадку действительной трудностью ). Но слишком заниженная догадка по (например, выбор слишком маленького значения) в результате даст конструкцию, чья безопасность будет хуже, чем заявленная в выводе 1. Слишком высокая догадка, с другой стороны, сделает снижение безопасности бесполезным(хотя мы и не имеем никаких действительных атак на МАС для больших ).


Теперь предлагаем основные моменты доказательства Теоремы 4. Из соображений свободного места, полное доказательство будет приведено только в полной версии этой статьи [29]. Каждый запрос к VRFY и запрос m к TAG определяет подмножество v (как вычисляется во втором шаге в определениях этих функций). Мы говорим, что подделка "свежее", если v, содержащееся в отличается от всех v, содержащихся в предыдущих запросах к TAG и VRFY. Доказательства для разных случаев различны и используют разные сокращения для случаев, когда подмена ближе к "свежей" или ближе к "несвежей". В обоих случаях мы рассматриваем сокращение , которое имеет доступ либо к нормальному оракулу , либо к оракулу LPN-подмножества . использует злоумышленника , который может найти подмену для МАС для разделения этих случаев и таким образом взломать предположение LPN. В первом случае, когда первая подмена скорее "несвежая", мы можем показать (используя тот факт, что попарные независимые перестановки используются для зашумления метки) что если оракулом является , то даже вычислительно неограниченный не может найти пару сообщение-метка , которая содержит только "несвежие" v. Таким образом, мы разделили случаи оракулов и простым наблюдением за тем, посылает ли когда-либо запрос к VRFY , содержащий "несвежий" v. (даже без возможности определить, является ли верным или нет).

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

Вторая конструкция

Теперь мы представим конструкцию другого , основанного на трудности LPN проблемы. Основное отличие от из предыдущего раздела - это способ генерации величин . В новой конструкции определим , где каждый является частью секретного ключа. Конструкция использует идеи из схемы IBE Уотерса[25], и части сокращения безопасности используют способы симуляции из [26][8] для адаптации к бинарному случаю.

Конструкция

Код аутентификации сообщений с сопутствующим пространством сообщений определяется следующим.

  • Открытые параметры.

как в протоколе атентификации из Раздела 3.

выходная длина хэш-функции

длина случайности

  • Генерация ключа Алгоритм моделирует и выбирает попарную независимую хэш-функцию , вместе с попарной независимой перестановкой над . Он возвращает в качестве секретного ключа.
  • Метки Получая секретный ключ и сообщение алгоритм TAG выполняется следующим образом.
  1. Вернуть
  • Проверка Имея на входе секретный ключ , сообщение и метку , алгоритм VRFY работает следующим образом.
  1. Анализ в виде . Если , то вернуть "отказ"
  2. Если вернуть "отказ", в противном случае вернуть "принято".
TemplateTheoremIcon.svg Теорема Теорема 5
Если -проблема -сложна, то защищен от uf-cma злоумышленников, где

имеет ошибку полноты , где зависит только от .
Доказательство
Сейчас мы приведем основные моменты доказательства Теоремы 5. По причине, аналогичной Теореме 4, мы не приводим полный текст доказательства (см. полную версию документа[29]. Аналогично Теореме 4, мы выделяем 2 случая: "свежие" и "несвежие" подмены. Здесь есть интересный новый момент в "свежем" случае. Идея в том, что в сокращении к SLPN проблеме мы определяем функцию ( где s - LPN-секрет) таким образом, что следующие пункты имеют ненулевую вероятность:
  1. Для каждого из запросов TAG имеет полный ранг и, следовательно, метки можно симулировать, используя оракула ;
  2. Для первой первой "свежей" подмены имеем так, что не зависит от s и сокращение может проверить верность подмены.
Эти два свойства позволяют поддерживать симуляцию. Настройка функции - очень важный этап и здесь мы адаптируем методы Бойена[26], основанные на гомоморфных кодированиях с полноранговыми отличиями, которые позволяют произвольно контролировать вероятность того, что это симуляция работает.


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

Кржиштоф хотел бы поблагодарить Вадима Любяшевского за множество интересных разговоров о LPN во время нахождения в Тель-Авиве и Эйяфьядлайёкюдль за то, что он позволил этим разговорам состояться.

Примечания

  1. См. неполный список связанных статей http://www.ecrypt.eu.org/lightweight/index.php/HB
  2. Для МАСов мы принимаем во внимание, что связь принимается при создании ЧП-защищенного 2-раундового протокола из МАСа, заставляя ответчика вычилсить метку от случайного сообщения из запроса.
  3. С использованием гибридного аргумента можно показать, что безопасность достигается даже при условии, что злоумышленник может взаимодействовать в независимых вариантах одновременно (и достигает успеха, если проверяющий примет хотя бы одну из них). использование гибридного аргумента позволяет избавиться от множителя k в сокращении безопасности

Авторы статьи

  1. RU Bochum; Финансирован Наградой им. Софьи Ковалевской Фонда Александра вон Хамболдта и Немецким Федеральным Министерством Образования и Науки.
  2. CWI Amsterdam; При поддержке Европейского Исследовательского Совета по Седьмой рамочной программе ЕС 9FP7/2007-2013) / Стартовый Грант ЕИС (259668-PSPC).
  3. UC San Diego; При поддержке NSF CCF-0915675.Исследование проведено при посещении CWI Amsterdam.
  4. UC Los Angeles;Исследование проведено при посещении CWI Amsterdam.
  5. Sapienza University of Rome; Исследование проведено при посещении CWI Amsterdam.

Литература

  1. 1,0 1,1 1,2 1,3 Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM 33, 792–807 (1986)
  2. Berlekamp, E., McEliece, R., van Tilborg, H.: On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory 24(3), 384–386 (1978)
  3. 3,0 3,1 Blum, A., Furst, M.L., Kearns, M.J., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994)
  4. 4,0 4,1 Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM 50(4), 506–519 (2003)
  5. Kearns, M.J.: Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983–1006 (1998)
  6. 6,0 6,1 6,2 6,3 6,4 Hopper, N.J., Blum, M.: Secure human identification protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001)
  7. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, New York (2005)
  8. 8,0 8,1 8,2 8,3 Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010)
  9. Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: 32nd ACM STOC, pp. 435–440. ACM Press, New York (May 2000)
  10. Levieil, ´E., Fouque, P.-A.: An improved LPN algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, Heidelberg (2006)
  11. 11,0 11,1 11,2 11,3 Juels, A., Weis, S.A.: Authenticating pervasive devices with human protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 293–308. Springer, Heidelberg (2005)
  12. Katz, J., Shin, J.S.: Parallel and concurrent security of the HB and HB protocols. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 73–87. Springer, Heidelberg (2006)
  13. 13,0 13,1 13,2 13,3 Katz, J., Shin, J.S., Smith, A.: Parallel and concurrent security of the HB and HB protocols. Journal of Cryptology 23(3), 402–421 (2010)
  14. 14,0 14,1 14,2 Gilbert, H., Robshaw, M., Sibert, H.: An active attack against HB - a provably secure lightweight authentication protocol. Cryptology ePrint Archive, Report 2005/237 (2005), http://eprint.iacr.org/
  15. Bringer, J., Chabanne, H., Dottax, E.: HB: a lightweight authentication protocol secure against some attacks. In: SecPerU, pp. 28–33 (2006)
  16. Duc, D.N., Kim, K.: Securing HB against GRS man-in-the-middle attack. In: SCIS (2007)
  17. Munilla, J., Peinado, A.: HB-MP: A further step in the HB-family of lightweight authentication protocols. Computer Networks 51(9), 2262–2267 (2007)
  18. Gilbert, H., Robshaw, M.J.B., Seurin, Y.: Good variants of HB are hard to find. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 156–170. Springer, Heidelberg (2008)
  19. 19,0 19,1 Gilbert, H., Robshaw, M.J.B., Seurin, Y.: HB: Increasing the security and efficiency of HB. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 361–378. Springer, Heidelberg (2008)
  20. Ouafi, K., Overbeck, R., Vaudenay, S.: On the security of HB against a man-inthe-middle attack. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 108–124. Springer, Heidelberg (2008)
  21. 21,0 21,1 21,2 Pietrzak, K.: Subspace LWE (2010) (manuscript) http://homepages.cwi.nl/~pietrzak/publications/SLWE.pdf
  22. Van De Graaf, J.: Towards a formal definition of security for quantum protocols. PhD thesis, Monreal, P.Q., Canada, AAINQ35648 (1998)
  23. Watrous, J.: Zero-knowledge against quantum attacks. SIAM J. Comput. 39(1), 25–58 (2009)
  24. Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)
  25. 25,0 25,1 Waters, B.R.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005)
  26. 26,0 26,1 26,2 26,3 Boyen, X.: Lattice mixing and vanishing trapdoors: A framework for fully secure short signatures and more. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 499–517. Springer, Heidelberg (2010)
  27. Cramer, R., Damgard, I.: On the amortized complexity of zero-knowledge protocols. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 177–191. Springer, Heidelberg (2009)
  28. Fischer, J.-B., Stern, J.: An efficient pseudo-random generator provably as secure as syndrome decoding. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 245–255. Springer, Heidelberg (1996)
  29. 29,0 29,1 29,2 29,3 The full version of this paper will be posted on the Cryptology ePrint Archive,http://eprint.iacr.org/
  30. Sch¨onhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Computing 7 (1971)
  31. F¨urer, M.: Faster integer multiplication. SIAM J. Comput. 39(3), 979–1005 (2009)