Кодовая маршрутизация: новая атака на проверку местоположения

Кодовая маршрутизация: новая атака на проверку местоположения

Отметка времени: 9 августа 2023 г., 11:18
Маршрутизация кода: новая атака на проверку позиции PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

Джой Кри и Алекс май

Стэнфордский университет

Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.

Абстрактные

Криптографическая задача проверки положения пытается проверить местоположение одной стороны в пространстве-времени, используя ограничения на квантовую информацию и релятивистскую причинность. Популярная схема проверки, известная как $f$-маршрутизация, требует от доказывающего перенаправить квантовую систему на основе значения булевой функции $f$. Стратегии обмана для схемы $f$-маршрутизации требуют, чтобы доказывающая сторона использовала предварительно разделенную запутанность, а безопасность схемы основывается на предположениях о том, какой степенью запутанности может манипулировать доказывающая сторона. Здесь мы даем новую стратегию мошенничества, в которой квантовая система закодирована в схему разделения секретов, а структура авторизации схемы разделения секретов используется для надлежащего управления системой. Эта стратегия завершает задачу $f$-маршрутизации с использованием пар ЭПР $O(SP_p(f))$, где $SP_p(f)$ — минимальный размер программы-расклада над полем $mathbb{Z}_p$, вычисляющей $ ф$. Это показывает, что мы можем эффективно атаковать схемы $f$-маршрутизации всякий раз, когда $f$ находится в классе сложности $text{Mod}_ptext{L}$, после разрешения локальной предварительной обработки. Наилучшая ранняя конструкция достигла класса L, который, как считается, находится строго внутри $text{Mod}_ptext{L}$. Мы также показываем, что размер схемы квантового разделения секрета с индикаторной функцией $f_I$ ограничивает стоимость запутывания $f$-маршрутизации на функции $f_I$.

► Данные BibTeX

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

[1] Нишант Чандран, Випул Гоял, Райан Мориарти и Рафаил Островский. Позиционная криптография. Ежегодная международная криптологическая конференция, страницы 391–407. Springer, 2009. https://​/​doi.org/​10.1007/​978-3-642-03356-8_23.
https:/​/​doi.org/​10.1007/​978-3-642-03356-8_23

[2] Адриан Кент, Уильям Дж. Манро и Тимоти П. Спиллер. Квантовая маркировка: Аутентификация местоположения с помощью квантовой информации и ограничений релятивистской сигнализации. Physical Review A, 84 (1): 012326, 2011. https://​/​doi.org/​10.1103/​PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[3] Адриан Кент. Квантовые задачи в пространстве Минковского. Классическая и квантовая гравитация, 29 (22): 224013, 2012. 10.1088/​0264-9381/​29/​22/​224013.
https:/​/​doi.org/​10.1088/​0264-9381/​29/​22/​224013

[4] Уильям К. Вуттерс и Войцех Х. Зурек. Отдельный квант нельзя клонировать. Nature, 299 (5886): 802–803, 1982. https://​/​doi.org/​10.1038/​299802a0.
https: / / doi.org/ 10.1038 / 299802a0

[5] Адриан П. Кент, Уильям Дж. Манро, Тимоти П. Спиллер и Рэймонд Дж. Босолей. Системы маркировки, 11 июля 2006 г. Патент США 7,075,438 XNUMX XNUMX.

[6] Роберт Малани. Связь, зависящая от местоположения, с использованием квантовой запутанности. Physical Review A, 81 (4): 042319, 2010. https://​/​doi.org/​10.1103/​PhysRevA.81.042319.
https: / / doi.org/ 10.1103 / PhysRevA.81.042319

[7] Гарри Бурман, Нишант Чандран, Серж Фер, Ран Геллес, Випул Гоял, Рафаил Островский и Кристиан Шаффнер. Позиционная квантовая криптография: невозможность и конструкции. SIAM Journal on Computing, 43 (1): 150–178, 2014 г. https://​/​doi.org/​10.1137/​130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Салман Бейджи и Роберт Кениг. Упрощенные мгновенные нелокальные квантовые вычисления с приложениями к позиционной криптографии. New Journal of Physics, 13 (9): 093036, 2011. 10.1088/​1367-2630/​13/​9/​093036.
https:/​/​doi.org/​10.1088/​1367-2630/​13/​9/​093036

