Построение секретных ключей для каналов с шумами

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:37, 20 декабря 2015.
Secret Keys from Channel Noise
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Hadi Ahmadi[@: 1] and
Reihaneh Safavi-Naini[@: 2]
Опубликован 2010 г.
Сайт Hadi Ahmadi's webpage
Перевели Nikolay Morozov
Год перевода 2015 г.
Скачать оригинал


Аннотация. Мы изучаем вопрос о безусловной безопасности Создания Секретного Ключа (SKE), когда Алиса и Боб объединены двумя каналами с шумами, которые прослушивает Ева. Мы рассмотрим случай, когда Алиса и Боб не имеют никаких источников случайности в своем распоряжении. Мы начинаем с обсуждения особых случаев, представляющих интерес, в которых SKE невозможно, а затем представим простую конструкцию SKE для двоичного симметричного канала, достигающую некоторую степень секретного ключа. Далее мы сосредоточимся на возможностях Секретного Ключа (SK) и обозначим для них нижнюю и верхнюю границы. Мы доказываем нижнюю границу, вводя некоторые цикличные SKE протоколы, называемые основными. Основной протокол состоит из стадии инициализации и повторения двухэтапного SKE подпротокола, который называется базовым протоколом. Мы покажем, что границы совпадают, когда каналы не дают утечки информации к противнику. Мы применяем результаты для случая, когда участники соединены двоичными симметричными каналами.

Введение

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

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

Физические каналы связи обладают шумами и могут рассматриваться как потенциальные источники случайности. Новаторская работа Винера [2] показала, что шумы в каналах могут быть использованы для обеспечения полной безопасности при передаче сообщений. Эта работа начала длинную череду исследований, использующих шумы для построения криптографических примитивов. Она разделяет предположение Крепо и Килиана [3] о том, что "Шум, с другой стороны, порождает беспорядок, неопределенность и путаницу. Таким образом, он является естественным помощником криптографа.

Работа Винера и, насколько нам известно, все криптографические системы, использующие каналы с шумами как источник, также предполагают доступ к источникам исходной случайности. В данной работе мы начинаем изучение криптографических систем без применения этого предположения. Мы рассмотрим случай, когда алгоритмы имеют фиксированные открытые параметры, такие как ID, и единственным источником случайности будет шум в каналах. Может возникнуть вопрос, существует ли в таких условиях определенный криптографический примитив, и, если они существуют, то представляет ли он практический интерес. Мы сфокусируемся на основной задаче Создания Секретного Ключа (SKE) при наличии пассивного противника и сформулируем следующий вопрос:


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

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

Наша работа

Мы сосредоточимся на Вопросе 1 и изучим SKE для пары независимых Дискретных Каналов Передачи без Памяти (DMBC). Мы называем этот подход 2DMBC. SKE для этого подхода было изучено в работе [4], однако, опять же, предполагалось, что Алиса и Боб имеют доступ к источнику исходной случайности. Мы же предполагаем, что Алиса и Боб имеют фиксированные строки, и соответственно. Мы также предполагаем наличие полнодуплексной модели коммуникации, где при каждой передаче сообщения, Алиса и Боб отправляют последовательности одинаковой длины. Данная модель передачи сообщений используется для упрощения изложения наших результатов; результаты могут быть легко адаптированы для полудуплексных каналов, где при каждой передаче сообщения либо Алиса, либо Боб посылают последовательность.

Невозможность получения результатов: Вне всякого сомнения, SKE без исходной случайности невозможно, если каналы между сторонами не имеют шумов. В Разделе 3, мы обсудим частные случаи 2DMBC подхода, где SKE невозможно, несмотря на наличие шумов в системе. Эти особые случаи включают (1) одностороннюю связь, (2) один DMBC без шумов, и (3) другой DMBC имеет шумы, но возвращает два идентичных результата. Отметим, что возможность SKE в этих случаях уже была доказана [5][6][7] при предположении, что исходная случайность доступна для обеих сторон.

