Модель с шумным хранилищем - Noisy-storage model

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

Мотивация

Квантовая связь оказалась чрезвычайно полезной при распространении ключей шифрования. Это позволяет двум удаленным сторонам Алисе и Бобу расширить небольшую начальную Секретный ключ в произвольно длинный секретный ключ, отправив кубиты (квантовые биты) друг к другу. Самое главное, можно показать, что любой подслушивающий попытки подслушать их общение не могут перехватить информацию о длинном ключе. Это известно как квантовое распределение ключей (QKD).

Тем не менее, было показано, что даже квантовая связь не позволяет безопасно реализовать многие другие двухсторонние криптографические задачи.^[2][3][4][5] Все они образуют экземпляры оценка безопасной функции. Примером является не обращая внимания на передачу. Что отличает эти задачи от распределения ключей, так это то, что они направлены на решение проблем между двумя сторонами, Алисой и Бобом, которые нет доверяют друг другу. То есть нет такой посторонней вечеринки, как подслушивающий, только Алиса и Боб. Интуитивно понятно, что именно недостаток доверия усложняет проблему. В отличие от квантовое распределение ключей, Алиса и Боб не могут совместно пытаться обнаружить любую активность подслушивания. Вместо этого каждая сторона должна заботиться о себе.

Поскольку задачи вроде безопасная идентификация представляют практический интерес, можно сделать предположения о том, насколько сильны противник возможно. Безопасность сохраняется, пока выполняются эти предположения. В классической криптографии, то есть без использования квантовых инструментов, большинство из них расчетные допущения. Такое предположение состоит из двух частей. Во-первых, предполагается, что конкретную проблему трудно решить. Например, можно предположить, что трудно фактор большой целое число в его основной факторы (например, 15 = 5x3). Во-вторых, предполагается, что злоумышленник имеет ограниченную вычислительную мощность, а именно меньшую, чем то, что (как предполагается) требуется для решения выбранной проблемы.

Ограниченное хранилище

В теоретическая криптография появляются физические предположения, которые не основываются на каких-либо предположениях о твердости, а просто предполагают ограничение на какой-либо другой ресурс. В классической криптографии модель ограниченного хранения представлен Ули Маурер предполагает, что противник может хранить только определенное количество классических битов.^[6][7] Известны протоколы, которые (в принципе) позволяют безопасно реализовать любую криптографическую задачу, если хранилище злоумышленника невелико. На интуитивном уровне безопасность становится возможной при этом предположении, поскольку злоумышленник должен сделать выбор, какую информацию сохранить. То есть протокол эффективно переполняет его запоминающее устройство, что приводит к неизбежной нехватке информации для противника. Позже было обнаружено, что любой классический протокол что требует от честных сторон хранить ${\displaystyle n}$ биты для успешного выполнения могут быть сломаны противником, который может хранить более ${\displaystyle O(n^{2})}$ биты.^[8] То есть разрыв между тем, что требуется для выполнения протокола, и тем, что требуется для взлома защиты, относительно невелик.

Ограниченное квантовое хранилище

Этот разрыв кардинально меняется при использовании квантовая связь^[9]. То есть Алиса и Боб могут отправить кубиты друг к другу как часть протокола. Точно так же теперь предполагается, что квантовое хранилище противника ограничено определенным количеством кубитов. Нет никаких ограничений на то, сколько классических битов может хранить злоумышленник. Это известно как ограниченныйквант-модель хранения.^[9][10] Было показано, что существуют квантовые протоколы, в которых честные стороны нуждаются в нет квантовое хранилище вообще для их выполнения, но тем не менее является безопасным, пока Алиса передает более чем в два раза больше кубитов, чем может сохранить злоумышленник.

Шумное хранилище

В более общем плане безопасность возможна до тех пор, пока ограничен объем информации, которую злоумышленник может хранить на своем устройстве памяти. Эта интуиция улавливается модель с шумной памятью,^[1] который включает модель ограниченного квантового накопителя как частный случай.^[11] Такое ограничение может, например, возникать, если запоминающее устройство очень велико, но очень несовершенно. В теория информации такое несовершенное запоминающее устройство также называют шумный канал. У этой более общей модели есть три мотивации. Во-первых, он позволяет делать заявления о гораздо более общих устройствах памяти, которые могут быть доступны злоумышленнику. Во-вторых, заявления о безопасности могут быть сделаны, когда передаваемые сигналы или само запоминающее устройство использует непрерывные переменные чья размерность бесконечна и, следовательно, не может быть захвачена предположением об ограниченном хранилище без дополнительных ограничений. В-третьих, даже если размер самих сигналов невелик, анализ зашумленного хранилища позволяет обеспечить безопасность за пределами режима, в котором само ограниченное хранилище может делать любые заявления о безопасности. Например, если канал хранения нарушает перепутанность, безопасность возможна, даже если запоминающее устройство произвольно велико (то есть никоим образом не ограничено).

Предположение

Предположение модели с шумным хранилищем состоит в том, что во время ожидания ${\displaystyle \Delta t}$ внесены в протокол, противник можно только хранить квантовая информация в его шумном запоминающем устройстве.^[11] Такое устройство - просто квантовый канал ${\displaystyle {\mathcal {F}}:{\mathcal {S}}({\mathcal {H}}_{\rm {in}})\rightarrow {\mathcal {S}}({\mathcal {H}}_{\rm {out}})}$ это требует ввода состояния ${\displaystyle \rho _{\rm {in}}\in {\mathcal {S}}({\mathcal {H}}_{\rm {in}})}$ в некоторые зашумленные состояния выхода ${\displaystyle \rho _{\rm {out}}\in {\mathcal {S}}({\mathcal {H}}_{\rm {out}})}$. В противном случае противник всемогущ. Например, он может хранить неограниченное количество классической информации и мгновенно выполнять любые вычисления.

Во время ожидания ${\displaystyle \Delta t}$ необходимо использовать запоминающее устройство.

Последнее предположение также подразумевает, что он может выполнять любую форму кодирование с исправлением ошибок до и после использования зашумленного устройства памяти, даже если это очень сложно с вычислительной точки зрения (т. е. требует много времени). В этом контексте это обычно называется атакой кодирования. ${\displaystyle {\mathcal {E}}}$ и декодирующая атака ${\displaystyle {\mathcal {D}}}$. Поскольку классическая память противника может быть сколь угодно большой, кодирование ${\displaystyle {\mathcal {E}}}$ может не только генерировать некоторые квантовое состояние как вход в запоминающее устройство ${\displaystyle {\mathcal {F}}}$ но также выводят классическую информацию. Расшифровывающая атака противника ${\displaystyle {\mathcal {D}}}$ может использовать эту дополнительную классическую информацию, а также любую дополнительную информацию, которую злоумышленник может получить по истечении времени ожидания.

На практике часто рассматриваются устройства хранения, состоящие из ${\displaystyle N}$ ячейки памяти, каждая из которых подвержена шуму. В теоретико-информационной терминологии это означает, что устройство имеет вид ${\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}}$, куда ${\displaystyle {\mathcal {N}}:S(\mathbb {C} ^{d})\rightarrow S(\mathbb {C} ^{d})}$ шумно квантовый канал воздействуя на ячейку памяти размерности ${\displaystyle d}$.

Примеры

• Запоминающее устройство состоит из ${\displaystyle N}$ кубиты, каждый из которых подлежит деполяризующий шум. То есть, ${\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}}$, куда ${\displaystyle {\mathcal {N}}(\rho )=\lambda \rho +(1-\lambda ){\mathsf {id}}/2}$ двумерный деполяризующий канал.
• Запоминающее устройство состоит из ${\displaystyle N}$ кубиты, которые бесшумны. Это соответствует частному случаю ограниченная квантовая память. То есть, ${\displaystyle {\mathcal {F}}={\mathsf {id}}^{\otimes N}}$, куда ${\displaystyle {\mathsf {id}}}$ это канал идентификации.

Протоколы

Большинство протоколов выполняется в два этапа. Сначала Алиса и Боб обмениваются ${\displaystyle n}$ кубиты закодировано в двух или трех взаимно объективные основы. Это те же самые кодировки, которые используются в BB84 или же протоколы с шестью состояниями из квантовое распределение ключей. Обычно это происходит в форме отправки таких кубитов Бобу Алисой, а Боб измеряет их сразу по прибытии. Это имеет то преимущество, что Алисе и Бобу не требуется квантовое хранилище для выполнения протокола. Кроме того, экспериментально относительно легко создать такой кубиты, что позволяет реализовать такие протоколы с использованием доступных в настоящее время технологий.^[12]

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

Общий

Чтобы продемонстрировать, что все двусторонние криптографические задачи могут быть реализованы безопасно, общий подход состоит в том, чтобы показать, что может быть реализован простой криптографический примитив, который, как известно, универсальный за оценка безопасной функции. То есть, как только удастся построить протокол для такого криптографического примитива, все остальные задачи могут быть реализованы с использованием этого примитива в качестве базового строительного блока. Одним из таких примитивов является не обращая внимания на передачу. В очереди, не обращая внимания на передачу может быть построен из еще более простого строительного блока, известного как слабое стирание строки в сочетании с криптографическими методами, такими как усиление конфиденциальности.

Все предложенные на сегодняшний день протоколы позволяют одной из сторон (Алисе) иметь даже неограниченный объем бесшумной квантовой памяти. То есть предположение о шумном хранении применяется только к одной из сторон (Боб). Для запоминающих устройств вида ${\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}}$ известно, что любой двусторонняя криптографическая задача можно безопасно реализовать с помощью слабое стирание строки и не обращая внимания на передачу при выполнении любого из следующих условий.

• Для ограниченной квантовой памяти (т. Е. ${\displaystyle {\mathcal {N}}={\mathsf {id}}}$) безопасность может быть достигнута с помощью протокола, в котором Алиса отправляет ${\displaystyle n>2N}$ BB84 закодированный кубиты.^[11] То есть безопасность может быть достигнута, когда Алиса отправляет в два раза больше кубитов, чем Боб может хранить. Можно также взглянуть на это с точки зрения Боба и сказать, что безопасность может быть достигнута, когда Боб может хранить строго меньше половины кубитов, отправленных Алисой, т.е. ${\displaystyle N<n/2}$.
• Для ограниченного квантового хранилища с использованием ячеек памяти более высокой размерности (т.е. каждая ячейка не является кубит, но Qudit ), безопасность может быть достигнута в протоколе, в котором Алиса отправляет ${\displaystyle n}$ многомерные кудиты закодировали один из возможных взаимно объективные основы. В пределах больших размеров безопасность может быть достигнута всякий раз, когда ${\displaystyle n\gtrapprox N}$. Таким образом, безопасность всегда может быть достигнута до тех пор, пока Боб не может хранить постоянную долю переданных сигналов.^[13] Это оптимально для рассматриваемых протоколов, поскольку для ${\displaystyle n=N}$ нечестный Боб может хранить все кудиты, отправленные Алисой. Неизвестно, возможно ли то же самое, просто используя BB84 закодированные кубиты.

• Для шумных хранилищ и устройств вида ${\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}}$ безопасность может быть достигнута с помощью протокола, в котором Алиса отправляет ${\displaystyle n}$ BB84 закодированный кубиты если

• ${\displaystyle n>2\cdot N\cdot C({\mathcal {N}})}$,^[11] куда ${\displaystyle C({\mathcal {N}})}$ это классическая емкость из квантовый канал ${\displaystyle {\mathcal {N}}}$, и ${\displaystyle {\mathcal {N}}}$ подчиняется так называемым сильное обратное свойство,^[14] или если

• ${\displaystyle n>2\cdot N\cdot E_{C}({\mathcal {N}})}$,^[15] куда ${\displaystyle E_{C}({\mathcal {N}})}$ это стоимость запутывания из квантовый канал ${\displaystyle {\mathcal {N}}}$. Обычно это намного лучше, чем состояние на классическая емкость, однако оценить сложнее ${\displaystyle E_{C}({\mathcal {N}})}$.

• Для шумных хранилищ и устройств вида ${\displaystyle {\mathcal {F}}={\mathcal {N}}^{\otimes N}}$ безопасность может быть достигнута с помощью протокола, в котором Алиса отправляет ${\displaystyle n}$ кубиты закодирован в одном из трех взаимно объективные основы на кубит, если

• ${\displaystyle n>Q({\mathcal {N}})N}$,^[16] куда ${\displaystyle Q}$ это квантовая емкость из ${\displaystyle {\mathcal {N}}}$, а параметр сильной обратной ${\displaystyle {\mathcal {N}}}$ не так уж и мала.

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

Конкретные задачи

Использование таких базовых примитивов в качестве строительных блоков не всегда является наиболее эффективным способом решения криптографической задачи. Специализированные протоколы, предназначенные для решения конкретных проблем, обычно более эффективны. Примеры известных протоколов:

• Битовая приверженность в модели с шумным хранилищем,^[11][13] а в случае ограниченной квантовой памяти^[10]
• Незаметный перевод в модели с шумным хранилищем,^[11] а в случае ограниченной квантовой памяти^[9][10]
• Безопасная идентификация в модели ограниченной квантовой памяти^[17][18]

Шумное хранилище и QKD

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

Смотрите также

• Стефани Венер

Рекомендации

