Безопасная аутентификация по слабому ключу без утечки информации

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 11:02, 9 ноября 2015.
Secure Authentication from a Weak Key, Without Leaking Information
NTRU.PNG
Авторы Damien Stehle[@: 1],
Ron Steinfeld[@: 2]
Опубликован 2011 г.
Сайт Homepage of Damien Stehle, Homepage of Ron Steinfeld
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Содержание

Теория

Мы изучаем проблему аутентификации, основанной на слабом ключе, в теоретико-информационной области. Ключ называют слабым, если его мин-энтропия — произвольная малая доля его битовой длины. Этой проблеме в последнее время уделяют значительное внимание, с помощью различных решений оптимизируя различные параметры. Мы рассматриваем данный вопрос в широком смысле, где слабый ключ — одноразовый сессионный ключ, полученный от публичного источника случайным образом с помощью (потенцильно тоже слабого) долгосрочного ключа. Наша задача в настоящий момент — аутентифицировать сообщение с помощью слабого сессионного ключа таким способом, чтобы не произошло (почти) никакой утечки информации долгосрочного ключа. Обеспечение конфиденциальности долгосрочного ключа жизненно важно для его вторичного использования. Предыдущая работа не считается такой проблемой конфиденциальности, и прошлые решения не выглядят удовлетворяющими этим требованиям. Мы покажем существование практического четырёхэтапного протокола, обеспечивающего аутентификацию сообщений слабым сессионным ключом, и избегающего незначительных утечек долгосрочного ключа. Безопасность нашей схемы также принимает во внимание моменты, где злоумышленник может ограничиться частичной информацией слабого сессионного ключа. Как применение нашей схемы, мы покажем существование идентификационной схемы в ограниченной квантовой(порционной) модели хранения, противостоящей атаке man-in-the-middle(встраивание) и имеющей чисто парольную основу: она не нуждается в ключе с высокой энтропией, в противоположность схеме, предложенной Дамгардом и другими.

Введение

Проблема

Рассмотрим проблему достижения аутентичной коммуникации через общественный канал, который может находиться под контролем активного злоумышленника. Мы изучаем эту проблему в информационно-теоретической области, т. е. мы полагаем, что злоумышленник не ограничен в вычислительных средствах. Конкретно, мы рассмотрим следующий сценарий. Алиса и Боб имеют долгосрочный ключ W. При необходимости Алиса и Боб могут извлечь слабый сессионный ключ Xw из вспомогательного источника случайных чисел с помощью W. Свойствами такого источника гарантируется, что потенциальный злоумышленник Ева, не знающий W, имеет ограниченную информацию о слабом сессионном ключе Xw. Это формализуетс я требованием Hmin (Xw|W E) ≥ k для некоего параметра k, где E обозначает информацию на стороне Евы. Примеры, в которых данный сценарий имеет место естественным образом, ограничены моделью хранения, где W определяет, какую часть огромной строчи читать, или частичной областью, где W определяет, в каком базисе измерять некое квантовое состояние. Теперь стоит задача проверить подлинность сообщения μ от Алисы Бобу с помощью слабого сессионного ключа Xw, таким образом, чтобы (1) Ева не могла исказить его, не будучи замеченной, и (2) Ева не узнала никакой информации о долгосрочном ключе W. Мы подчёркиваем, что свойство (2) жизненно необходимо Алисе и Бобу для того, чтобы в дальнейшем использовать ключ W. Заметим, что использовав аутентификацию слабым ключом, Алиса и Боб могут также заключить ключевое соглашение, просто стандартно случайным образом производя извлечение, где источник экстрактора связано подтверждённым образом. Мы хотим подчеркнуть, что, по предположению, каждый новый Xw ключ сеанса для того же самого долгосрочного ключа W содержит новую случайность, обеспечиваемую вспомогательным источником. Следовательно, выше описанная задача не противоречит хорошо известной невозможности аутентификационного ключа без обновления. Заметим также, что мы не указываем, как точно вспомогательный источник случайности создаёт Xw из W; вопреки этому мы хотим безопасности независимо от того, как Xw был получен, как только Xw содержит достаточно ми-энтропии (данной информацией злоумышленника и ключом W).

Схожая работа

