Модель с шумным хранилищем
Модель шумного хранения [1] относится к криптографической модели, используемой в квантовой криптографии . Предполагается, что устройство квантовой памяти злоумышленника ( противника ), пытающегося взломать протокол, несовершенно (зашумлено). Основная цель этой модели — обеспечить безопасную реализацию двусторонних криптографических примитивов, таких как фиксация битов , неконтролируемая передача и безопасная идентификация .
Мотивация
[ редактировать ]Квантовая связь оказалась чрезвычайно полезной, когда дело доходит до распространения ключей шифрования. Это позволяет двум удаленным сторонам, Алисе и Бобу, расширить небольшой начальный секретный ключ до секретного ключа произвольной длины, отправляя кубиты друг другу (квантовые биты). Самое главное, можно показать, что любой перехватчик, пытающийся подслушать их общение, не сможет перехватить никакой информации о длинном ключе. Это известно как квантовое распределение ключей (QKD).
Тем не менее, было показано, что даже квантовая связь не позволяет безопасно реализовать многие другие двусторонние криптографические задачи. [2] [3] [4] [5] Все это образует примеры безопасной оценки функций . Примером является невнимательная передача . Что отличает эти задачи от распределения ключей, так это то, что они направлены на решение проблем между двумя сторонами, Алисой и Бобом, которые не доверяют друг другу. нет То есть посторонней стороны вроде подслушивателя , есть только Алиса и Боб. Интуитивно понятно, что именно отсутствие доверия усложняет проблему. В отличие от квантового распределения ключей , Алиса и Боб не могут сотрудничать, пытаясь обнаружить любую подслушивающую активность. Вместо этого каждая сторона должна постоять за себя.
Поскольку такие задачи, как безопасная идентификация, представляют практический интерес, можно сделать предположения о том, насколько могущественным может быть противник . Безопасность сохраняется до тех пор, пока выполняются эти предположения. В классической криптографии, то есть без использования квантовых инструментов, большинство из них являются вычислительными предположениями . Такие предположения состоят из двух частей. Во-первых, предполагается, что конкретную проблему трудно решить. Например, можно предположить, что сложно разложить большое целое число на его простые множители (например, 15=5x3). Во-вторых, предполагается, что противник обладает ограниченной вычислительной мощностью, а именно меньшей, чем то, что (предположительно) требуется для решения выбранной проблемы.
Ограниченное хранилище
[ редактировать ]В теоретико-информационной криптографии появляются физические предположения, которые не опираются на какие-либо предположения о стойкости, а просто предполагают ограничение какого-то другого ресурса. В классической криптографии модель ограниченного хранилища, предложенная Ули Маурером, предполагает, что злоумышленник может хранить только определенное количество классических битов. [6] [7] Известны протоколы, которые (в принципе) позволяют безопасно реализовать любую криптографическую задачу, пока у противника мало памяти. Интуитивно, безопасность становится возможной при этом предположении, поскольку злоумышленнику приходится выбирать, какую информацию хранить. То есть протокол фактически переполняет его память, что приводит к неизбежной нехватке информации для противника. Позже было обнаружено, что любой классический протокол , требующий от честных сторон хранить бит для успешного выполнения могут быть взломаны злоумышленником, который может хранить более биты. [8] То есть разрыв между тем, что требуется для выполнения протокола, и тем, что требуется для взлома безопасности, относительно невелик.
Ограниченное квантовое хранилище
[ редактировать ]Этот разрыв резко меняется при использовании квантовой связи. [9] . То есть Алиса и Боб могут отправлять друг другу кубиты в рамках протокола. Аналогично, теперь предполагается, что квантовая память противника ограничена определенным количеством кубитов. Нет ограничений на количество классических битов, которые может хранить злоумышленник. Это известно как модель ограниченного квантового хранилища . [9] [10] Было показано, что существуют квантовые протоколы, в которых честным сторонам вообще не требуется квантовое хранилище для их выполнения, но, тем не менее, они безопасны, пока Алиса передает более чем в два раза больше кубитов, чем может хранить противник.
Шумное хранилище
[ редактировать ]В более общем плане безопасность возможна до тех пор, пока объем информации, которую злоумышленник может хранить в своем запоминающем устройстве, ограничен. Эта интуиция отражается моделью шумного хранения . [1] который включает в себя модель ограниченного квантового хранения как частный случай. [11] Такое ограничение может возникнуть, например, если запоминающее устройство чрезвычайно велико, но очень несовершенно. В теории информации такое несовершенное запоминающее устройство еще называют шумным каналом . Мотивация для этой более общей модели тройная. Во-первых, это позволяет делать заявления о гораздо более общих устройствах памяти, которые могут быть доступны противнику. Во-вторых, заявления о безопасности могут быть сделаны, когда передаваемые сигналы или само устройство хранения используют непрерывные переменные , размерность которых бесконечна и, следовательно, не может быть учтена с помощью предположения об ограниченном хранении без дополнительных ограничений. В-третьих, даже если размерность самих сигналов невелика, анализ хранения с шумом обеспечивает безопасность, выходящую за рамки режима, в котором само ограниченное хранилище может делать какие-либо заявления о безопасности. Например, если канал хранения нарушает запутанность, безопасность возможна, даже если устройство хранения имеет сколь угодно большой размер (т. е. не ограничено каким-либо образом).
Предположение
[ редактировать ]Предположение модели хранения с шумом состоит в том, что во время ожидания введенное в протокол, противник может хранить квантовую информацию только в своем шумном устройстве памяти. [11] Такое устройство представляет собой просто квантовый канал который принимает входные состояния к некоторым шумным состояниям вывода . В противном случае противник всесилен. Например, он может хранить неограниченное количество классической информации и мгновенно выполнять любые вычисления.

