Квантовые токены для цифровых подписей

Квантовые токены для цифровых подписей

Отметка времени: 19 января 2023 г., 8:49

Шалев Бен-Давид1 и Или Саттат2

1Университет Ватерлоо, Школа компьютерных наук Дэвида Р. Черитона
2Университет Бен-Гуриона в Негеве, факультет компьютерных наук

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

Абстрактные

Рыбак поймал квантовую рыбу. «Рыбак, пожалуйста, отпусти меня, — умоляла рыба, — и я исполню три твоих желания». Рыбак согласился. Рыба дала рыбаку квантовый компьютер, три токена квантовой подписи и его классический открытый ключ. Рыба объяснила: «Чтобы подписать свои три желания, используйте схему токенизированной подписи на этом квантовом компьютере, а затем покажите свою действительную подпись королю, который должен мне услугу».
Рыбак использовал один из жетонов подписи, чтобы подписать документ «Дайте мне замок!» и бросился во дворец. Король выполнил классический алгоритм проверки, используя открытый ключ рыбы, и, поскольку он был действительным, король подчинился.
Жена рыбака хотела подписать десять желаний двумя оставшимися жетонами. Рыбак не хотел обманывать и тайно поплыл навстречу рыбе. «Рыбка, моя жена хочет подписать еще десять желаний». Но рыбку это не волновало: «Квантовую криптографию я выучил по предыдущему рассказу («Рыбак и его жена» братьев Гримм). Квантовые токены расходуются во время подписания. Твоя полиномиальная жена не может даже подписать четыре желания, используя три жетона подписи, которые я тебе дал».
"Как это работает?" — удивился рыбак. «Вы слышали о квантовых деньгах? Это квантовые состояния, которые легко проверить, но трудно скопировать. Эта токенизированная схема квантовой подписи расширяет схему квантовых денег Ааронсона и Кристиано, поэтому подписные токены нельзя скопировать».
«Есть ли у вашей схемы дополнительные причудливые свойства?» — спросил рыбак. «Да, у схемы есть и другие гарантии безопасности: возможность отзыва, возможность тестирования и постоянная безопасность. Кроме того, если вы находитесь в море и ваш квантовый телефон принимает только классический сигнал, вы можете использовать эту схему для перевода стоимости квантовых денег на берег», — сказала рыба и уплыла.

Квантовые токены для цифровых подписей PlatoBlockchain Data Intelligence. Вертикальный поиск. Ай.

[Встраиваемое содержимое]

► Данные BibTeX

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

[1] С. Ааронсон. Квантовая защита от копирования и квантовые деньги. В материалах 24-й ежегодной конференции IEEE по вычислительной сложности, CCC 2009, Париж, Франция, 15–18 июля 2009 г., страницы 229–242, 2009 г.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Ю. Ааронов, Дж. Анандан и Л. Вайдман. Смысл волновой функции. физ. Ред. А, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] С. Ааронсон и П. Кристиано. Квантовые деньги из скрытых подпространств. В материалах 44-го симпозиума по теории вычислительной конференции, STOC 2012, Нью-Йорк, штат Нью-Йорк, США, 19–22 мая 2012 г., страницы 41–60, 2012 г.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] С. Ааронсон и П. Кристиано. Квантовые деньги из скрытых подпространств. Теория вычислительной техники, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] Р. Амос, М. Георгиу, А. Киайяс и М. Жандри. Одноразовые подписи и приложения для гибридной квантовой/классической аутентификации. К. Макарычев, Ю. Макарычев, М. Тулсиани, Г. Камат и Дж. Чужой, редакторы, Труды ежегодного симпозиума ACM SIGACT по теории вычислений, стр. 255–268. ACM, 2020, Cryptology ePrint Archive: Report 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Ю. Ааронов и Л. Вайдман. Измерение волны Шредингера одиночной частицы. Письма по физике А, 178 (1): 38–42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] Б. Барак. Надежды, страхи и программная обфускация. коммун. АКМ, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart и S. Wiesner. Квантовая криптография, или жетоны метро, ​​которые невозможно подделать. В Достижениях в области криптологии, страницы 267–275. Спрингер, 1983 год.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] Н. Битанский, З. Бракерский и Ю. Т. Калай. Конструктивные постквантовые редукции. В И. Додис и Т. Шримптон, редакторы, Достижения в криптологии - КРИПТО 2022 - 42-я ежегодная международная криптологическая конференция, КРИПТО 2022, Санта-Барбара, Калифорния, США, 15-18 августа 2022 г., Труды, часть III, том 13509 лекции Заметки по информатике, страницы 654–683. Спрингер, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] Н. Битанский, Р. Канетти, Х. Кон, С. Гольдвассер, Ю. Т. Калай, О. Панет и А. Розен. Невозможность обфускации с помощью вспомогательного ввода или универсального симулятора. В Дж. А. Гарай и Р. Дженнаро, редакторы, Достижения в криптологии - КРИПТО 2014 - 34-я ежегодная конференция по криптологии, Санта-Барбара, Калифорния, США, 17–21 августа 2014 г., Труды, часть II, том 8617 лекций по информатике, страницы 71–89. Спрингер, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] Б. Барак, О. Гольдрейх, Р. Импальяццо, С. Рудич, А. Сахай, С. П. Вадхан и К. Ян. О (не)возможности запутывания программ. Журнал ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] Х. Бомбин. Ворота Клиффорда с помощью деформации кода. Новый журнал физики, 13(4):043005, 2011.
https:/​/​doi.org/​10.1088/​1367-2630/​13/​4/​043005
http:/​/​stacks.iop.org/​1367-2630/​13/​i=4/​a=043005

[13] Г. Брассар. Поиск в квантовой телефонной книге. Наука, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] А. Бехера, О. Саттах и ​​У. Шинар. Помехоустойчивые квантовые токены для MAC, 2021 г.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] Д. Бонэ и М. Жандри. Коды аутентификации сообщений Quantum-Secure. Т. Йоханссон и П. К. Нгуен, редакторы, «Достижения в криптологии — EUROCRYPT 2013», 32-я ежегодная международная конференция по теории и применению криптографических методов, Афины, Греция, 26–30 мая 2013 г. Труды, том 7881 лекций по компьютерам Наука, страницы 592–608. Спрингер, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] Р. Клив и Д. Готтесман. Эффективные вычисления кодировок для квантовой коррекции ошибок. физ. Rev. A, 56:76–82, июль 1997 г.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] К. Чанг, М. Георгиу, К. Лай и В. Зикас. Криптография с одноразовыми бэкдорами. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] П. Кристиано. Личное общение, 2015.

[19] А. Коладанжело, Дж. Лю, К. Лю и М. Жандри. Скрытые классы и приложения к неклонируемой криптографии, 2021 г., arXiv: 2107.05692.
Arxiv: 2107.05692

[20] С. Чакраборти, Дж. Радхакришнан и Н. Рагунатан. Границы уменьшения ошибок с помощью нескольких квантовых запросов. В книге «Аппроксимация, рандомизация и комбинаторная оптимизация, алгоритмы и методы», 8-й Международный семинар по алгоритмам аппроксимации для задач комбинаторной оптимизации, APPROX 2005 и RANDOM 2005, Беркли, Калифорния, США, 22–24 августа 2005 г., Труды, страницы 245–256, 2005 г. .
https: / / doi.org/ 10.1007 / 11538462_21

[21] Р. Канетти, Г. Н. Ротблюм и М. Вариа. Обфускация принадлежности к гиперплоскости. В Д. Мичиансио, редактор, Теория криптографии, 7-я конференция по теории криптографии, TCC 2010, Цюрих, Швейцария, 9–11 февраля 2010 г. Труды, том 5978 лекций по информатике, страницы 72–89. Спрингер, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] В. Диффи и М. Е. Хеллман. Новые направления в криптографии. IEEE транс. Теория информации, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] Ю.З. Дин и М.О. Рабин. Гипершифрование и вечная безопасность. В H. Alt и A. Ferreira, редакторы, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, France, 14-16 марта 2002 г., Proceedings, volume 2285 of Lecture Notes in Computer Science, стр. 1–26. Спрингер, 2002.
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[24] Э. Фархи, Д. Госсет, А. Хассидим, А. Лютомирски, Д. Нагай и П. Шор. Квантовое восстановление состояния и однокопийная томография основных состояний гамильтонианов. физ. Rev. Lett., 105:190503, ноябрь 2010 г.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] Э. Фархи, Д. Госсет, А. Хасидим, А. Лютомирски и П. Шор. Квантовые деньги из узлов. В материалах 3-й конференции «Инновации в теоретической информатике», страницы 276–289. АКМ, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] Д. Гавински. Квантовые деньги с классической проверкой. На 27-й ежегодной конференции IEEE по вычислительной сложности, стр. 42–52. ИИЭР, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] С. Гольдвассер и Ю. Т. Калай. О невозможности запутывания вспомогательным вводом. На 46-м ежегодном симпозиуме IEEE по основам компьютерных наук (FOCS 2005), 23–25 октября 2005 г., Питтсбург, Пенсильвания, США, Труды, стр. 553–562, 2005 г.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] М. Георгиу и И. Керенидис. Новые конструкции для квантовых денег. В С. Бейги и Р. Кениг, редакторы, 10-я конференция по теории квантовых вычислений, связи и криптографии, TQC 2015, 20–22 мая 2015 г., Брюссель, Бельгия, том 44 LIPics, страницы 92–110. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] О. Гольдрейх. Основы криптографии - Vol. 2, Основные приложения. Издательство Кембриджского университета, 2004.