Пусть n — битовый размер ключа (в нашем случае, ключа сессии) и k — его мин-энтропия (в битах). Додисом и Вичсом доказано, что неинтерактивная аутентификация невозможна, когда k ≤ n/2, даже в том случае, когда стороны имеют доступ к локальному источнику случайности, который мы будем предполагать. Авторство первого протокола интерактивной аутентификации для произвольного слабого ключа принадлежит Реннеру и Вулфу. Требуется (l) раундов взаимодействия для проверки подлинности сообщения длиной l –бит. В случае [1] аутентификационный протокол для произвольного слабого ключа описан так, что требуется всего два раунда, что является оптимальным (с точки зрения количества раундов). Чандран и другие [2] делают акцент на минимизации энтропийной потери и описывают протокол усиления конфиденциальности, оптимальной с точки зрения энтропийной потери (с точностью до констант). Их конструкция требует линейного числа раундов (линейного в параметрах безопасности). Случай, в котором Алиса и Боб имеют высоко-коррелированные, но возможно, неравные ключи – “нечёткий” случай – решён в [3] и улучшен Канукурти и Рейзином [4], но также покрывается [1] и [2]. Мы подчеркиваем, что ни одна из этих работ не может решить случай, когда слабый ключ получен из долгосрочного ключа и где сохранность долгосрочного ключа должна быть гарантирована.

Наш вклад

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

Применение

Наше главное применение заключается в парольной идентификации на ограниченной квантовой модели хранения, предложенной Дамсгардом и другими. Две идентификационные схемы были предложены в [5] , Q-ID, защищённая только от злоумышленных Алисы и Боба, и Q-ID+, которая также защищена против MITM атак. Тем не менее, только Q-ID на самом деле имеет парольную основу; в Q-ID+ Алиса и Боб, в дополнение к паролю, должны делить ключ с высокой энтропией. Включением наших новых технологий в Q-ID+, мы покажем существование действительно парольной идентификационной схемы ы ограниченной квантовой модели хранения с защитой от MITM атак. Основываясь на Q-ID+, Дамгард и другие также предложили схему распространения аутентифицированного частичного ключа в ограниченной квантовой модели хранении, которая, по сравнению со стандартной схемой распространения частичных ключей, не требует аутентифицированной коммуникации, но имеет встроенную проверку подлинности. Наша релаксация на требуемый ключевой материал в Q-ID+ влияет на схему распределения ключей и обходит необходимость в ключе с высокой энтропией. Как результат, мы получаем схему распределения парольных аутентификационных ключей в ограниченной модели хранения.

Структура статьи

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

Обозначения


Докажем безопасность нашей схемы в присутствии квантового противника с частичной информацией и введем некоторые подходящие обозначения. Однако подчеркнём, что большинство заметок и доказательств можно почерпнуть из классической информационно-теоретической точки зрения.
= P()| | |=, где P - возможное распределение, формы ортонормального базиса и |= . В этом случае можно понимать как случайную величину, и система в состоянии |=, особенно если принимает значение . Поэтому мы также говорим о случайной величине и квантовой системе . Чтобы упростить обозначения, мы часто пишем вместо |=. Читатели, не знакомые с частью информации, могут смело принимать как классическое, в этом случае |= все являются диагональными с вероятностями условных распределений P|(|) как диагональные элементы.
Расстояние между двумя состояниями , измеряется по длине пути || - ||1, где 1 - норма L1. В случае классических состояний, т.е. и соответствуют распределениям и , длина пути совпадает со статическим расстоянием |() - ()|.
В следующем приближении мы рассмотрим двудольную систему с классическим . называют случайной и независимой, если = U , где U - полностью смешанное состояние на (т.е. U - классическое, с равномерным распределением). В случае классического это эквивалентно = (в том смысле, что (,) = () () ). Следующее определение показыват, как далеко от идеальной ситуации.

Определение 1. (Расстояние до формы)

Расстояние до формы X данного E определяется как
- 1.
Если E также классическое, упрощается до

Нетрудно показать, что для трёхчастной системы с классическими и

Из этого следует лемма 1.

Лемма 1.

Для любого

Определение 2 (Вероятность угадывания).

Вероятность угадывания данного определяется как
,
где верхняя грань берётся по всем {}на .
В случае, если и E классическое, Guess упрощается до стандартного среднего ожидания вероятности