Построение SKE: Мы даем положительный ответ на Вопрос 1, рассматривая сценарий, где каждый DMBC состоит из двух независимых Симметричных Двоичных Каналов (BSC). Мы предлагаем двухэтапное SKE построение, которое использует три простых примитива, генератор случайности фон Неймана, двоичный код, исправляющий ошибки и универсальную хэш-функцию. Протокол работает следующим образом. На 1-ой стадии Алиса посылает постоянную (нулевую) последовательность Бобу; Боб получает строку с шумами и использует генератор Неймана для получения равномерной случайной двоичной последовательности из этой строки. На 2-ой стадии Боб разбивает последовательность на две подпоследовательности, кодирует их по-отдельности и посылает Алисе кодовые слова. Алиса декодирует полученную последовательность, чтобы найти обе подпоследовательности. В заключение, Алиса и Боб осуществляют хеширование для подпоследовательностей для получения безопасного секретного ключа.

Мощность SK: Мы формализуем 2DMBC модель и сосредоточимся на общем описании SKE протокола в 2DMBC модели. Мы определяем мощность Секретного Ключа (SK) в модели 2DMBC как наивысший уровень SK, достижимый SKE протоколами. Это приводит к следующему вопросу:


Вопрос 2. Что такое мощность SK для заданной 2DMBC модели?
Для ответа на Вопрос 2, мы определяем нижнюю и верхнюю границы мощности SK для 2DMBC модели. Докажем нижнюю границу, показав, что существует конструкция SKE для ее достижения. Мы опишем циклический SKE протокол, называемый основным протоколом, который состоит из стадии инициализации и повторяющегося использования двухэтапного протокола, называемого базовым.

На стадии инициализации загружается главный протокол, который предоставляет Алисе и Бобу некоторые части "независимой случайности". Под независимой случайностью мы подразумеваем случайную величину, не зависящую от всех переменных, собранных другими сторонами. Случайность извлекается из шумов в каналах и требуется для выполнения итерации базового протокола. Каждая итерация использует новые случайности, полученные в предыдущей итерации, и одновременно служит двум целям: (1) предоставить новые независимые случайности Алисе и Бобу (для следующей итерации), и (2) предоставить часть секретного ключа. Для достижения этих двух целей базовый протокол использует два новых детерминированных примитива, которые мы обозначим как безопасный блочный код и безопасное распределение, соответственно. Каждая итерация основного протокола дает фиксированную часть ключа. Однако, во время стадии инициализации не создается ни один бит секретного ключа. Так как использование каналов на стадии инициализации может быть амортизировано в течение нескольких последовательных вызовов базового протокола, размер SK стремится к одному из базовых исполнений протокола. По сравнению с другими возможными способами создания ключа (См. Раздел 1.2), протокол, описанный в данной статье, достигает наибольшего значения, что приводит к более жесткой нижней границе можности SK.

Нижняя граница показывает, что положительные значения SK могут быть достигнуты, когда оба DMBC канала связаны с легальным сторонами. Интересно то, что это показывает, что это условие, хоть и является достаточным, не необходимо, и существуют случаи, когда оба DMBC канала доступны Еве, но при этом можно установить безопасный общий ключ. Мы также определяем верхнюю границу для SK и показываем, что нижняя и верхняя границы совпадают в том случае, если каналы не дают утечки информация противнику. Это соответствует общей проблеме генерации случайностей для независимых каналов с шумами, изученной в работе [8], где была получена общая мощность случайности.

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

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

Доказательство для нижней границы, приведенное в данной работе, использует экзистенциальный аргумент. Тем не менее, попытки работать эффективно при оптимальных примитивах для безопасного распределения и безопасного блочного кода могут быть непосредственно применены к главному SKE протоколу для достижения значений SK ключа, близких к нижней границе. Это интересное направление для будущих исследований, похожих на работу [9]' , где наблюдаются попытки применения теоретических результатов для SKE из работы [2][6] на практике.

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

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

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

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

Использование шумов в каналах для обеспечения безопасности было впервые рассмотрено Винером [2], который предложил альтернативу модели безопасных коммуникаций Шеннона [10]. Работа Винера вызвала длинную череду исследований по использованию шумов в каналах для построения теоретически информационно безопасных криптографических примитивов, включающих построение SKE [11][5][12][6][13], Неосознанную Передачу (OT) [3], и BC схемы [14]. Однако, в этих работах предполагается наличие доступа к исходной случайности, и удаление этого предположения потребует пересмотра результатов и проверки существования примитивов.

