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

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

Мітка часу: 19 січня 2023 р., 8:49 ранку

Шалев Бен-Давид1 та Або Саттах2

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

Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.

абстрактний

Рибалка зловив квантову рибу. «Рибалку, відпусти мене, — благала рибка, — і я виконаю тобі три бажання». Рибалка погодився. Риба дала рибалці квантовий комп’ютер, три квантові маркери підпису та свій класичний відкритий ключ. Риба пояснила: «щоб підписати свої три бажання, скористайтеся токенізованою схемою підпису на цьому квантовому комп’ютері, а потім покажіть свій дійсний підпис королю, який винен мені послугу».
Одним із жетонів для підпису рибалка підписав документ «Подаруй мені замок!». і кинувся до палацу. Король виконав класичний алгоритм перевірки, використовуючи відкритий ключ риби, і оскільки він був дійсним, король підкорився.
Дружина рибалки хотіла підписати десять бажань двома жетонами, що залишилися. Рибалка не захотів хитрувати і таємно поплив назустріч рибі. «Рибка, моя дружина хоче підписати ще десять бажань». Але рибка не хвилювалася: «Я навчився квантової криптографії за попереднім оповіданням («Рибалка і його жінка» братів Грімм). Квантові токени споживаються під час підписання. Твоя поліноміальна дружина не може навіть підписати чотири бажання, використовуючи три підписи, які я тобі дав».
"Як це працює?" — здивувався рибалка. «Ви чули про квантові гроші? Це квантові стани, які можна легко перевірити, але важко скопіювати. Ця токенізована схема квантового підпису розширює схему квантових грошей Ааронсона та Крістіано, тому токени підпису неможливо скопіювати».
«Чи має ваша схема додаткові фантастичні властивості?» — запитав рибалка. «Так, схема має інші гарантії безпеки: можливість відкликання, тестування та постійну безпеку. Крім того, якщо ви в морі і ваш квантовий телефон має лише класичний прийом, ви можете скористатися цією схемою, щоб перенести вартість квантових грошей на берег», – сказала рибка і попливла.

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

[Вбудоване вміст]

► Дані BibTeX

► Список літератури

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

[2] Ю. Агаронов, Дж. Анандан, Л. Вайдман. Значення хвильової функції. фіз. Rev. A, 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] Р. Амос, М. Георгіу, А. Кіаяс, М. Жандри. Одноразові підписи та застосування для гібридної квантової/класичної автентифікації. У K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath і J. Chuzhoy, редактори, Матеріали щорічного симпозіуму ACM SIGACT з теорії обчислень, сторінки 255–268. ACM, 2020, Архів Cryptology ePrint: звіт 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Ю. Агаронов та Л. Вайдман. Вимірювання хвилі Шредінгера окремої частинки. Physics Letters A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

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

[8] Ч. Б. Беннетт, Г. Брассард, С. Брейдбарт і С. Візнер. Квантова криптографія, або непідробні токени метро. У Досягнення в криптології, сторінки 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] Н. Бітанський, З. Бракерський, Я. Т. Калай. Конструктивні постквантові редукції. У Y. Dodis і T. Shrimpton, редактори, Advances in Cryptology – CRYPTO 2022 – 42-га щорічна міжнародна конференція з криптології, CRYPTO 2022, Санта-Барбара, Каліфорнія, США, 15-18 серпня 2022 р., матеріали, частина III, том 13509 лекції Notes in Computer Science, сторінки 654–683. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] Н. Бітанскі, Р. Канетті, Х. Кон, С. Голдвассер, Ю. Т. Калай, О. Панет і А. Розен. Неможливість обфускації за допомогою допоміжного введення або універсального симулятора. У JA Garay та R. Gennaro, редактори, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II, том 8617 Lecture Notes in Computer Science, сторінки 71–89. Springer, 2014.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, SP Vadhan і K. Yang. Про (не)можливість обфускації програм. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] Х. Бомбін. Ворота Кліффорда за кодовою деформацією. New Journal of Physics, 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. У T. Johansson і PQ Nguyen, редактори, Advances in Cryptology – EUROCRYPT 2013, 32-а щорічна міжнародна конференція з теорії та застосування криптографічних методів, Афіни, Греція, 26-30 травня 2013 р. Матеріали, том 7881 конспектів лекцій з комп’ютера Наука, сторінки 592–608. Springer, 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] K. Chung, M. Georgiou, C. Lai та V. Zikas. Криптографія з одноразовими бекдорами. Cryptogr., 3(3):22, 2019, Архів Cryptology ePrint: звіт 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] Р. Канетті, Г. Н. Ротблюм і М. Варіа. Обфускація членства в гіперплощині. У D. Micciancio, редактор, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Цюріх, Швейцарія, 9-11 лютого 2010 р. Proceedings, том 5978 Лекційних конспектів з інформатики, сторінки 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

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