[9] Андреас Блюм, Маттиас Кристандль и Флориан Спилман. Протокол проверки позиции одного кубита, защищенный от атак с несколькими кубитами. Nature Physics, стр. 1–4, 2022 г. https://​/​doi.org/​10.1038/​s41567-022-01577-0.
https:/​/​doi.org/​10.1038/​s41567-022-01577-0

[10] Гарри Бурман, Серж Фер, Кристиан Шаффнер и Флориан Спилман. Модель садового шланга. В материалах 4-й конференции «Инновации в теоретической информатике», стр. 145–158, 2013 г. https://​/​doi.org/​10.1145/​2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Хартмут Клаук и Супарта Поддер. Новые границы модели садового шланга. Основы программных технологий и теоретической информатики, 2014. 10.4230/LIPIcs.FSTTCS.2014.481.
https://​/​doi.org/​10.4230/​LIPIcs.FSTTCS.2014.481

[12] Шринивасан Аруначалам и Супарта Поддер. Коммуникационный сувенир: сложность общения без памяти. На 12-й конференции «Инновации в теоретической информатике» (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. 10.4230/​LIPIcs.ITCS.2021.61.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.61

[13] Алекс Мэй. Квантовые задачи в голографии. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https://​/​doi.org/​10.1007/​JHEP10(2019)233.
HTTPS: / / doi.org/ 10.1007 / JHEP10 (2019) 233

[14] Алекс Мэй, Джефф Пенингтон и Джонатан Сорс. Для голографического рассеяния требуется связанный клин запутывания. Журнал физики высоких энергий, 2020 г. (8): 1–34, 2020 г. https://​/​doi.org/​10.1007/​JHEP08(2020)132.
HTTPS: / / doi.org/ 10.1007 / JHEP08 (2020) 132

[15] Алекс Мэй. Сложность и запутанность в нелокальных вычислениях и голографии. Quantum, 6: 864, ноябрь 2022 г. ISSN 2521-327X. 10.22331/​q-2022-11-28-864. URL https://​/​doi.org/​10.22331/​q-2022-11-28-864.
https:/​/​doi.org/​10.22331/​q-2022-11-28-864

[16] Адам Д Смит. Разделение квантового секрета для структур общего доступа. Препринт arXiv quant-ph/​0001087, 2000. https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0001087.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0001087
Arxiv: колич-фот / 0001087

[17] Хуан Малдасена. Предел больших N суперконформных теорий поля и супергравитации. Международный журнал теоретической физики, 38 (4): 1113–1133, 1999. https://​/​doi.org/​10.1023/​A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

[18] Эдвард Виттен. Пространство анти-де-ситтера и голография. Успехи теоретической и математической физики, 2: 253–291, 1998. 10.4310/ATMP.1998.v2.n2.a2.
https:/​/​doi.org/​10.4310/​ATMP.1998.v2.n2.a2

[19] Даниэль Готтесман. Теория квантового обмена секретами. Physical Review A, 61 (4): 042311, 2000. https: //www.doi.org/ 10.1103/ PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[20] Бенджамин Шумахер и Майкл Нильсен. Квантовая обработка данных и исправление ошибок. Physical Review A, 54 (4): 2629, 1996. https://doi.org/10.1103/PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

[21] Бенджамин Шумахер и Майкл Д Уэстморленд. Приблизительная квантовая коррекция ошибок. Квантовая обработка информации, 1 (1): 5–12, 2002 г. https://​/​doi.org/​10.1023/​A:1019653202562.
https: / / doi.org/ 10.1023 / A: 1019653202562

[22] Герхард Бунтрок, Карстен Дамм, Ульрих Хертрампф и Кристоф Мейнель. Структура и важность класса logspace-mod. Математическая теория систем, 25 (3): 223–237, 1992. https://​/​doi.org/​10.1007/​BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Маурисио Карчмер и Ави Вигдерсон. По объему программ. В [1993] Материалы восьмой ежегодной конференции по теории структуры сложности, страницы 102–111. IEEE, 1993. 10.1109/SCT.1993.336536.
https://​/​doi.org/​10.1109/​SCT.1993.336536

[24] Нил Д. Джонс, И. Эдмунд Лиен и Уильям Т. Лаасер. Новые проблемы завершены для недетерминированного пространства журнала. Математическая теория систем, 10 (1): 1–17, 1976. https://​/​doi.org/​10.1007/​BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Клаус Рейнхардт и Эрик Аллендер. Делая недетерминизм однозначным. SIAM Journal on Computing, 29 (4): 1118–1131, 2000. https://​/doi.org/​10.1137/​S0097539798339041.
https: / / doi.org/ 10.1137 / S0097539798339041

[26] Эрик Аллендер, Клаус Рейнхардт и Шию Чжоу. Выделение, сопоставление и подсчет равномерных и неравномерных верхних границ. Журнал компьютерных и системных наук, 59 (2): 164–181, 1999 г. https://​/​doi.org/​10.1006/​jcss.1999.1646.
https: / / doi.org/ 10.1006 / jcss.1999.1646

[27] Эяль Кушилевич. Коммуникативная сложность. В « Достижениях в области компьютеров» , том 44, страницы 331–360. Elsevier, 1997. https://​/​doi.org/​10.1016/​S0065-2458(08)60342-3.
https:/​/​doi.org/​10.1016/​S0065-2458(08)60342-3

[28] Ноам Нисан. Коммуникационная сложность пороговых ворот. Комбинаторика, Полу Эрдосу восемьдесят, 1: 301–315, 1993.

[29] Роберт Робер, Тонианн Питасси, Бенджамин Россман и Стивен Кук. Экспоненциальные нижние оценки для монотонных программ. В 2016 г. состоялся 57-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS), страницы 406–415. IEEE, 2016. 10.1109/​FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Флориан Спилман. Мгновенное нелокальное вычисление квантовых цепей с малой глубиной T. На 11-й конференции по теории квантовых вычислений, связи и криптографии (TQC 2016), том 61 Международного журнала Лейбница по информатике (LIPIcs), страницы 9: 1–9: 24, Дагштуль, Германия, 2016 г. Schloss Dagstuhl-Leibniz- Центр информатики. ISBN 978-3-95977-019-4. 10.4230/LIPIcs.TQC.2016.9.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2016.9