Маурер [6], одновременно с Алсведе и Сзизаром [11], изучал проблемы согласования ключей в открытых каналах, когда Алиса и Боб имеют исходную коррелированную случайность и нижнюю и верхнюю границы значения мощности SK. Согласование ключей с использованием коррелированных случайностей и односторонних каналов с шумами обсуждается в работах [12][13].

Следующие две работы тесно связаны с данной статьей, хотя ни одна из них нет решения проблемы. Венкатесан и Анантхарам[8] рассматривали генерацию общей случайности для пары независимых каналов и получили общую мощность случайности. Авторы отметили, что их результаты не могут быть применены к случаю, когда каналы прослушиваются Евой; в данной статье этот случай также рассматривается. В работе [4], мы рассмотрели построение SKE для 2DMBC модели и условия ограничения мощности SK. Эта работа, однако, предполагает наличие свободной независимой случайности, без которой доказательство не будет действительным. При отсутствии исходной случайности, можно конечно использовать результаты работы [4] для последующей разработки протокола. Алиса и Боб сначала осуществляют стадию инициализации, чтобы получить необходимое количество независимых случайностей. Затем они запускают протокол из [4], чтобы получить секретный ключ. По сравнению с этим, наш основной протокол через итерации увеличивает значение SK в два раза. Новизна базового протокола заключается в том, что он сочетает в себе как задачу вывода безопасного ключа, так и генерацию случайностей.

Обозначения

Мы используем каллиграфические буквы , заглавные буквы , и строчные буквы , чтобы обозначить конечные алфавиты, случайные переменные , и их реализации над множествами, соответственно. является множеством всех последовательностей длины n (так называемых n-последовательностей) с элементами из обозначает случайную n-последовательность в . В случае, если не существует путаницы относительно длины, мы используем X для обозначения случайной последовательности и x для обозначения реализации в . При описании циклических протоколов, мы можем использовать или для обозначения случайной n-последовательности, отправленной, полученной или созданной на этапе r. "" обозначает объединение двух последовательностей. Для значения х, мы используем , чтобы обозначить , а для целого числа N, мы используем [N], чтобы показать множество {1, 2,...,N}. Все логарифмы берутся по основанию 2, а для , обозначает двоичную энтропию функции.

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

Раздел 2 описывает SKE построение для 2DMBC модели и предоставляет определения для безопасности. В разделе 3, мы предоставляем результаты неприменимости и приводим простое SKE построение для BSC модели. В разделе 4 приведены основные результаты для значений SK ключей. В разделе 5 мы описываем основной протокол, достигающий нижней границы. Раздел 6 исследует результаты SKE построения для BSC случая и раздел 7 дает заключения по работе.

Постановка проблемы

Суть 2DMBC модели показана на рис. 1(а). Существует прямой DMBC канал от Алисы к Бобу и Еве, обозначаемый как , и обратный DMBC канал от Боба к Алисе и Еве, обозначаемый как . Стороны имеют детерминированные системы расчетов. 


Рис. 1. 2DMBC модель (а) в общем и (b) в случае независимых BSC. 


Чтобы установить секретный ключ, Алиса и Боб следуют SKE протоколу с t стадиями связи, где на каждой стадии r, каждый канал используется раз. Протокол определяется как последовательность детерминированных пар функций , а пара таких (детерминированных) функций вывода ключей , что

, (1) , (2)

где обозначает символ ошибки и является общим числом используемых каналов.

Протокол принимает на вход пару постоянных и известных последовательностей. На стадии связи r, Алиса и Боб отправляют nr –последовательности и получают и , соответственно. Ева получает пару  Входные последовательности рассчитываются следующим образом:

где являются состояниями для Алисы, Боба и Евы в конце стадии r-1, т.е.

, and (4)