Определение 3 (Мин-энтропия).

Мин-энтропия данного определяется как

Это определение совпадает с определением, введённым Реннером [7], как показано в [8]

в случае классического E, оно совпадает с классическим определением условной мин-энтропии [9].


=== Определение 4. === Функция является - сильный экстрактор, если для любой двухчастной квантовой системы с классическим и и для равномерного и независимого источника имеем

Заметим, что мы находим термин "экстрактор квантовых противников" довольно громоздким; поэтому мы просто называем Ext (сильным) экстрактором, даже если он является более сильным, чем стандартный. При необходимости, мы проводим различие между двумя понятиями, говоря, что экстрактор защищён или не защищен от дополнительной информации.
Хорошо известный пример сильного экстрактора (защищённого от квантов сторонней информации) - это двоично-универсальная хэш-функция Действительно, для любой с классическим , и для независимого источника , равномерно распределённом на усиление приватности [10] гарантирует, что

Определение безопасности.

В масштабе этой статьи, протокол аутентификации понимается как классический протокол между двумя сторонами - Алисой и Бобом. Алиса вводит сообщение и слабый сессионный ключ , и Боб вводит сообщение и тот же ключ . В конце протокола Боб объявляет булево решение - "принять" или "отклонить". Слабый сессионный ключ может зависеть произвольно от долгосрочного ключа . Во время исполнения протокола злоумышленник Ева имеет полный контроль над связью между Алисой и Бобом.
Мы требуем, чтобы протокол удовлетворял следующему формальному определению.

Определение 5.

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

Схема аутентификации Додиса-Вичса


Здесь мы опишем немного модифицированную версию двух-раундового протокола аутентификации сообщений Додиса и Вичса. Наша конструкция будет основана на этом протоколе. Начнём с нескольких ключевых определений.

Определение 6.(Эпсилон-предугадывание)

Пусть - целые положительные. Пусть случайные величины в диапазоне , и пусть ,math>E</math> - квантовая система. Для любого пусть определяется как

Упорядоченная пара (A,B) - предугадывание, обусловленное если

Определение 7.(Предугадывающий экстрактор)

называют -предугадывающим экстрактором если для любой случайно величины и квантовой системы c имеет место следующее. Пусть - независимый и равномерно распределённый источник, и пусть противоположно выбраны данные S и E, это может включать измерение E, в результате будет получено новое состояние E'. Затем, упорядоченные пары , где и -предугадывание обусловленное и .


Неформально, предугадывающий экстрактор имеет свойство, что даже если злоумышленник может модифицировать источник, получив первые >math>i</math> бит ключа, полученные с помощью модифицированного источника, оставшиеся блоки ключа, извлечённые корректным источником, по прежнему выглядят случайными.

Определение 8.(Предугадывающая безопасность )

Семейство функций

индексируемые ключами являются предугадывающе-безопасными MAC если для любой пары фиксированных и отдельных сообщений , и для любой упорядоченной пары случайных величин , удовлетворяющей свойству с параметром , определённым в системе ,
.
Теперь мы готовы представить протокол аутентификации сообщений Додиса и Вичса - DW-MAC. Этот протокол немного модифицирован, мы предполагаем, что Алиса уже отправила Бобу сообщение , а он получил его как сообщение (возможно, . Модификация проведена для простоты, и потому, что нашей целью не является минимизация количества раундов. Функция есть - предугадывающий экстрактор и есть надёжный MAC.
DW-MAC






Надёжность DW-MAC следует из определений основных блоков: laExt обеспечивает, что версии ключа K Алисы и Боба удовлетворяют предугадывающему свойству, и в этом случае гарантируется, что MAC действует как надёжный MAC, даже когда ключ Алисы модифицирован.
Тем не менее, в нашем случае мы хотим дополнительно поддерживать конфиденциальность долгосрочного ключа W, который может произвольно зависеть от , DW-MAC не выглядит достаточно хорошим вариантом - пока Ева остается пассивной. Действительно, если Ева не манипулирует связанным источником , то из предполагаемой нижней границы следует, что извлечённое на стороне Боба близко к случайному и независимому и , и поэтому из не происходит утечки информации о . Однако, если Ева манипулирует источником (заменяя его значением по своему выбору), то больше не гарантируется отсутствие утечек информации о W.
Ещё одина, но более тонкая, потенциальная возможность для Евы добыть информацию о , не меняя сообщение, т.е. оставляя , но меняя источник и пытаясь получить информацию о , наблюдая, подтверждает Боб или нет.

3.1 На пути к конфиденциальности ключа

Здесь мы приведём некие размышления на тему того, как преодолеть проблемы безопасности DW-MAC по отношению к долгосрочному ключу . Аналогично нашим обозначениям, и отличаются от ярлыков, вычисленных Алисой и Бобом соответственно, мы записываем и , отличные от значений Алисы и Боба, которые могут различаться, если Ева активно манипулирует передаваемыми сообщениями.
Первой попыткой предотвратить утечку через было одноразовое шифрование . Ключ для шифрования добывается средствами сильного экстрактора Ext из , где Алиса выбрала ядро:






В приведённом выше протоколе (а также ниже), мы понимаем, что и вычисляется как в DW-MAC. Заметим, что как только Алиса выбирает ядро и ограничено снизу, гарантированно близко к случайному независимому ), и потому скрывает всю информацию, которая может просочиться через о . Однако, эта модификация делает безопасность схемы недействительной. Например, мы не можем исключить то, что модифицируя ядро соответственно, Ева может привязать , поэтому ей достаточно послать , чтобы убедить Боба.