1. Wehner, S .; К. Шаффнер; Б. Терхал (2008). «Криптография из зашумленных хранилищ». Письма с физическими проверками. 100 (22): 220502. arXiv:0711.2895. Bibcode:2008PhRvL.100v0502W. Дои:10.1103 / PhysRevLett.100.220502. PMID  18643410.
2. Lo, H .; Х. Чау (1997). «Возможны ли квантовые биты?». Письма с физическими проверками. 78 (17): 3410. arXiv:Quant-ph / 9603004. Bibcode:1997ПхРвЛ..78.3410Л. Дои:10.1103 / PhysRevLett.78.3410.
3. Lo, H (1997). «Небезопасность квантовых безопасных вычислений». Физический обзор A. 56 (2): 1154–1162. arXiv:Quant-ph / 9611031. Bibcode:1997ПхРвА..56.1154Л. Дои:10.1103 / PhysRevA.56.1154.
4. Майерс, Д. (1997). «Безоговорочно безопасное обязательство Quantum Bit невозможно». Письма с физическими проверками. 78 (17): 3414––3417. arXiv:Quant-ph / 9605044. Bibcode:1997ПхРвЛ..78.3414М. Дои:10.1103 / PhysRevLett.78.3414.
5. D'Ariano, G .; Д. Кречманн; Д. Шлингеманн; Р.Ф. Вернер (2007). «Квантовая приверженность битам: новое: возможное и невозможное». Физический обзор A. 76 (3): 032328. arXiv:Quant-ph / 0605224. Bibcode:2007PhRvA..76c2328D. Дои:10.1103 / PhysRevA.76.032328.
6. Маурер, У. (1992). «Условно-совершенная секретность и проверяемый случайный шифр». Журнал криптологии. 5 (1): 53––66. Дои:10.1007 / bf00191321.
7. Cachin, C .; У. Маурер (1997). «Безусловная безопасность против противников, ограниченных памятью». Труды CRYPTO 1997: 292–306.
8. Джимбовский, С .; У. Маурер (2004). «О генерации начального ключа в модели с ограниченным объемом памяти». Труды EUROCRYPT: 126–137.
9. И., Дамгаард; С. Фер; Л. Сальвейл; К. Шаффнер (2005). Криптография в модели ограниченного квантового хранилища. Материалы 46-го симпозиума IEEE по основам информатики. С. 449–458. arXiv:Quant-ph / 0508222. Bibcode:2005квант.ч..8222D. Дои:10.1109 / SFCS.2005.30. ISBN  978-0-7695-2468-9.
10. Damgaard, I .; С. Фер; Р. Реннер; Л. Сальвейл; К. Шаффнер (2007). Тесная связь энтропической квантовой неопределенности высокого порядка с приложениями. Материалы CRYPTO 2007. Конспект лекций по информатике. 4622. С. 360––378. arXiv:Quant-ph / 0612014. Bibcode:2006quant.ph.12014D. Дои:10.1007/978-3-540-74143-5_20. ISBN  978-3-540-74142-8.
11. Кениг, Роберт; С. Венер; Дж. Вулльшлегер (2009). «Безусловная безопасность от шумного квантового хранилища». IEEE Transactions по теории информации. 58 (3): 1962–1984. arXiv:0906.1030. Bibcode:2009arXiv0906.1030K. Дои:10.1109 / TIT.2011.2177772.
12. Wehner, S .; М. Курти; К. Шаффнер; Х. Ло (2010). «Реализация двухсторонних протоколов в модели с шумным хранилищем». Физический обзор A. 81 (5): 052336. arXiv:0911.2302. Bibcode:2010PhRvA..81e2336W. Дои:10.1103 / PhysRevA.81.052336.
13. Mandayam, P .; С. Венер (2011). «Достижение физических ограничений модели с ограниченным хранилищем». Физический обзор A. 83 (2): 022329. arXiv:1009.1596. Bibcode:2011PhRvA..83b2329M. Дои:10.1103 / PhysRevA.83.022329.
14. Koenig, R .; С. Венер (2009). «Сильный переход для классического кодирования каналов с использованием запутанных входов». Письма с физическими проверками. 103 (7): 070504. arXiv:0903.2838. Bibcode:2009ПхРвЛ.103г0504К. Дои:10.1103 / PhysRevLett.103.070504. PMID  19792627.
15. Berta, M .; Ф. Брандао; М. Кристандл; С. Венер (2013). «Стоимость запутывания квантовых каналов». IEEE Transactions по теории информации. 59 (10): 6779–6795. arXiv:1108.5357. Bibcode:2011arXiv1108.5357B. Дои:10.1109 / TIT.2013.2268533.
16. Berta, M .; О. Фаузи; С. Венер (2014). «Квантово-классические экстракторы случайности». IEEE Transactions по теории информации. 60 (2): 1168–1192. arXiv:1111.2026. Bibcode:2011arXiv1111.2026B. Дои:10.1109 / TIT.2013.2291780.
17. Damgaard, I .; С. Фер; Л. Сальвейл; К. Шаффнер (2007). Идентификация и КРК в модели ограниченного квантового хранилища. Материалы CRYPTO 2007. Конспект лекций по информатике. 4622. С. 342–359. arXiv:0708.2557. Bibcode:2007arXiv0708.2557D. Дои:10.1007/978-3-540-74143-5_19. ISBN  978-3-540-74142-8.
18. Bouman, N .; С. Фер; К. Гонсалес-Гильен; К. Шаффнер (2011). «Все, кроме одного отношения энтропийной неопределенности и приложение к идентификации на основе пароля». arXiv:1105.6212. Bibcode:2011arXiv1105.6212B.