Последнее предположение также подразумевает, что он может выполнить любую форму кодирования с коррекцией ошибок до и после использования шумного устройства памяти, даже если это очень сложно сделать в вычислительном отношении (т. е. требует много времени). В этом контексте это обычно называется атакой кодирования. и атака декодирования . Поскольку классическая память противника может быть сколь угодно большой, кодирование может не только генерировать некоторое квантовое состояние в качестве входных данных для устройства хранения но и выводить классическую информацию. Декодирующая атака противника может использовать эту дополнительную классическую информацию, а также любую дополнительную информацию, которую злоумышленник может получить по истечении времени ожидания.
На практике часто рассматривают устройства хранения данных, состоящие из ячейки памяти, каждая из которых подвержена шуму. В терминах теории информации это означает, что устройство имеет вид , где — это шумный квантовый канал, действующий на ячейку памяти размером .
Примеры
[ редактировать ]- Устройство хранения состоит из кубиты , каждый из которых подвержен деполяризующему шуму . То есть, , где — двумерный деполяризующий канал .
- Устройство хранения состоит из кубиты , которые не содержат шума. Это соответствует частному случаю ограниченной квантовой памяти . То есть, , где это идентификационный канал .
Протоколы
[ редактировать ]Большинство протоколов выполняются в два этапа. Сначала Алиса и Боб обмениваются кубиты, закодированные в двух или трех взаимно несмещенных базисах . Это те же кодировки, которые используются в BB84 или с шестью состояниями протоколах квантового распределения ключей . Обычно это происходит так: Алиса отправляет такие кубиты Бобу, а Боб измеряет их сразу по прибытии. Преимущество этого подхода заключается в том, что Алисе и Бобу не требуется квантовое хранилище для выполнения протокола. Более того, экспериментально относительно легко создать такие кубиты , что позволяет реализовать такие протоколы с использованием доступных в настоящее время технологий. [12]
Вторым шагом является выполнение классической постобработки данных измерений, полученных на первом этапе. Используемые методы зависят от рассматриваемого протокола и включают усиление конфиденциальности , коды, исправляющие ошибки , выборку с минимальной энтропией и интерактивное хеширование.
Общий
[ редактировать ]Чтобы продемонстрировать, что все двусторонние криптографические задачи могут быть реализованы безопасно, общий подход состоит в том, чтобы показать, что может быть реализован простой криптографический примитив, который, как известно, является универсальным для безопасной оценки функции . То есть, как только удастся построить протокол для такого криптографического примитива, все остальные задачи можно будет реализовать, используя этот примитив в качестве основного строительного блока. Одним из таких примитивов является передача без внимания . В свою очередь, передача без внимания может быть построена из еще более простого строительного блока, известного как стирание слабой строки, в сочетании с криптографическими методами, такими как усиление конфиденциальности .
Все предложенные на сегодняшний день протоколы позволяют одной из сторон (Алисе) иметь даже неограниченный объем бесшумной квантовой памяти. Т.е. предположение о хранении шума применяется только к одной из сторон (Бобу). Для запоминающих устройств вида известно, что любая двусторонняя криптографическая задача может быть безопасно реализована посредством слабого стирания строки и неконтролируемой передачи, когда выполняется любое из следующих условий.
- Для ограниченной квантовой памяти (т.е. ), безопасность может быть достигнута с помощью протокола, по которому Алиса отправляет BB84 в кодировке Кубиты . [11] То есть безопасность может быть достигнута, когда Алиса отправляет более чем в два раза больше кубитов, чем может хранить Боб. Можно также посмотреть на это с точки зрения Боба и сказать, что безопасность может быть достигнута, когда Боб сможет хранить строго меньше половины кубитов, отправленных Алисой, т. е. .
- Для ограниченного квантового хранилища с использованием ячеек памяти более высокой размерности (т. е. каждая ячейка является не кубитом , а кудитом ) безопасность может быть достигнута с помощью протокола, по которому Алиса отправляет кудиты более высокого измерения закодировали одну из возможных взаимно несмещенных базисов . В пределе больших размеров безопасность может быть достигнута всякий раз, когда . То есть безопасность всегда может быть достигнута до тех пор, пока Боб не может хранить какую-либо постоянную часть передаваемых сигналов. [13] Это оптимально для рассматриваемых протоколов, поскольку для нечестный Боб может хранить все кудиты, отправленные Алисой. Неизвестно, возможно ли то же самое, используя только кубиты, закодированные в BB84 .
- Для шумохранилищ и устройств вида безопасность может быть достигнута с использованием протокола, по которому Алиса отправляет BB84, в кодировке кубиты если
- , [11] где — классическая пропускная способность квантового канала , и подчиняется так называемому сильному обратному свойству , [14] или, если
- , [15] где - стоимость запутанности квантового канала . Это, как правило, гораздо лучше, чем условие классической емкости , однако оценить его труднее. .
- Для шумохранилищ и устройств вида безопасность может быть достигнута с использованием протокола, по которому Алиса отправляет кубиты, закодированные в одном из трех взаимно несмещенных оснований на кубит, если
Три взаимно несмещенных основания представляют собой те же кодировки, что и в с шестью состояниями протоколе квантового распределения ключей . Последнее условие действительно является наиболее известным условием для большинства каналов, однако квантовую емкость , а также сильный обратный параметр обычно определить непросто.
Конкретные задачи
[ редактировать ]Использование таких базовых примитивов в качестве строительных блоков не всегда является наиболее эффективным способом решения криптографической задачи. Специализированные протоколы, предназначенные для решения конкретных проблем, обычно более эффективны. Примеры известных протоколов:
- Обязательство по битам в модели хранения с шумом. [11] [13] а в случае ограниченной квантовой памяти [10]
- Незабываемый перенос в модели с шумным запоминанием, [11] а в случае ограниченной квантовой памяти [9] [10]
- Безопасная идентификация в модели с ограниченной квантовой памятью [17] [18]
Шумное хранилище и QKD
[ редактировать ]Предположение об ограниченном квантовом хранилище также применялось за пределами безопасной оценки функций . В частности, было показано, что если перехватчик при распределении квантовых ключей ограничен памятью, в экспериментальной реализации можно допустить более высокий уровень битовых ошибок. [10]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Венер, С.; К. Шаффнер; Б. Терхал (2008). «Криптография из шумохранилища». Письма о физических отзывах . 100 (22): 220502. arXiv : 0711.2895 . Бибкод : 2008PhRvL.100v0502W . doi : 10.1103/PhysRevLett.100.220502 . ПМИД 18643410 . S2CID 2974264 .
- ^ Ло, Х.; Х. Чау (1997). «Действительно ли возможно использование квантовых битов?». Письма о физических отзывах . 78 (17): 3410. arXiv : quant-ph/9603004 . Бибкод : 1997PhRvL..78.3410L . doi : 10.1103/PhysRevLett.78.3410 . S2CID 3264257 .
- ^ Ло, Х (1997). «Небезопасность квантово-безопасных вычислений». Физический обзор А. 56 (2): 1154–1162. arXiv : Quant-ph/9611031 . Бибкод : 1997PhRvA..56.1154L . дои : 10.1103/PhysRevA.56.1154 . S2CID 17813922 .
- ^ Майерс, Д. (1997). «Безусловно безопасное использование квантовых битов невозможно». Письма о физических отзывах . 78 (17): 3414–3417. arXiv : Quant-ph/9605044 . Бибкод : 1997PhRvL..78.3414M . doi : 10.1103/PhysRevLett.78.3414 . S2CID 14522232 .
- ^ Д'Ариано, Дж.; Д. Кречманн; Д. Шлингеманн; РФ Вернер (2007). «Возвращение к квантовым битам: возможное и невозможное». Физический обзор А. 76 (3): 032328. arXiv : quant-ph/0605224 . Бибкод : 2007PhRvA..76c2328D . дои : 10.1103/PhysRevA.76.032328 . S2CID 119340261 .
- ^ Маурер, У. (1992). «Условно-совершенная секретность и доказуемо безопасный рандомизированный шифр» . Журнал криптологии . 5 (1): 53––66. дои : 10.1007/bf00191321 . S2CID 12079602 .
- ^ Кашен, К.; У. Маурер (1997). «Безусловная безопасность от противников, ограниченных памятью». Труды CRYPTO 1997 : 292–306.
- ^ Дзембовский, С.; У. Маурер (2004). «О создании начального ключа в модели с ограниченным хранилищем». Труды EUROCRYPT : 126–137.
- ^ Перейти обратно: а б с И., Дамгаард; С. Фер; Л. Сальвей; К. Шаффнер (2005). «Криптография в модели ограниченного квантового хранилища». 46-й ежегодный симпозиум IEEE по основам информатики (FOCS'05) . стр. 449–458. arXiv : Quant-ph/0508222 . Бибкод : 2005quant.ph..8222D . дои : 10.1109/SFCS.2005.30 . ISBN 978-0-7695-2468-9 . S2CID 174322 .
- ^ Перейти обратно: а б с д Дамгаард, И.; С. Фер; Р. Реннер; Л. Сальвей; К. Шаффнер (2007). «Жесткая связь энтропийной квантовой неопределенности высокого порядка с приложениями». Достижения криптологии — КРИПТО 2007 . Конспекты лекций по информатике. Том. 4622. стр. 360–378. arXiv : Quant-ph/0612014 . Бибкод : 2006quant.ph.12014D . дои : 10.1007/978-3-540-74143-5_20 . ISBN 978-3-540-74142-8 . S2CID 2557603 .
- ^ Перейти обратно: а б с д и ж Кениг, Роберт; С. Венер; Дж. Вулшлегер (2009). «Безусловная безопасность от шумного квантового хранилища». Транзакции IEEE по теории информации . 58 (3): 1962–1984. arXiv : 0906.1030 . Бибкод : 2009arXiv0906.1030K . дои : 10.1109/TIT.2011.2177772 . S2CID 12500084 .
- ^ Венер, С.; М. Керти; К. Шаффнер; Х. Ло (2010). «Реализация двусторонних протоколов в модели хранения с шумом». Физический обзор А. 81 (5): 052336. arXiv : 0911.2302 . Бибкод : 2010PhRvA..81e2336W . дои : 10.1103/PhysRevA.81.052336 . S2CID 6187112 .
- ^ Перейти обратно: а б Мандаям, П.; С. Венер (2011). «Достижение физических пределов модели с ограниченной памятью». Физический обзор А. 83 (2): 022329. arXiv : 1009.1596 . Бибкод : 2011PhRvA..83b2329M . дои : 10.1103/PhysRevA.83.022329 . S2CID 11753298 .
- ^ Кениг, Р.; С. Венер (2009). «Сильное обращение к классическому канальному кодированию с использованием запутанных входов». Письма о физических отзывах . 103 (7): 070504. arXiv : 0903.2838 . Бибкод : 2009PhRvL.103g0504K . doi : 10.1103/PhysRevLett.103.070504 . ПМИД 19792627 . S2CID 25002853 .
- ^ Берта, М.; Ф. Брандао; М. Кристандл; С. Венер (2013). «Стоимость запутанности квантовых каналов». Транзакции IEEE по теории информации . 59 (10): 6779–6795. arXiv : 1108.5357 . Бибкод : 2011arXiv1108.5357B . дои : 10.1109/TIT.2013.2268533 . S2CID 322613 .
- ^ Берта, М.; О. Фаузи; С. Венер (2014). «Квантовые и классические экстракторы случайности». Транзакции IEEE по теории информации . 60 (2): 1168–1192. arXiv : 1111.2026 . Бибкод : 2011arXiv1111.2026B . дои : 10.1109/TIT.2013.2291780 . S2CID 10018325 .
- ^ Дамгаард, И.; С. Фер; Л. Сальвей; К. Шаффнер (2007). «Безопасная идентификация и QKD в модели ограниченного квантового хранения». Достижения криптологии — КРИПТО 2007 . Конспекты лекций по информатике. Том. 4622. С. 342–359. arXiv : 0708.2557 . Бибкод : 2007arXiv0708.2557D . дои : 10.1007/978-3-540-74143-5_19 . ISBN 978-3-540-74142-8 . S2CID 97510 .
- ^
Бауман, Н.; С. Фер; К. Гонсалес-Гильен; К. Шаффнер (2011). «Энтропийные отношения неопределенности «все кроме одного» и применение к идентификации на основе пароля». arXiv : 1105.6212 . Бибкод : 2011arXiv1105.6212B .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь )