Jump to content

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

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

Мотивация

[ редактировать ]

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

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

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

[ редактировать ]

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

Во время ожидания необходимо использовать запоминающее устройство.

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

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

  • Устройство хранения состоит из кубиты , каждый из которых подвержен деполяризующему шуму . То есть, , где — двумерный деполяризующий канал .
  • Устройство хранения состоит из кубиты , которые не содержат шума. Это соответствует частному случаю ограниченной квантовой памяти . То есть, , где это идентификационный канал .

Протоколы

[ редактировать ]

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

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

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

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

  • Для ограниченной квантовой памяти (т.е. ), безопасность может быть достигнута с помощью протокола, по которому Алиса отправляет BB84 в кодировке Кубиты . [11] То есть безопасность может быть достигнута, когда Алиса отправляет более чем в два раза больше кубитов, чем может хранить Боб. Можно также посмотреть на это с точки зрения Боба и сказать, что безопасность может быть достигнута, когда Боб сможет хранить строго меньше половины кубитов, отправленных Алисой, т. е. .
  • Для ограниченного квантового хранилища с использованием ячеек памяти более высокой размерности (т. е. каждая ячейка является не кубитом , а кудитом ) безопасность может быть достигнута с помощью протокола, по которому Алиса отправляет кудиты более высокого измерения закодировали одну из возможных взаимно несмещенных базисов . В пределе больших размеров безопасность может быть достигнута всякий раз, когда . То есть безопасность всегда может быть достигнута до тех пор, пока Боб не может хранить какую-либо постоянную часть передаваемых сигналов. [13] Это оптимально для рассматриваемых протоколов, поскольку для нечестный Боб может хранить все кудиты, отправленные Алисой. Неизвестно, возможно ли то же самое, используя только кубиты, закодированные в BB84 .
  • Для шумохранилищ и устройств вида безопасность может быть достигнута с использованием протокола, по которому Алиса отправляет BB84, в кодировке кубиты если
  • Для шумохранилищ и устройств вида безопасность может быть достигнута с использованием протокола, по которому Алиса отправляет кубиты, закодированные в одном из трех взаимно несмещенных оснований на кубит, если
  • , [16] где квантовая емкость и сильный обратный параметр не слишком мал.

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

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

[ редактировать ]

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

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

[ редактировать ]

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

См. также