Мы не включили постоянные и детерминированные функции, которые применяются для переменных в состояниях, так как они не содержат никакой информации (случайности). После выполнения t стадий, Алиса и Боб рассчитывают свои секретные ключи, соответственно, как 

, and (5)

Где будет состоянием Евы в конце протокола.
TemplateDifinitionIcon.svg Определение « Определение 1»
Для и SKE протокол Π является -безопасным, если существует такая случайная величина , что выполняются следующие требования

Случайность: (6a)

Случайность: (6b)

Случайность: (6c)

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

SKE в особых случаях 2DMBC модели

Неосуществимость результатов в особых случаях

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

Односторонняя связь: Рассмотрим случай, когда один из DMBC каналов, скажем, обратный, всегда возвращает постоянные значения. Это подразумевает одностороннюю связь через прямой канал. Независимо от протокола, Алиса никогда не будет иметь ни одного бита случайности для своего состояния, и, без случайности, она не сможет получить секретный ключ. Отметим, что это особый случай по существу является односторонним DMBC каналом Сцизара и Кернера [5], с той лишь разницей, что сторонам не предоставляется исходная случайность.

Один открытый канал без шумов: Предположим, что без потери общности обратный DMBC канал обладает данным свойством. Для любого SKE протокола, описанного в Разделе 2, мы получаем для каждого этапа r. Это говорит о том, что в целом, состояние Евы включает в себя состояние Алисы (см. (4)). Ева может просто использовать функцию вывода ключа Алисы для своего состояния, чтобы вычислить . Это свойство подразумевает наличие положительных значений SK, когда стороны имеют доступ к исходной случайности [6].

Один канал имеет шумы, но возвращает два идентичных значения: Предположим, что это свойство выполняется для обратного DMBC канала. В этом случае может отличаться от возвращаемых значений, и мы имеем только Этого достаточно, чтобы утверждать, что состояния Алисы и Бобы идентичны,откуда следует и невыполнимость SKE алгоритма.

SKE протокол для двоичных симметричных каналов

Предположим, что 2DMBC модель состоит из четырех независимых двоичных симметричных каналов (BSC), как показано на рис. 1(b). Основные каналы имеют вероятность ошибки бита p1, в то время как оба канала Евы имеют вероятность ошибки p2. Ниже мы опишем двухэтапное построение SKE, использующее введенные примитивы.

Генератор случайности фон Неймана [15]: Этот генератор получает на вход двоичную последовательность четной длины и возвращает последовательность переменной длины, имеющую равномерное распределение. Для входной последовательности Бернулли четной длины m, где , генератор фон Неймана делит последовательность на m/2 пары битов и использует следующую систему маркировки каждой пары

где означает отсутствие выхода. Выходная последовательность является объединением маркированных битов. Легко заметить, что генератор вычислительно эффективен и выходные биты независимо и равномерно распределены.

Хотя генератор фон Неймана не возвращает последовательность фиксированной длины, он может быть использован для создания функции , производящей l-битные однородные строки из m-битной последовательности Бернулли. Функция Ext запускает генератор фон Неймана для m-битной последовательности Y. Если длина выходной последовательности меньше l, он выводит в противном случае он выводит первые l бит из выходной последовательности. Вероятность того, что Ext выводит для m-битной последовательности Бернулли с определяется как:

(7)

Канальный код, исправляющий бинарные ошибки (n,k): Обозначим функции кодирования и декодирования как , соответственно. Существуют эффективные коды , которые исправляют до ошибочных битов. При использовании для BSC модели с вероятностью ошибки р, вероятность успешного декодирования ошибки для таких кодов будет определяться как:

(8)

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

где выводит первые s бит из c.x, и результат выводится в форме многочлена из . Хеш-функции являются эффективными по времени и по

памяти.