Произведение следует понимать в соответствующем бинарном поле. Утечка из по прежнему предотвращается, поскольку ненулевой составной одноразовый ключ по-прежнему хороший одноразовый ключ. Более того, для безопасности, мы можем интуитивно рассуждать следующим образом. Рассмотрим этап выполнения протокола после того, как было сообщено. Теперь мы даём Еве значение просто так; это делает её только сильнее. Безопасностью лежащего в основе DW-MAC, мы знаем, что для Евы трудно угадать значение . Теперь, предполагая, что существует два различных значения , для каждого из которых Ева может предугадать соответствующее значение , следует, что Ева действительно может предугадать , получаем противоречие. Однако, может быть не более одного значения выбора Боба, для которого Ева достаточно хорошо может предугадать .
Отметим, что приведённые выше интуитивные соображения включают перемотку; в обычном случае это нормально, но в квантовом случае не проходит (см. [11]). Таким образом, в неформальном доказательстве безопасности мы позволяем Еве поддерживать квантовое состояние. Как следствие, в качестве протокола, считается несколько иным образом.
Остаётся нерешённой проблема, что решение Боба, принять или отклонить, может также пропускать информацию о когда и Ева модифицирует одно или оба ядра или . Отметим, что проблемы нет в случае , потому что тогда Боб отклоняет с полной уверенностью. Например, может случиться так, что изменение первого бита меняет или не меняет , зависит от . Таким образом, изменяя первый бит и получая решения Боба, Ева может узнать первый бит , что может дать ей один бит информации о . Решение о преодолении этой проблема напрашивается интуитивно: использовать MAC не только для аутентификации сообщения, но и двух ядер и . Затем, как в случае . если Ева меняет одно из ядер, решение Боба - отклонить. Отметим, что данная модификация представляет некую рекурсию: ключ , используемый для аутентификации ядра получается из средствами ядра . Однако, оказывается, что мы можем с этим справиться.

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

Теперь обратимся к нашей конструкции протокола аутентификации сообщений с секретным долгосрочным ключом (Определение 5). В конструкции мы будем использовать DW-MAC как строительный блок. Говоря неформально, основная идея в том, чтобы зашифровать аутентификационную метку DW-MAC используя одноразовую запись, предотвращающую утечку ключа. Такой ключ создаётся в последовательности вопросов-ответов, из смеси локальной и общей случайности. В дополнение к этому, мы используем DW-MAC протокол для аутентификации некоторых ядер экстракторов, которые появляются в конструкции, для предотвращения утечки из решений Боба.
Пусть будет предугадывающим экстрактором. Пусть будет -сильным экстрактором. Пусть MAC: будет предугадывающим защищённым MAC, для любого . Пусть - сессионный ключ, общий для Алисы и Боба, и удовлетворяющий . Символ представляет побитовое сложение по модулю 2. Умножение следует понимать как умножение в соответствующем конечном поле: или . Мы пишем для q наиболее значимых бит битовой строки . Протокол AUTH показан ниже.