[ редактировать ]
  1. ^ Перейти обратно: а б Венер, С.; К. Шаффнер; Б. Терхал (2008). «Криптография из шумохранилища». Письма о физических отзывах . 100 (22): 220502. arXiv : 0711.2895 . Бибкод : 2008PhRvL.100v0502W . doi : 10.1103/PhysRevLett.100.220502 . ПМИД   18643410 . S2CID   2974264 .
  2. ^ Ло, Х.; Х. Чау (1997). «Действительно ли возможно использование квантовых битов?». Письма о физических отзывах . 78 (17): 3410. arXiv : quant-ph/9603004 . Бибкод : 1997PhRvL..78.3410L . doi : 10.1103/PhysRevLett.78.3410 . S2CID   3264257 .
  3. ^ Ло, Х (1997). «Небезопасность квантово-безопасных вычислений». Физический обзор А. 56 (2): 1154–1162. arXiv : Quant-ph/9611031 . Бибкод : 1997PhRvA..56.1154L . дои : 10.1103/PhysRevA.56.1154 . S2CID   17813922 .
  4. ^ Майерс, Д. (1997). «Безусловно безопасное использование квантовых битов невозможно». Письма о физических отзывах . 78 (17): 3414–3417. arXiv : Quant-ph/9605044 . Бибкод : 1997PhRvL..78.3414M . doi : 10.1103/PhysRevLett.78.3414 . S2CID   14522232 .
  5. ^ Д'Ариано, Дж.; Д. Кречманн; Д. Шлингеманн; РФ Вернер (2007). «Возвращение к квантовым битам: возможное и невозможное». Физический обзор А. 76 (3): 032328. arXiv : quant-ph/0605224 . Бибкод : 2007PhRvA..76c2328D . дои : 10.1103/PhysRevA.76.032328 . S2CID   119340261 .
  6. ^ Маурер, У. (1992). «Условно-совершенная секретность и доказуемо безопасный рандомизированный шифр» . Журнал криптологии . 5 (1): 53––66. дои : 10.1007/bf00191321 . S2CID   12079602 .
  7. ^ Кашен, К.; У. Маурер (1997). «Безусловная безопасность от противников, ограниченных памятью». Труды CRYPTO 1997 : 292–306.
  8. ^ Дзембовский, С.; У. Маурер (2004). «О создании начального ключа в модели с ограниченным хранилищем». Труды EUROCRYPT : 126–137.
  9. ^ Перейти обратно: а б с И., Дамгаард; С. Фер; Л. Сальвей; К. Шаффнер (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 .
  10. ^ Перейти обратно: а б с д Дамгаард, И.; С. Фер; Р. Реннер; Л. Сальвей; К. Шаффнер (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 .
  11. ^ Перейти обратно: а б с д и ж Кениг, Роберт; С. Венер; Дж. Вулшлегер (2009). «Безусловная безопасность от шумного квантового хранилища». Транзакции IEEE по теории информации . 58 (3): 1962–1984. arXiv : 0906.1030 . Бибкод : 2009arXiv0906.1030K . дои : 10.1109/TIT.2011.2177772 . S2CID   12500084 .
  12. ^ Венер, С.; М. Керти; К. Шаффнер; Х. Ло (2010). «Реализация двусторонних протоколов в модели хранения с шумом». Физический обзор А. 81 (5): 052336. arXiv : 0911.2302 . Бибкод : 2010PhRvA..81e2336W . дои : 10.1103/PhysRevA.81.052336 . S2CID   6187112 .
  13. ^ Перейти обратно: а б Мандаям, П.; С. Венер (2011). «Достижение физических пределов модели с ограниченной памятью». Физический обзор А. 83 (2): 022329. arXiv : 1009.1596 . Бибкод : 2011PhRvA..83b2329M . дои : 10.1103/PhysRevA.83.022329 . S2CID   11753298 .
  14. ^ Кениг, Р.; С. Венер (2009). «Сильное обращение к классическому канальному кодированию с использованием запутанных входов». Письма о физических отзывах . 103 (7): 070504. arXiv : 0903.2838 . Бибкод : 2009PhRvL.103g0504K . doi : 10.1103/PhysRevLett.103.070504 . ПМИД   19792627 . S2CID   25002853 .
  15. ^ Берта, М.; Ф. Брандао; М. Кристандл; С. Венер (2013). «Стоимость запутанности квантовых каналов». Транзакции IEEE по теории информации . 59 (10): 6779–6795. arXiv : 1108.5357 . Бибкод : 2011arXiv1108.5357B . дои : 10.1109/TIT.2013.2268533 . S2CID   322613 .
  16. ^ Берта, М.; О. Фаузи; С. Венер (2014). «Квантовые и классические экстракторы случайности». Транзакции IEEE по теории информации . 60 (2): 1168–1192. arXiv : 1111.2026 . Бибкод : 2011arXiv1111.2026B . дои : 10.1109/TIT.2013.2291780 . S2CID   10018325 .
  17. ^ Дамгаард, И.; С. Фер; Л. Сальвей; К. Шаффнер (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 .
  18. ^ Бауман, Н.; С. Фер; К. Гонсалес-Гильен; К. Шаффнер (2011). «Энтропийные отношения неопределенности «все кроме одного» и применение к идентификации на основе пароля». arXiv : 1105.6212 . Бибкод : 2011arXiv1105.6212B . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 73a6979cbeaba8c9a22fe4a6673dc95f__1692900120
URL1:https://arc.ask3.ru/arc/aa/73/5f/73a6979cbeaba8c9a22fe4a6673dc95f.html
Заголовок, (Title) документа по адресу, URL1:
Noisy-storage model - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)