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

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

Введение

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

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

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

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

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

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

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

Невозможность получения результатов: Вне всякого сомнения, 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 в два раза. Новизна базового протокола заключается в том, что он сочетает в себе как задачу вывода безопасного ключа, так и генерацию случайностей.

Мы используем каллиграфические буквы   ( X ) , чтобы обозначить конечные алфавиты, случайные переменные   ( R V ) , и их реализации над множествами, соответственно.   X n является множеством всех последовательностей длины n (так называемых n-последовательностей) с элементами из   X , X n = ( X 1 , X 2 , . . . . , X n ) ∈ X n обозначает случайную n-последовательность в   X n . В случае, если не существует путаницы относительно длины, мы используем X для обозначения случайной последовательности и x для обозначения реализации в   X n . При описании циклических протоколов, мы можем использовать   X n : r для обозначения случайной n-последовательности, отправленной, полученной или созданной на этапе r. "   | | " обозначает объединение двух последовательностей. Для значения х, мы используем   ( x ) + , чтобы обозначить   max ( 0 , x ) , а для целого числа N, мы используем [N], чтобы показать множество . Все логарифмы берутся по основанию 2, а для   0 ⩽ p ⩽ 1 , h ( x ) = − p log ⁡ p − ( 1 − p ) log ⁡ ( 1 − p ) , обозначает двоичную энтропию функции.

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

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

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

Чтобы установить секретный ключ, Алиса и Боб следуют SKE протоколу с t стадиями связи, где на каждой стадии r, каждый канал используется   n r раз. Протокол определяется как последовательность детерминированных пар функций   ( f r , g r ) r = 1 t − 1 , а пара таких (детерминированных) функций вывода ключей   ( ϕ A , ϕ B ) (2)

\delta _=\sum _^n_,\perp > обозначает символ ошибки и   n = δ t − 1 является общим числом используемых каналов.