Protocol AUTH













В полной версии статьи [6] мы показываем как проиллюстрировать строительные блоки (из-за ограничений пространства мы включили только части, иллюстрирующие MAC в настоящей версии, в дополнении A). для получения схемы с разумными параметрами. В этом процессе мы используем технику из [1], кроме того мы заменяем сильные экстракторы, которые являются частями предугадывающего экстрактора, что доказало безопасность от квантовой сторонней информации ([12]).
В зависимости от параметров конкретизации AUTH И количества бит , может быть выгодно, или даже необходимо, аутенцифицировать хэш тройки , вместо аутентификации самой тройки. В этом случае, мы позволим Алисе выбрать малый источник для почти универсальной хэш-функции и применить к этому источнику, и хэш тройки (по отношению к этому источнику). Мы на самом деле воспользуемся предложенной модификацией для установки AUTH.
Перед тем, как перейти к доказательству безопасности AUTH, мы разрешим рекурсивную проблему, полученную из аутентификации источника , использовавшегося для получения аутентификационного ключа .

Лемма 2.

Рассматривая MAC как -предугадывающе-безопасный для любого . Пусть - произвольные случайные величины и E - квантовое состояние, и пусть упорядоченная пара удовлетворяет предугадывающему свойству с параметром , обусловленным и событие . Тогда,
Доказательство. Мы ставим условия на и и предположим, что . Потому как может зависеть от , обуславливаясь фиксированными значениями, последнее предполагает, что не обязательно -предугадывающее. Пусть будет максимальным на следующего выражения

Следовательно, из определения 6, есть -предыгадывающий обусловленный на и сообщениях . Заметим, что усреднение над результируется в

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





Это завершает доказательство.

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

В этом разделе мы покажем, что протокол AUTH удовлетворяет свойствам, приведённым в Определении 5. Для начала отметим, что легко увидеть из описания протокола, что свойство корректности соблюдено, и мы не будем рассматривать это в дальнейшем.
На протяжении доказательств, пусть - квантовая сторонняя информация Евы до выполнения AUTH. , где , представляет квантовую сторону информации Евы после i-го раунда коммуникации, и следовательно включает связанные случайные величины до этого раунда. представляет информацию на стороне Евы после выполнения AUTH, включая решение Боба ( не включает это решение). В дальнейшем, как в секции 3.1, мы пишем и т.д. для соответствующих значений .

Теорема 1. (Безопасность)

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

Отметим, что это выражение сводится к простому выражению Теоремы 1 доказательства безопасности, потому что в этом случае (по определению 5), которое предполагает, что .
Доказательство. Рассмотрим этап протокола после второго раунда коммуникации. Полагаем, что и назначены злоумышленником (это делает её только сильнее). Пусть и
Из цепного правила, и по использованию в дальнейшем и , отбираемых независимо, следует, что

По предполагаемым параметрам, т.е. следует, что -предугадывающий, определённый на Для того, чтобы применить лемму 2, мы дополнительно ставим условие Лемма 1 гарантирует, что растёт не более чем на фактор Теперь применим лемму 2 и получим:

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




Наконец, имеем



Теорема 2. (Секретность долгосрочного ключа)

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

Случай нечёткости. До этого момента мы предполагали сценарий, в котором Алиса и Боб имеют общие идентичные копии сессионного ключа . Теперь мы рассмотрим «нечёткий» случай, в котором Алиса и Боб сожержат ключи, которые близки по значению в некотором смысле, но не обязательно идентичны. Такой тип сценария обычно возникает, когда Алиса и Боб получают свои сессионные ключи с присутствием шума. Для простоты и с нашим приложением (Секция 6) в уме, мы используем расстояние Хэмминга для измерения близости ключей.
Рассмотрим следующий простой подход. Пусть ключ Боба называется . Перед выполнением процедуры аутентификации, Боб посылает некую корректирующую ошибки информацию (например, синдром по отношению к некоему коду, исправляющему ошибки) Алисе, чтобы она могла скорректировать ошибки в своём ключе , или наоборот. К сожалению, Ева может модифицировать эту корректировочную информацию так, что Алиса не сможет восстановить правильно исходный ключ, и в этом случае работа нашей схемы не гарантируется. Тем не менее, как доказано в [1], этот подход работает в случае, если один из них использует переменное извлечение на основе предугадывающих экстракторов. Для работы этого решения необходимо, чтобы оба ключа и имели достаточную min-энтропию, и чтобы Боб посылал корректировочную информацию Алисе (т.е информация должна быть послана в том же направлении, что и ядро экстрактора). Тоже самое выполняется в том случае, когда Еве позволяется иметь квантовую стороннюю информацию.
Тонкость заключается в том, что корректирующая информация не должна пропускать информации о , чтобы соблюсти свойство секретности. Подробно эта проблема раскрыта в [13], и обобщена для квантового случая в [14]. Заметим, что для верхней границы min-энтропии потери в и из-за коррекции ошибок: по правилу цепи это самый большой размер в битах корректирующей ошибки информации.

