М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 168
Текст из файла (страница 168)
Напротив, безопасность криптографии с открытым ключом (приложение 5) основана на недоказанных математических гипотезах о трудности решения определенных задач, таких, как разложение на множители (с классическими компьюгерэми!), но несмотря на это, такие криптосистемы более удобны и широко используются. Основной трудностью при использовании криптосистем с закрытым ключом является безопасное распределение битов ключа. В частности, шифр Веризма надежен, только пока число битов ключа не меньше размера кодируемого сообщения, причем биты ключа нельзя использовать повторно! Большое количество битов ключа делает такие схемы непрактичными для широкого применения. Кроме того, биты ключа должны быть доставлены заранее, тщательно защищены до использования, а потом уничтожены; в противном случае классическая информация такого рода может быть в принципе скопирована, что подвергает опасности надежность всего протокола.
Несмотря на эти недостатки, криптосистемы с закрытым ключом, такие как шифр Вернама, продолжают использовать благодаря их гарантированной безопасности с ключами, 45' 708 Глава 12. Квантовая теория информации доставленными при тайном свидании, доверенным курьером или при помощи надежных личных связей. сообщение % И |А| К Ш И |М| ю|о|ИИ~ИИИ И И И И И И И Зищнфровенное ~ Иу| |ц ~Е [Е | ц~ я ~~р сообщение | Открытый канал Полученное ~~ Е | | ьт| щ ~д ~щ Рут сообщение д ру й [сЦ |О~ [У] ~Я |Щ Я |в~ ключ И И И И И И И ~О] ~~ ~~~ ~й~ |ГГ |Я | М сообщение Рис.
12.12. Шифр Вернама Алиса кодирует, прибавляя к посылаемому сообщению случайные биты ключа (или как в нашем примере, буквы алфавита). Боб декодирует, вычитая биты ключа, чтобы восстановить сообщение 'Упражнение 12.25. Рассмотрите систему с и пользователями, любая пара которых хотела бы общаться лично. Сколько требуется ключей при использовании криптографии с открытым ключом? Сколько требуется ключей при использовании криптографии с закрытым ключом? 12.6.2 Усиление конфиденциальности и согласование информации Первый шаг в криптографии с закрытым ключом — распределение строки ключа. Что, если Алиса и Боб начнут с дефектных ключей? Предположим, в частности, что Алиса и Боб разделяют коррелированные случайные классические битовые строки Х и У, и существует верхняя граница для взаимной информации Евы с Х и У.
Как они могут получить из этих дефектных ключей достаточно хороший ключ для выполнения безопасного криптографического протокола? Мы покажем, что, выполнив согласование информации, а затем усиление конфиденциальности, Алиса и Боб могут систематически увеличивать корреляцию между своими строками ключа, одновременно уменьшая вза- 12.6. Квантовая криптография 709 имную информацию с подслушивающей Евой до некоторого желаемого уровня безопасности.
Эти классические процедуры будут использованы в квантовом протоколе распределения ключей, описанном в следующем разделе. Согласование информации — не что иное, как исправление ошибок, выполняемое в открытом канале, которое устраняет расхождения между Х и У, что позволяет получить совместную битовую строку И' и насколько возможно уменьшить утечку информации к Еве. Предположим, что после этой процедуры Ева получила случайную величину Я, которая частично коррелирована с И~. Тогда Алиса и Боб используют усиление конфиденциальности для выделения из И' меньшего набора битов Я, корреляция которого с Я ниже желаемого порога.
Поскольку этот последний шаг концептуально нов, рассмотрим его в первую очередь. Детальное доказательство того, почему достигается усиление конфиденциальности, выходит за рамки этой книги, но мы опишем основной метод и приведем главную теорему. Один из способов усиления конфиденциальности состоит в использовании класса универсальных хеш-функций и, которые отображают набор и битовых строк А в набор пг-битовых строк Н. При этом для любых различных ам аз 6 А и д, случайно выбранного из й, вероятность того, что д(аг) = д(аг), не более, чем 1/~В/. Коллизионная энтропия случайной величины Х с распределением вероятностей р(х) определяется как (12.171) Нс(Х) = — 1оя У р(х) (Иногда ее называют энтропией Реньи второго порядка.) Используя выпуклость логарифмической функции, нетрудно показать, что энтропия Шеннона ограничивает эту величину сверху: Н(Х) > НДХ).
Коллизионная энтропия используется в следующей теореме об универсальных хеш-функциях: Теорема 12.16. Пусть Х вЂ” случайная величина из алфавита Х с распределением вероятностей р(х) и коллизионной энтропией Н,(Х) и пусть 0 — случайная величина, соответствующая равновероятному случайному выбору хешфункций из универсального класса хеш-функций, отображающих Х в (О, Ц"'. Тогда Н(б(Х) Щ ~ )На(ЯХ)!С) > пг — 2~ ~ ~~1.
(12.172) Теорему 12.16 можно использовать для усиления конфиденциальности следующим образом. Алиса и Боб открыто выбирают д е и и каждый применяет д к И~, получая новую битовую строку Я в качестве своего секретного ключа. Если неопределенность Евы относительно И~ при заданном ее знании Я = г (о конкретном значении И~), выраженная через коллизионную энтропию, ограничена снизу некоторым числом Н (% ~ Е = з) > И, то из теоремы 12 16 следует, что (12.173) Н,(Я~С, Я = г) > т — 2 710 Глава 12. Квантовая теория информации Другими словами, т может быть выбрано настолько малым, чтобы Н,($~С,Е = г) приблизительно равнялась т.
Это приводит к максимально возможной неопределенности Евы относительно ключа Я, обеспечивая секретность ключа. Согласование информации также уменьшает число битов ключа, которые Алиса и Боб могут получить, однако, это уменьшение может быть ограничено следующим образом. Проводя проверки на четность по нескольким подмножествам своих битов Х, Алиса может составить (классическое) сообщение и, содержащее описания этих подмножеств и их четности.
Получив это сообщение, Боб исправляет ошибки в своей строке У, после чего и Алиса, и Боб имеют одну и ту же строку 1т". Очевидно, что это потребует посылки )е > Н(И'~У) битов информации в и. Однако, эта процедура дает Еве дополнительное знание У = и, увеличивая таким образом ее коллизионную энтропию до Н,(1У~ Е = г, Н = и). В среднем (по возможным сообщениям согласования и) это увеличение ограничено снизу Н,(И'~Я = г, У = и) > Н,(Ю~Х = г) — Н(Н), где Н(17) — обычная энтропия Шеннона для У.
Однако это ограничение слишком слабое, поскольку предполагает, что вероятность того, что просочившаяся информация У = и уменьшит Н, на величину, большую тН(Н), всего лишь не больше 1/т. Более сильное ограничение дает следующая теорема: Теорема 12.17. Пусть Х и У вЂ” случайные величины из алфавитов Х и 11 соответственно, где Х имеет распределение вероятностей р(х), а р(х, и) — совместное распределение У с Х.
Пусть также в > 0 — произвольный параметр. Тогда с вероятностью, по меньшей мере, 1 — 2 ', У принимает значение и, для которого Н,(Х~(7= и) > Н,(Х) — 21ой)14! — 2в. (12.174) Входящее в это выражение в называется параметром секретности. Применение теоремы к протоколу согласования позволяет сделать вывод, что Алиса и Боб могут выбрать такое в, что коллизионная энтропия Евы будет ограничена снизу как Н,(УМ~2 = г, У = и) > д — 2(й+ в) с вероятностью, большей, чем 1 — 2 *. Затем, усиление конфиденциальности дает им возможность очистить т битов секретного ключа Я, для которого полная информация Евы меньше, чем 2'" е+Щ"+'1 битов.
Усиление конфиденциальности и согласование информации с иомои4ью СЯЯ кода Как отмечалось выше, согласование информации — зто не что иное, как исправление ошибок. Оказывается, что усиление конфиденциальности также тесно связано с исправлением ошибок, и обе задачи можно решить, используя классические коды.
Такая точка зрения будет полезна при доказательстве безопасности квантового распределения ключей в подрэзд. 12.6.5, поскольку у нас есть хорошо разработанная теория квантовых кодов, исправляющих ошибки. Ввиду этого полезно привести следующие соображения. Декодирование из случайно выбранного СЯЗ кода (см. подрэзд. 10.4.2) можно рассматривать как согласование информации и усиление конфиденциаль- 12.6. Квантовая криптография 711 ности. Хотя СЯЯ коды обычно используются для кодирования квантовой информации, для наших целей мы можем ограничиться их классическими свойствами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