[30] М. Грассл, М. Рёттелер и Т. Бет. Эффективные квантовые схемы для некубитных квантовых кодов с исправлением ошибок. Междунар. Дж. Найден. вычисл. наук, 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] Дж. Кац и Ю. Линделл. Введение в современную криптографию, второе издание. CRC Press, 2014.

[32] Н. А. Линч. Распределенные алгоритмы. Морган Кауфманн, 1996 год.

[33] М. Моска и Д. Стебила. Квантовые монеты, том 523 Contemp. Матем., стр. 35–47. амер. Мат. Соц., 2010.

[34] М. С. Пена, Р. Д. Диас, Дж. Фожер, Л. Х. Энсинас и Л. Перре. Неквантовый криптоанализ зашумленной версии схемы квантовых денег Ааронсона-Кристиано. Информационная безопасность ИЭПП, 13(4):362–366, 2019 г.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] М. С. Пена, Ж. Фожер и Л. Перре. Алгебраический криптоанализ схемы квантовых денег. Бесшумный случай. В Дж. Кац, редактор, Криптография с открытым ключом - PKC 2015 - 18-я Международная конференция IACR по практике и теории криптографии с открытым ключом, Гейтерсберг, Мэриленд, США, 30 марта - 1 апреля 2015 г., Труды, том 9020 лекций. в области компьютерных наук, страницы 194–213. Спрингер, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] А. Прасад. Подсчет подпространств конечного векторного пространства — 1. Резонанс, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] Ф. Паставски, Н.Ю. Яо, Л. Цзян, М.Д. Лукин и Дж.И. Сирак. Не подделываемые шумоустойчивые квантовые токены. Труды Национальной академии наук, 109(40):16079–16082, 2012 г.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] Р. Радиан и О. Саттах. Полуквантовые деньги. В материалах 1-й конференции ACM по достижениям в области финансовых технологий, AFT 2019, Цюрих, Швейцария, 21–23 октября 2019 г., страницы 132–146. ACM, 2019, архив: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
Arxiv: 1908.08889

[39] Р. Радиан и О. Саттах. Полуквантовые деньги. Журнал криптологии, 35(2), январь 2022 г., arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
Arxiv: 1908.08889

[40] О. Саттах. Quantum Prudent Contracts с приложениями к биткойнам, 2022 г.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] О. Саттах. Неклонируемая криптография, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] О. Шмуэли. Квантовые деньги с открытым ключом в классическом банке. В С. Леонарди и А. Гупта, редакторы, STOC '22: 54-й ежегодный симпозиум ACM SIGACT по теории вычислений, Рим, Италия, 20–24 июня 2022 г., страницы 790–803. АКМ, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] О. Шмуэли. Полуквантовые токенизированные подписи. В Й. Додис и Т. Шримптон, редакторы, Достижения в криптологии - КРИПТО 2022 - 42-я ежегодная международная криптологическая конференция, КРИПТО 2022, Санта-Барбара, Калифорния, США, 15-18 августа 2022 г., Труды, часть I, том 13507 лекции Заметки по информатике, страницы 296–319. Спрингер, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] Т. Тулси, Л. К. Гровер и А. Патель. Новый алгоритм квантового поиска с фиксированной точкой. Квантовая информация и вычисления, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Ю. Токунага, Т. Окамото и Н. Имото. Анонимные квантовые деньги. На конференции ERATO по квантовой информатике, 2003 г.

[46] Д. Унру. Отзывное квантовое шифрование с временным выпуском. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] Д. Унру. Вечные многосторонние вычисления. J. Cryptol., 31(4):965–1011, 2018.
HTTPS: / / doi.org/ 10.1007 / s00145-018-9278-г