Применение: парольная идентификация в ограниченной квантовой модели хранения

Дамгардом и другими в [5] предложено две схемы парольной идентификации: и . Первый по-настоящему имеет парольную основу, но не защищает от атаки man-in-the-middle, в то время как второй обеспечивает безопасность в таком случа, но не действительно парольный, потому что «Пользователь» U и «Сервер» S обязаны иметь секретный высоко-энтропийный ключ. Мы набросаем, как наша аутентификационная схема приводит к к действительно-парольной схеме идентификации в ограниченной квантовой модели хранения, защищённой от атак man-in-the-middle.
Идея и следующая. U посылает n BB84 квантовых бит

S, который измеряет их в базисе где есть обычный пароль и c — подходящий код с большим кодовым расстоянием . Затем, U объявляет базис , используемый для BB84 кубит. Это позволяет U и S вычислить строку , состоящую из всех позиций с , т.е где U и S использовали одинаковый базис. Затем, U необходимо убедить S в том, что он действительно знает (ту же самую) строку . Дамгард и др. показали способ сделать это, который гарантирует отсутствие утечки информации о для потенциального злоумышленника U или S. Защита от злоумышленника U необходимо безоговорочно, в то время как защита от злоумышленника S осуществляется в ограниченной квантовой модели хранения (где S по предположению имеет ограниченное квантовое хранилище). В основе последнего доказательства — нижняя граница min-энтропии с точки зрения сервера-злоумышленника, что следует из неопределённого отношения [15].
Чтобы защитить протокол от атак man-in-the-middle, можно защитить (классическую и квантовую) коммуникацию от подделки. В попытке обнаружить подмену передаваемых кубитов, U и S выбирают образец кубитов и убеждаются, что в нём не было подмены. В попытке обнаружить подмену в классической коммуникации, Дамгард и др. предлагают использовать так назвываемый экстрактор MAC. Такой MAC проще, чем обычный информационно-теоретический MAC, и требует ключа с высокой энтропией, но также является экстрактором. Способ, которым этот экстрактор MAC используется в позволяет использовать высоко-энтропийный ключ повторно.

Наш подход