Описание протокола: Используя описанные примитивы, SKE протокол действует следующим образом. Алиса посылает свою постоянную последовательность через прямой DMBC канал. Боб и Ева получают m-последовательности и (где m четное). Боб рассматривает их в качестве m-битной последовательности Бернулли с и находит . Если , выдается  ; в противном случае Боб разбивает l-битную U на две самостоятельные и равномерные k-битные последовательности и , где k = l/2. Он вычисляет n-битные кодовые слова и и отправляет их по обратному DMBC каналу, где Алиса и Ева получают и , соответственно. Алиса вычисляет k-последовательности и . Ошибка имеет место, когда . Далее, Алиса и Боб используют универсальное хеширование для усиления конфиденциальности, то есть для получения ключей, защищенных от Евы. Секретным ключом будет , где . Боб вычисляет , а Алиса , где .

Приведенный выше протокол обеспечивает Алисе и Бобу s равномерно случайных битов для ключа. Сложность создания ключа рассчитывается как число бит для ключа, деленное на количество используемых каналов, т.е. . Для экономии места мы опускаем описание для надежности и безопасности данного построения. Более полный анализ приведен в полной версии [3]. В таблице 1 приведены параметры SKE построения для BSC модели при и , для длины ключа s = 100 и различных значений параметра безопасности . Согласно этой таблице, достижимый размер SK при построении составляет около бит на используемый канал.

Таблица 1. Параметры SKE для при .
10-1 404 300 600 5230 0,0166
10-2 458 330 660 5430 0,0158
10-3 508 358 716 5590 0,0151
10-4 560 388 776 5730 0,0146

Замечание 1. Наличие модели двусторонней коммуникации позволяет Алисе и Бобу параллельно запустить протокол в обратном направлении. Это удвоит размер SK, получаемый данным построением, т.е. .

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

Результаты мощности SK

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

TemplateTheoremIcon.svg Теорема Теорема 1. Значение SK ключа ограниченно снизу величиной

(9)

где

, (10)

, (11)

, (12)

, (13)

такие что

(14)

(15)

Доказательство
Для доказательства см. Разделы 5 и [3, Приложение А].

Нижняя граница (9) достигается за счет, так называемого, основного протокола, состоящего из этапа инициализации и следующего за ним этапа итерации базового протокола. Двусторонние каналы позволяют Алисе и Бобу параллельно запустить две итерации базового протокола. За счет этих двух итераций достигаются граничные значения ключей и , соответственно. Значения, достигаемые на втором этапе базового протокола, зависят от DMBC параметров (то есть и ), в то время, как на первом этапе значения зависят от "обратных" DMBC параметров (то есть, и ). Реальным значением μ является разница между числом каналов, используемых на первом и на втором этапах . Реальные значения γ1 и γ2 должны ограничивать количество достижимых значений ключей в зависимости от функции случайности, полученной из шума в каналах. Когда оба DMBC канала, открытые для Алисы и Боба, то есть и , положительны, и будут положительными при простом задании . Это подразумевает положительное значение мощности SK. Когда каналы открыты для Евы, нижняя граница может оставаться положительной, если обратный DMBC канал открыт для Алисы и Боба. Изучение нижней границы для BSC модели в Разделе 6 ясно показывает существование положительных SK в последнем случае (см. рис. 2).


TemplateTheoremIcon.svg Теорема Теорема 2. Значение мощности SK ограниченно сверху величиной:

,где (16)

, (17)

, (18)

Доказательство
Для доказательства см. [3, Приложение В].

Теорема 3 показывает, что обе оценки совпадают, когда оба DMBC канала не дают утечки информации. Полученное значение соответствует общему значению мощности случайности для пары независимых Дискретных Каналов без Памяти (DMC), приведенной в [8].


TemplateTheoremIcon.svg Теорема Теорема 3
Когда DMBC каналы не дают утечки информации к Еве, границы совпадают и значение мощности SK равно

(19)

Доказательство
Для доказательства см. [3, Приложение C].


Основной SKE протокол: достижение нижней границы

Мы отметили, что граница в теореме 1 достигается за счет основного протокола. Основной протокол содержит этапов и не имеет никакой исходной случайности. Протокол начинается с этапа инициализации (этап 0), обеспечивающего Алису и Боба некоторой независимой случайностью. За этим этапом следуют t итераций подпротоколов, называемых базовыми. Базовый протокол использует независимую случайность от Алисы и Боба и возвращает им часть секретного ключа и некоторые новые независимые случайности. Независимая случайность, полученная в итерациях (соотв. этапу 0) будет использоваться в итерации (соотв. итерации 1). Части секретного ключа объединяются, и получается окончательный секретный ключ. Основной протокол основан на существовании двух примитивов, называемых безопасным равнораспределением и безопасным блочным кодом. Далее мы приводим определения и теоремы для описания существования этих примитивов и описываем основной протокол.