Цитируется

[1] Алекс Мэй, «Сложность и запутанность в нелокальных вычислениях и голографии», Квант 6, 864 (2022).

[2] Алекс Мэй, Джонатан Сорс и Бени Йошида, «Теорема о связном клине и ее следствия», Журнал физики высоких энергий 2022 11, 153 (2022).

[3] Кфир Долев и Сэм Кри, «Голография как ресурс для нелокальных квантовых вычислений», Arxiv: 2210.13500, (2022).

[4] Кфир Долев и Сэм Кри, «Нелокальные вычисления квантовых схем с малыми световыми конусами», Arxiv: 2203.10106, (2022).

[5] Рене Аллерсторфер, Гарри Бурман, Алекс Мэй, Флориан Спилман и Филип Вердуйн Люнель, «Связь нелокальных квантовых вычислений с теоретико-информационной криптографией», Arxiv: 2306.16462, (2023).

[6] Льоренс Эскола-Фаррас и Флориан Спилман, «Протокол проверки квантовой позиции с одним кубитом, устойчивый к потерям, защищенный от запутанных злоумышленников», Arxiv: 2212.03674, (2022).

Приведенные цитаты из САО / НАСА ADS (последнее обновление успешно 2023-08-10 03:31:42). Список может быть неполным, поскольку не все издатели предоставляют подходящие и полные данные о цитировании.

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2023-08-10 03:31:41).

Эта статья опубликована в Quantum под Creative Commons Attribution 4.0 International (CC BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.

Отметка времени:

Больше от Квантовый журнал