Наш подход к достижению защищённости от атак man-in-the-middle без ключа с высокой энтропией теперь просто проводит аутентификацию классической коммуникации с применением протокола AUTH Секции 4, используя как слабый сессионный ключ. Наше свойство секретности гарантирует, что такая аутентификация не допускает утечки информации о пароле . Подчёркиваем, что прошлые схемы аутентификации на основе слабых ключей будут (потенциально) пропускать информацию об .
Существует пара тонкостей, о которых следует позаботиться в нашем подходе. Если квантовая коммуникация содержит шум (как бывает в реалистичных сценариях), или если злоумышленник man-in-the-middle модифицирует некоторые кубиты (довольно небольшое количество, чтобы не обнаружить себя), то версии для U и S не идентичны. Поэтому мы имеем нечёткий случай. Как обсуждалось в Секции 6, это не является проблемой, как только корректирующая ошибки информация отправляется от Боба к Алисе, т.е от U к S в условиях идентификации, и как только мы имеем нижние границы версий U и S (с точки зрения злоумышленника). О первом требовании легко позаботиться, мы просто отправляем коррекцию ошибок в нужном направлении; от S к U. В попытке гарантировать, что обе версии имеют соответствующую min-энтропию (анализ Дамгарда и др. только гарантирует min-энтропию U), мы модифицируем схему следующим образом. Вместо того, чтобы измерять BB84 кубиты в базисе , S измеряет ихх в случайном базисе и объявляет разницу . Затем, U и S обновляют код c сдвигая каждое кодовое слово на r так, что по отношению к новому коду c', S имеет измеренные BB84 кубиты в базисе . Этот трюк также был использован в [16] , но по другой причине, и не оказал существенного влияния на анализ схемы. Тем не менее, как мы покажем ниже, это заставляет нас согласиться с тем, что версия S имеет ограниченную снизу min-энтропию, и потому аутентификация классических сообщений гарантированно работает, что обеспечивает безопасность парольной идентификационной схемы.
Напомним, что защита от злоумышленного U или S требует, чтобы злоумышленная группировка могла исключить хотя бы одну возможность пароля (за одно выполнение атаки); действительно, это лучшее, на что мы можем надеяться, потому что злоумышленники всегда могут попытаться угадать . Для парольной man-in-the-middle защиты мы требуем, чтобы злоумышленник мог исключить не более двух возможностей пароля. И снова это лучшее, на что мы можем надеяться, потому что в атаке man-in-the-middle атакующий может (но не обязан) индивидуально атаковать U и S, и в обеих атаках может попытаться угадать . Такую безопасность мы достигаем с помощью нашей схемы.
Вначале наметим нашу схему ниже, а потом будем утверждать (неформально), почему она защищена. Отсюда, мы будем использовать заглавные буквы для случайных величин, которые описывают значения и т.д. в чистом исполнении протокола. это следует из анализа в [5] (который до сих пор применяется для сдвига кодового слова, описанного выше) и что существует (независимое от W) такое, что если , существует min-энтропия в ,ограниченная до , с точки зрения Евы.
Для рассуждаем следующим образом. Рассмотрим две возможности для W: и . Фокусируемся на позициях, где (которые будут теми же позициями, если c заменить на c'). Теперь фиксируем ; следующее будет выполняться для любого (выбранного пользователем). Из соотношения неопределённостей [15] следует (приблизительно):
,
где

 - распределение 

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

1. U выбирет и посылает n-кубитное состояние к S.
2. S выбирает и измеряет в базисе . Пусть x является исходом. S вычисляет и пересылает U . Мы определяем и
3. U посылает и S.
4. S выбирает и случайное подмножество размерности , вычисляет и и посылает пользвателю U.
5. U послает , восстанавливает из с помощью s, и посылает test и S. 6. Используя слабый ключ , U аутентифицирует все передаваемые классические сообщения,т.е используя S по отношению к S.
7. S принимает тогда, и только тогда, когда (1) AUTH принимает, (2) test совпадает с test' независимо от того, совпали ли базисы (до некоего уровня шума), и (3)


Как дополнительное условие Евы квантовой системы E, мы принимаем хранилище, ограниченное q и делаем вывод, что . Так как F выбирается независимо, мы можем наложить дополнительное условие на F.
Пусть будет (возможно) модифицированной злоумышленником версией , посланной на шаге 3. Злоумышленник получает как квантовое измерение , мы можем наложить условие на вместо без понижения ограничения. Теперь, из-а условий на мы можем заменить парой в min-энтропийной границе, где состоит из позиций таких, что и упрощённого . (Энтропия больше не может уменьшиться, не ограничиваясь в позициях Поэтому,
,
и потому, в частности
.
Это выполняется любых , так что из энтропии, разделяющей лемму [5], следует существование (независимого от W), так что если , существует ограниченная снизу на min-энтропия в , с точки зрения Евы, после шага 3. Заметим, что в точке, где используется для запуска протокола AUTH, Ева получит дополнительную информацию (в шаге 4 и 5). Тем не менее, нетрудно ограничить сверху потери min-энтропии в согласно этой дополнительной информации, так что с правильным выбором параметров ещё существует ограниченная снизу минимальная энтропия.
Мы согласились, что и , или и в терминологии секции 6, имеют ограниченную снизу минимальную энтропию, с точки зрения Евы. Более того, в нашей описанной выше схеме иденификации, S посылает корректирующую ошибки информацию к U. Вместе это гарантирует защищённость AUTH когда применяется нечёткий случай. Также в оригинальном протоколе корректирующая информация посылается в другом направлении, инверсия этого направления допустима потому, что аутентификация обеждает, что ни одно сообщение не было изменено.
Сейчас безопасность следует из анализа [5] (и также из [16], затрагивающего смещающихся кодовых слов).

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

Мы бы хотели поблагодарить Кшиштофа Пьетржака за интересные дискуссии и ценные комментарии касательно этой работы.

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

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

Примечания

Литература

  1. 1,0 1,1 1,2 1,3 Dodis, Y., Wichs, D.: Non-malleable extractors and symmetric key cryptography from weak secrets. In: STOC ’09: Proceedings of the 41st annual ACM symposium on theory of computing. pp. 601–610 (2009)
  2. 2,0 2,1 Chandran, N., Kanukurthi, B., Ostrovsky, R., Reyzin, L.: Privacy amplification with asymptotically optimal entropy loss. In: STOC ’10: Proceedings of the 42nd ACM symposium on theory of computing. pp. 785–794. ACM (2010)
  3. Renner, R., Wolf, S.: The exact price for unconditionally secure asymmetric cryptography. In: Cachin, C., Camenisch, J. (eds.) Advances in Cryptology - EUROCRYPT ’04, Lecture Notes in Computer Science, vol. 3027, pp. 109–125. Springer (2004)
  4. Kanukurthi, B., Reyzin, L.: Key agreement from close secrets over unsecured channels. In: Joux, A. (ed.) Advances in Cryptology - EUROCRYPT ’09, Lecture Notes in Computer Science, vol. 5479, pp. 206–223. Springer (2009)
  5. 5,0 5,1 5,2 5,3 5,4 Damg˚ard, I., Fehr, S., Salvail, L., Schaffner, C.: Secure identification and QKD in the bounded-quantum-storage model. In: Advances in Cryptology - CRYPTO ’07. Lecture Notes in Computer Science, vol. 4622, pp. 342–359. Springer (2007)
  6. 6,0 6,1 Bouman, N.J., Fehr, S.: Secure authentication from a weak key, without leaking information (full version). Cryptology ePrint Archive (2011), http://eprint.iacr.org/2011/034
  7. Renner, R.: Security of Quantum Key Distribution. Ph.D. thesis, ETH Z¨urich (Switzerland) (2005)
  8. K¨onig, R., Renner, R., Schaffner, C.: The operational meaning of min- and maxentropy. IEEE Transactions on Information Theory 55(9), 4337–4347 (2009)
  9. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)
  10. Renner, R., K¨onig, R.: Universally composable privacy amplification against quantum adversaries. In: Kilian, J. (ed.) Theory of Cryptography - TCC ’05, Lecture Notes in Computer Science, vol. 3378, pp. 407–425. Springer (2005)
  11. Van De Graaf, J.: Towards a formal definition of security for quantum protocols. Ph.D. thesis, Univ. de Montreal (Quebec, Canada) (1998)
  12. De, A., Portmann, C., Vidick, T., Renner, R.: Trevisan’s extractor in the presence of quantum side information. arXiv (2009), http://arxiv.org/abs/0912.5514
  13. Dodis, Y., Smith, A.: Correcting errors without leaking partial information. In: STOC ’05: Proceedings of the 37th annual ACM symposium on theory of computing. pp. 654–663. ACM (2005)
  14. Fehr, S., Schaffner, C.: Randomness extraction via delta-biased masking in the presence of a quantum attacker. In: Theory of Cryptography - TCC ’08. pp. 465– 481. Lecture Notes in Computer Science (2008)
  15. 15,0 15,1 Damg˚ard, I.B., Fehr, S., Renner, R., Salvail, L., Schaffner, C.: A tight high-order entropic quantum uncertainty relation with applications. In: Advances in Cryptology - CRYPTO ’07. pp. 360–378. Lecture Notes in Computer Science, Springer (2007)
  16. 16,0 16,1 Damg˚ard, I., Fehr, S., Lunemann, C., Salvail, L., Schaffner, C.: Improving the security of quantum protocols via commit-and-open. In: Advances in Cryptology - CRYPTO ’09. pp. 408–427. Lecture Notes in Computer Science, Springer (2009)