Предварительные определения

TemplateDifinitionIcon.svg Определение «Определение 3.»
Для распределения вероятностей на множестве последовательность будет иметь e-тип, если , где .
TemplateDifinitionIcon.svg Определение «Определение 4.»
Блочный кодов для представляет собой такое множество , что принадлежит , и .

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

TemplateDifinitionIcon.svg Определение «Определение 5.»
Безопасный блочный код для состоит из блочного кода для , как показано выше, перевода в , функции вывода ключей , определяемой как , тогда и только тогда, когда , такой, что если равномерно выбирается из и , тогда .

Хотя приведенное выше определение безопасного блочного кода в качестве примитива является новым в литературе, работы по безопасной передачи сообщений или согласованию ключей для односторонних DMBC каналов [5][2] неявно исследуют существование такого примитива. Результаты работ [5][2] позволяют сделать следующее заключение.

TemplateDifinitionIcon.svg Определение «Лемма 1.»
Для любых и достаточно большого n, существует такой безопасный блочный код для , с кодовыми словами типа e, что и .

Для доказательства см. [18, теорема 2] и [8, утверждение 1].

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

TemplateDifinitionIcon.svg Определение «Лемма 2.»
Для любых , достаточно большого и достаточно больших n существует N (не обязательно различных) таких безопасных блочных кодов для с кодовыми словами типа e , что и  ; причем вероятность, что случайно выбранная последовательность принадлежит хотя бы одному из кодов, составляет, по крайней мере , где .

Для доказательства см. [3, приложение D]

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

TemplateDifinitionIcon.svg Определение «Определение 6.»
Безопасное равнораспределение для по отношению в рамках модели будет равнораспределением для С в рамках модели, а функция вывода случайностей будет определяться как если и если , для и ; кроме того, будет выполнено

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

TemplateDifinitionIcon.svg Определение «Лемма 3.»
Для любых, типичного размера меньше чем , , и достаточно больших n существует такое безопасное равнораспределение для модели, что и выполнено  

, где

Для доказательства см. [3, приложение E].

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

TemplateDifinitionIcon.svg Определение «Определение 7.»
При заданном распределении для мы определяем соответствующий обратный DMBC канал как , где рассчитывается из совместного распределения .

Описание основного протокола

Пусть и выбраны так, что условия (14) и (15) удовлетворены. Тогда условия можно перефразировать как

, , (20)

, , (21)

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

Определим:

, , ,

, , (22)

.

, , ,

, , (23)

.

Каждая итерация двухэтапного базового протокола использует 2DMBC канал раз в первом этапе и раз во втором; то есть в общей сложности . На втором этапе Алиса (соотв. Боб) посылает две последовательности длины и (соотв. и ), где и, 

, (24)

, (25)

C использованием указанных величин, мы определяем:

, ,

, ,

, (26)

, , ,

,

, ,

, ,

, (27)

, , ,

,

Рассматривая (22) - (26), можно заметить, что и . Пусть множество будет получено независимым выбором последовательностей в . По определению выполнено . Пусть Алиса и Боб имеют два фиксированных открытых значения и и две фиксированные открытые последовательности и , соответственно. Пусть и будут произвольными биективными отображениями.