[48] С. Виснер. Сопряженное кодирование. Новости ACM Sigact, 15 (1): 78–88, 1983.
https: / / doi.org/ 10.1145 / 1008908.1008920

[49] В. К. Вуттерс и В. Х. Зурек. Отдельный квант нельзя клонировать. Природа, 299 (5886): 802–803, 1982.

[50] М. Чжун, М. П. Хеджес, Р. Л. Алефельдт, Дж. Г. Варфоломей, С. Э. Биван, С. М. Виттиг, Дж. Дж. Лонгделл и М. Дж. Селларс. Оптически адресуемые ядерные спины в твердом теле с шестичасовым временем когерентности. Nature, 517(7533):177–180, январь 2015 г.
https: / / doi.org/ 10.1038 / nature14025

[51] М. Жандри. Квантовая молния никогда не поражает одно и то же состояние дважды, 2017 г., arXiv: 1711.02276.
Arxiv: 1711.02276

[52] М. Жандри. Квантовая молния никогда не поражает одно и то же состояние дважды. Или: Квантовые деньги из криптографических предположений. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
HTTPS: / / doi.org/ 10.1007 / s00145-020-09372-х
Arxiv: 1711.02276

Цитируется

[1] С. Пирандола, У.Л. Андерсен, Л. Банки, М. Берта, Д. Бунандар, Р. Колбек, Д. Инглунд, Т. Геринг, К. Лупо, К. Оттавиани, Дж. Л. Перейра, М. Разави, Дж. Шамсул Шаари, М. Томамичел, В. С. Усенко, Г. Валлоне, П. Виллорези и П. Уолден, «Достижения в области квантовой криптографии», Достижения в оптике и фотонике 12 4, 1012 (2020).

[2] Дуглас Скотт, «Научные розыгрыши, физические розыгрыши и астрономические выходки», Arxiv: 2103.17057.

[3] Томас Видик и Тина Чжан, «Классические доказательства квантового знания», Arxiv: 2005.01691.

[4] Ор Саттах, «Quantum Prudent Contracts with Applications to Bitcoin», Arxiv: 2204.12806.

[5] Скотт Ааронсон, Цзяхуи Лю, Ципэн Лю, Марк Чандри и Руиже Чжан, «Новые подходы к квантовой защите от копирования», Arxiv: 2004.09674.

[6] Рой Радиан и Ор Саттах, «Полуквантовые деньги», Arxiv: 1908.08889.

[7] Андреа Коладанжело, Шафи Голдвассер и Умеш Вазирани, «Отрицаемое шифрование в квантовом мире», Arxiv: 2112.14988.

[8] Прабханджан Анант и Роландо Л. Ла Плака, «Безопасный лизинг программного обеспечения», Arxiv: 2005.05289.

[9] Ор Саттат и Шай Выборски, «Неклонируемые дешифраторы от квантовой защиты от копирования», Arxiv: 2203.05866.

[10] Андреа Коладанжело и Ор Саттат, «Квантовые деньги — решение проблемы масштабируемости блокчейна», Arxiv: 2002.11998.

[11] Джиахуи Лю, Харт Монтгомери и Марк Чандри, «Еще один раунд взлома и зарабатывания квантовых денег: как не строить их из решеток и не только», Arxiv: 2211.11994.

[12] Андреа Коладанжело, Цзяхуи Лю, Ципэн Лю и Марк Жандри, «Скрытые классы смежности и приложения к неклонируемой криптографии», Arxiv: 2107.05692.

[13] Ор Саттах, «Неклонируемая криптография», Arxiv: 2210.14265.

[14] Амит Бехера и Ор Саттах, «Почти публичные квантовые монеты», Arxiv: 2002.12438.

[15] Энн Бродбент, Севаг Гарибян и Хун-Шенг Чжоу, «К квантовым одноразовым воспоминаниям из аппаратного обеспечения без состояния», Arxiv: 1810.05226.

[16] Нирадж Кумар, «Практически осуществимые надежные квантовые деньги с классической проверкой», Arxiv: 1908.04114.

[17] Ор Саттах и ​​Уриэль Шинар, «Квантовая амнезия оставляет криптографические сувениры: заметка о квантовом скептицизме», Arxiv: 2212.08750.

[18] Нир Битанский, Звика Бракерски и Яэль Тауман Калай, «Конструктивные постквантовые редукции», Arxiv: 2203.02314.

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

On Цитируемый сервис Crossref Данные о цитировании работ не найдены (последняя попытка 2023-01-20 14:01:00).

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

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

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