[23] Ю. З. Дінь і М. О. Рабін. Гіпершифрування та вічна безпека. У H. Alt і A. Ferreira, редактори, STACS 2002, 19-й щорічний симпозіум з теоретичних аспектів інформатики, Антіб – Жуан-ле-Пен, Франція, 14-16 березня 2002 р., Матеріали, том 2285 конспектів лекцій з інформатики, сторінки 1–26. Springer, 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] Е. Фархі, Д. Госсет, А. Хасидім, А. Лютомірскі, П. Шор. Квантові гроші з вузлів. У матеріалах конференції 3rd Innovations in Theoretical Computer Science, сторінки 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] Д. Гавінського. Квантові гроші з класичною перевіркою. На 27-й щорічній конференції IEEE з обчислювальної складності, сторінки 42–52. IEEE, 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] М. Георгіу та І. Керенідіс. Нові будівництва за квантові гроші. У S. Beigi та R. König, редактори, 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] О. Голдрайх. Основи криптографії – Том. 2, Основні програми. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler і T. Beth. Ефективні квантові схеми для некубітових квантових кодів з виправленням помилок. Міжн. Ж. Знайдено. обчис. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

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

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

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

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas і L. Perret. Неквантовий криптоаналіз галасливої ​​версії квантово-грошової схеми Ааронсона-Крістіано. IET Information Security, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère та L. Perret. Алгебраїчний криптоаналіз схеми квантових грошей. Випадок без шуму. У J. Katz, редактор, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30 – April 1, 2015, Proceedings, том 9020 Лекційних конспектів в інформатиці, сторінки 194–213. Springer, 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, arXiv: 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 із застосуванням до Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

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

[42] О. Шмуелі. Відкритий ключ Quantum money з класичним банком. У С. Леонарді та А. Гупта, редактори, STOC '22: 54-й щорічний симпозіум ACM SIGACT з теорії обчислень, Рим, Італія, 20–24 червня 2022 р., сторінки 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] О. Шмуелі. Напівквантові токенізовані підписи. У Y. Dodis і T. Shrimpton, редактори, Advances in Cryptology – CRYPTO 2022 – 42-а щорічна міжнародна конференція з криптології, CRYPTO 2022, Санта-Барбара, Каліфорнія, США, 15-18 серпня 2022 р., матеріали, частина I, том 13507 лекції Notes in Computer Science, сторінки 296–319. Springer, 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] Д. Унру. Відкличне шифрування Quantum Timed-Release. 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-z

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

[49] WK Wootters і WH Zurek. Окремий квант неможливо клонувати. Nature, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell і MJ Sellars. Оптично адресовані ядерні спіни в твердому тілі з шестигодинним часом когерентності. 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-x
arXiv: 1711.02276

Цитується

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

[2] Дуглас Скотт, «Наукові обмани, фізичні витівки та астрономічні витівки», arXiv: 2103.17057.

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

[4] Або Саттах, «Квантово-розважливі контракти із застосуванням до біткойнів», 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] Jiahui Liu, Hart Montgomery та Mark Zhandry, «Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More», 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.

Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2023-01-20 14:01:05). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.

On Служба, на яку посилається Crossref даних про цитування робіт не знайдено (остання спроба 2023-01-20 14:01:00).

Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.

Часова мітка:

Більше від Квантовий журнал