Инверсный прямой канал и инверсный обратный канал задаются в соответствии с определением 7. Задав и , и используя леммы 1, 2 и 3, мы приходим к следующему:

  • Для инверсного прямого DMBC канала существует таких безопасных блочный кодов с функцией вывода ключей , что случайно выбранная последовательность e типа в имеется по крайней мере в одном из кодов с вероятностью не менее .
  • Для инверсного обратного DMBC канала существует таких безопасных блочных кодов с функцией выводы ключей , что случайно выбранная последовательность e типа в имеется по крайней мере в одном из кодов с вероятностью не менее .
  • Для прямого DMBC канала существует блок безопасных кодов с функцией вывода ключей  ; кроме того, для любого существует безопасное равнораспределение с функцией вывода случайности .
  • Для обратного DMBC канала существует безопасный блочный код с функцией вывода ключей  ; кроме того, для любого существует безопасное равнораспределение с функцией вывода случайности .
  • Для прямого DMBC канала, для существует безопасное равнораспределение с функцией вывода случайности .
  • Для обратного DMBC канала, для существует безопасное равнораспределение с функцией вывода случайности .


Этап инициализации (этап 0): Алиса и Боб посылают постоянных последовательностей и по своим каналам и получают обратно версии с шумами и , соответственно. Ева также получает и . На этом этапе секретный ключ не устанавливается; однако для получения независимой случайности, Алиса и Боб вычисляют и , соответственно. Затем они вычисляют и , где первая и вторая части используются на первом и втором этапах итерации 1, соответственно.


Основной протокол (итерации ): Существует два этапа, и , в которых протокол использует 2DMBC каналы и раз, соответственно. На этапе , Алиса и Боб отправляют и , а получают и , соответственно. Ева также получает и . Алиса находит такие , что , то есть кодовое слово в безопасном блочном коде для обратного DMBC канала; аналогично, Боб получает такие , что . Этап может быть описан следующим образом. Алиса и Боб имеют закодированные и для кодовых слов и ; они посылают их через инверсные DMBC каналы, но не упоминают, какому из блоков они принадлежат. Таким образом, этап в основном используется для отправки идентификаторов блоков, то есть и . Этот этап также используется для отправки частей случайности и и детерминированных последовательностей и .

В начале этапа , Алиса и Боб соответственно вычисляют и следующим образом (заметим, что и )


, and (28)


Следующая задача для функции вывода ключей (в безопасном блочном коде) - это расчет частей ключей и . На этом этапе, Алиса и Боб отправляют последовательностей и и получают и , соответственно. Ева также получает и .

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

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


Во-первых, стороны вычисляют

(29)

(30)


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

Что же касается создания части секретного ключа, Алиса вычисляет и , а Боб в свою очередь вычисляет и . Общая часть секретного ключа в r итерации будет равна . В целом, основной протокол использует 2DMBC каналы раз, чтобы установить . Следуя этому протоколу, Алиса вычисляет , а Боб . В работе [3, приложение. А] мы показываем, что основной протокол удовлетворяет всем трем требованиям, введенным в определении 1, и достигает нижней границы из теоремы 1.

Значение SK для двоичных симметричных каналов

Рассмотрим случай, когда каждый DMBC канал состоит из независимых BSC каналов с вероятностями ошибки p1 и , то есть случай, описанный в разделе 3.2 (см. рис.1 (b)). Исходя из определения (9) для нижней границы в теореме 1, и полагая, что и равномерные двоичные RV, мы определяем нижнюю границу для значения SK ключа потенциала в случае BSC каналов.

, где (31)

(32)

, (33)

В общем случае является неотрицательным вещественным числом. Тем не менее, мы показали в работе [3], что только три выборки для , а именно и , определенными в уравнении (34)) могут привести к нижней границе (31).

и (34)

Другими словами, нижняя граница в (31) упрощается до

(35)

Это позволяет легко рассчитывать нижнюю границу. Следуя определению верхней границы (16) в теореме 2, получаем

, где (36)

(37)

(38)

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

(39)

Рис. 2 показывает две границы, (35) и (39), для различных значений вероятностей и . Рис. 2 (a) иллюстрирует изменения в границах по отношению к при . Границы совпадают при или при . При вся информация, переданная по 2DMBC каналам, доступна Еве и построение SKE невозможно, так что обе границы оказываются равными нулю. Когда , модель не дает утечки информации к Еве, а из теоремы 3 следует, что обе границы совпадают. Рис. 2 (b) показывает изменения двух границ, когда и . Когда основные каналы не имеют шумов или полностью с шумами , две границы совпадают и равны нулю, а построение SKE невозможно. В первом случае не существует случайности в системе, а в последнем не существует надежных связей. Графики показывают также возможность построения SKE, даже если оба DMBC канала открыты для Евы. Это видно на рис. 2 (а) для значений и на рис. 2 (b) при значениях .

В разделе 3.2 мы представили простое построение SKE. Для значений и , схема достигает значения в 3%. Как изображено на рис. 2, две границы для значений SK ключей для этих вероятностей составляют около 45% и 72% соответственно. Это показывает, как построение из раздела 3.2 далеко от оптимально достижимых значений. Как было отмечено ранее, можно повысить производительность протокола с помощью более подходящих примитивов.

Заключение

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

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

  1. Department of Computer Science, University of Calgary, Canada, E-mail: hahmadi@ucalgary.ca
  2. Department of Computer Science, University of Calgary, Canada, E-mail: rei@ucalgary.ca

Примечание

Литература

  1. Dodis, Y., Spencer, J.: On the (non)universality of the one-time pad. In: IEEE Annual Symposium FOCS, pp. 376–388 (2002)
  2. 2,0 2,1 2,2 2,3 2,4 Wyner, A.D.: The wire-tap channel. Bell System Technical Journal 54, 1355–1367 (1975)
  3. 3,0 3,1 Cr ́epeau, C., Kilian, J.: Weakening security assumptions and oblivious transfer. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 2–7. Springer, Heidelberg (1990)
  4. 4,0 4,1 4,2 4,3 Ahmadi, H., Safavi-Naini, R.: Secret key establishment over a pair of indepen- dent broadcast channels. In: International Symposium Information Theory and its Application (2010); Full version on the arXiv preprint server, arXiv:1001.3908
  5. 5,0 5,1 5,2 5,3 5,4 Csisz ́ar, I., K ̈orner, J.: Broadcast channels with confidential messages. IEEE Transaction Information Theory 24, 339–348 (1978)
  6. 6,0 6,1 6,2 6,3 6,4 Maurer, U.: Secret key agreement by public discussion from common information. IEEE Transaction Information Theory 39, 733–742 (1993)
  7. Csisz ́ar, I., Narayan, P.: Common randomness and secret key generation with a helper. IEEE Transaction Information Theory 46, 344–366 (2000)
  8. 8,0 8,1 8,2 Venkatesan, S., Anantharam, V.: The common randomness capacity of a pair of independent discrete memoryless channels. IEEE Transaction Information The- ory 44, 215–224 (1998)
  9. Bloch, M., Barros, J., Rodrigues, M.R.D., McLaughlin, S.W.: Wireless information theoretic security. IEEE Transaction Information Theory 54, 2515–2534 (2008)
  10. Shannon, C.E.: Communication theory of secrecy systems. Bell System Technical Journal 28, 656–715 (1948)
  11. 11,0 11,1 Ahlswede, R., Csisz ́ar, I.: Common randomness in information theory and cryptog- raphy. Part I: secret sharing. IEEE Transaction Information Theory 39, 1121–1132 (1993)
  12. 12,0 12,1 Khisti, A., Diggavi, S., Wornell, G.: Secret key generation with correlated sources and noisy channels. In: IEEE International Symposium Information Theory, pp. 1005–1009 (2008)
  13. 13,0 13,1 Prabhakaran, V., Eswaran, K., Ramchandran, K.: Secrecy via sources and chan- nels - a secret key - secret message rate trade-off region. In: IEEE International Symposium Information Theory, pp. 1010–1014 (2008)
  14. Barros, J., Imai, H., Nascimento, A.C.A., Skludarek, S.: Bit commitment over Gaussian channels. In: IEEE International Symposium Information Theory, pp. 1437–1441 (2006)
  15. von Neumannm, J.: Various techniques used in connection with random digits. National Bureau of Standards Applied Math Series 12, 36–38 (1951)
  16. Carter, J.L., Wegman, M.N.: Universal Classes of Hash Functions. Journal of Computer and System Sciences 18, 143–154 (1979)
  17. Wegman, M.N., Carter, J.L.: New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, vol. 22, pp. 265-279 (1981)