Quantum Tokens för digitala signaturer

Quantum Tokens för digitala signaturer

Tidsstämpel: 19 januari 2023 8:49
Källnod: 1908311

Shalev Ben-David1 och Eller Sattath2

1University of Waterloo, David R. Cheriton School of Computer Science
2Ben-Gurion University of the Negev, Institutionen för datavetenskap

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Fiskaren fångade en kvantfisk. "Fiskare, låt mig gå", bad fisken, "och jag kommer att ge dig tre önskningar". Fiskaren höll med. Fisken gav fiskaren en kvantdator, tre kvantsigneringssymboler och hans klassiska publika nyckel. Fisken förklarade: "för att underteckna dina tre önskningar, använd det tokeniserade signaturschemat på denna kvantdator och visa sedan din giltiga signatur för kungen, som är skyldig mig en tjänst".
Fiskaren använde en av signaturpolletterna för att underteckna dokumentet "ge mig ett slott!" och rusade till palatset. Kungen utförde den klassiska verifieringsalgoritmen med hjälp av fiskens publika nyckel, och eftersom den var giltig följde kungen.
Fiskarens fru ville skriva på tio önskningar med hjälp av deras två återstående signeringspolletter. Fiskaren ville inte fuska och seglade i smyg för att möta fisken. "Fish, min fru vill skriva på tio önskningar till". Men fisken var inte orolig: ”Jag har lärt mig kvantkryptografi efter föregående berättelse (Fiskeren och hans fru av bröderna Grimm). Kvanttokensen förbrukas under signeringen. Din polynomhustru kan inte ens skriva under fyra önskningar med de tre signeringstecknen jag gav dig”.
"Hur fungerar det?" undrade fiskaren. "Har du hört talas om kvantpengar? Dessa är kvanttillstånd som lätt kan verifieras men som är svåra att kopiera. Detta tokeniserade kvantsignaturschema utökar Aaronsons och Christianos kvantpengarschema, vilket är anledningen till att signatursymbolerna inte kan kopieras”.
"Har ditt schema ytterligare snygga egenskaper?" frågade fiskaren. "Ja, systemet har andra säkerhetsgarantier: återkallbarhet, testbarhet och evig säkerhet. Dessutom, om du är till sjöss och din kvanttelefon bara har klassisk mottagning, kan du använda detta schema för att överföra värdet av kvantpengarna till land”, sa fisken och simmade iväg.

[Inbäddat innehåll]

► BibTeX-data

► Referenser

[1] S. Aaronson. Quantum Copy-Protection och Quantum Money. I Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, Frankrike, 15-18 juli 2009, sidorna 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan och L. Vaidman. Betydelsen av vågfunktionen. Phys. Rev. A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson och P. Christiano. Kvantpengar från dolda delutrymmen. I Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19 – 22 maj 2012, sidorna 41–60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson och P. Christiano. Kvantpengar från dolda delrum. Theory of Computing, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias och M. Zhandry. One-shot signaturer och applikationer för hybrid kvant/klassisk autentisering. I K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath och J. Chuzhoy, redaktörer, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing, sidorna 255–268. ACM, 2020, Cryptology ePrint Archive: Rapport 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov och L. Vaidman. Mätning av Schrödingervågen för en enda partikel. Physics Letters A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Förhoppningar, rädslor och mjukvaruförvirring. Commun. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart och S. Wiesner. Kvantkryptografi, eller oförglömliga tunnelbanesymboler. I Advances in Cryptology, sidorna 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski och YT Kalai. Konstruktiva postkvantreduktioner. I Y. Dodis och T. Shrimpton, redaktörer, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15-18 augusti 2022, Proceedings, Del III, volym 13509 av föreläsning Notes in Computer Science, sidorna 654–683. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] N. Bitansky, R. Canetti, H. Cohn, S. Goldwasser, YT Kalai, O. Paneth och A. Rosen. Omöjligheten att fördunkla med hjälpingång eller en universell simulator. I JA Garay och R. Gennaro, redaktörer, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, USA, 17-21 augusti 2014, Proceedings, Part II, volym 8617 av Lecture Notes in Computer Science, sidorna 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 och K. Yang. Om (o)möjligheten att fördunkla program. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombin. Clifford-portar genom koddeformation. 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] G. Brassard. Söka efter en kvanttelefonbok. Science, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] A. Behera, O. Sattath och U. Shinar. Noise-tolerant Quantum Tokens för MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh och M. Zhandry. Quantum-Secure Message Authentication Codes. I T. Johansson och PQ Nguyen, redaktörer, Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aten, Grekland, 26-30 maj 2013. Proceedings, volym 7881 of Lecture Notes in Computer Vetenskap, sidorna 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve och D. Gottesman. Effektiva beräkningar av kodningar för kvantfelskorrigering. Phys. Upp. A, 56:76–82, juli 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai och V. Zikas. Kryptografi med engångsbakdörrar. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] P. Christiano. Personlig kommunikation, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu och M. Zhandry. Dolda cosets och applikationer för oklonbar kryptografi, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan och N. Raghunathan. Gränser för felminskning med få kvantfrågor. I Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 och RANDOM 2005, Berkeley, CA, USA, 22-24 augusti, 2005, 245, 256, 2005, Procedur .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum och M. Varia. Obfuskering av Hyperplane-medlemskap. I D. Micciancio, redaktör, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zürich, Schweiz, 9-11 februari 2010. Proceedings, volym 5978 av Lecture Notes in Computer Science, sidorna 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie och MIG Hellman. Nya riktningar inom kryptografi. IEEE Trans. Information Theory, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding och MO Rabin. Hyperkryptering och evig säkerhet. I H. Alt och A. Ferreira, redaktörer, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, Frankrike, 14-16 mars 2002, Proceedings, volym 2285 av Lecture Notes in Computer Science, sidorna 1–26. Springer, 2002.
https:/​/​doi.org/​10.1007/​3-540-45841-7_1

[24] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, D. Nagaj och P. Shor. Quantum State Restoration and Single-Copy Tomography for Ground States of Hamiltonians. Phys. Rev. Lett., 105:190503, nov 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski och P. Shor. Kvantpengar från knutar. I Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, sidorna 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gavinsky. Kvantpengar med klassisk verifiering. I IEEE 27th Annual Conference on Computational Complexity, sidorna 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser och YT Kalai. Om omöjligheten att obfuskera med hjälpinmatning. I 46:e årliga IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 ​​oktober 2005, Pittsburgh, PA, USA, Proceedings, sidorna 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou och I. Kerenidis. Nya konstruktioner för kvantpengar. I S. Beigi och R. König, redaktörer, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, 20-22 maj 2015, Bryssel, Belgien, volym 44 av LIPIcs, sidorna 92–110. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2015.
https: / ⠀ </ ⠀ <doi.org/†<10.4230 / ⠀ <LIPIcs.TQC.2015.92

[29] O. Goldreich. The Foundations of Cryptography - Vol. 2, grundläggande applikationer. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler och T. Beth. Effektiva kvantkretsar för icke-Qubit Quantum felkorrigerande koder. Int. J. Funnet. Comput. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz och Y. Lindell. Introduktion till modern kryptografi, andra upplagan. CRC Press, 2014.

[32] NA Lynch. Distribuerade algoritmer. Morgan Kaufmann, 1996.

[33] M. Mosca och D. Stebila. Kvantmynt, volym 523 av Contemp. Math., sidorna 35–47. Amer. Matematik. Soc., 2010.

[34] MC Pena, RD Diaz, J. Faugère, LH Encinas och L. Perret. Icke-kvantkrypteringsanalys av den bullriga versionen av Aaronson-Christianos Quantum Money Scheme. IET Information Security, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère och L. Perret. Algebraisk krypteringsanalys av ett kvantpengarschema Det brusfria fallet. I J. Katz, redaktör, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, 30 mars – 1 april 2015, Proceedings, volym 9020 av Lecture Notes i datavetenskap, sidorna 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Räkna delrum i ett ändligt vektorrum — 1. Resonance, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski, NY Yao, L. Jiang, MD Lukin och JI Cirac. Oförfalsbara brustoleranta kvanttokens. Proceedings of the National Academy of Sciences, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian och O. Sattath. Semi-kvantpengar. I Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zürich, Schweiz, 21–23 oktober 2019, sidorna 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] R. Radian och O. Sattath. Semi-kvantpengar. Journal of Cryptology, 35(2), januari 2022, arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv: 1908.08889

[40] O. Sattath. Quantum Prudent Contracts with Applications to Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. Okloningsbar kryptografi, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Offentlig nyckel Quantum pengar med en klassisk bank. I S. Leonardi och A. Gupta, redaktörer, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rom, Italien, 20–24 juni 2022, sidorna 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Shmueli. Semi-quantum tokeniserade signaturer. I Y. Dodis och T. Shrimpton, redaktörer, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15-18 augusti 2022, Proceedings, Del I, volym 13507 av föreläsning Notes in Computer Science, sidorna 296–319. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover och A. Patel. En ny algoritm för kvantsökning med fast punkt. Quantum Information & Computation, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto och N. Imoto. Anonyma kvantpengar. I ERATO Conference on Quantum Information Science, 2003.

[46] D. Unruh. Återkallbar Quantum Timed-Release-kryptering. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] D. Unruh. Evig beräkning med flera partier. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

[48] S. Wiesner. Konjugatkodning. ACM Sigact News, 15 (1): 78–88, 1983.
https: / / doi.org/ 10.1145 / 1008908.1008920

[49] WK Wootters och WH Zurek. Ett enda kvantum kan inte klonas. Nature, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell och MJ Sellars. Optiskt adresserbar kärnkraftssnurr i ett fast material med en koherenstid på sex timmar. Nature, 517(7533):177–180, jan 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M. Zhandry. Kvantblixten slår aldrig ner i samma tillstånd två gånger, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Kvantblixten slår aldrig ner i samma tillstånd två gånger. Eller: Kvantpengar från kryptografiska antaganden. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Citerad av

[1] S. Pirandola, UL Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, JL Pereira, M. Razavi, J. Shamsul Shaari, M. Tomamichel, VC Usenko, G. Vallone, P. Villoresi och P. Wallden, "Advances in quantum cryptography", Framsteg inom optik och fotonik 12 4, 1012 (2020).

[2] Douglas Scott, "Science Spoofs, Physics Pranks and Astronomical upptåg", arXiv: 2103.17057.

[3] Thomas Vidick och Tina Zhang, "Klassiska bevis på kvantkunskap", arXiv: 2005.01691.

[4] Eller Sattath, "Quantum Prudent Contracts with Applications to Bitcoin", arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry och Ruizhe Zhang, "New Approaches for Quantum Copy-Protection", arXiv: 2004.09674.

[6] Roy Radian och Or Sattath, "Semi-Quantum Money", arXiv: 1908.08889.

[7] Andrea Coladangelo, Shafi Goldwasser och Umesh Vazirani, "Deniable Encryption in a Quantum World", arXiv: 2112.14988.

[8] Prabhanjan Ananth och Rolando L. La Placa, "Secure Software Leasing", arXiv: 2005.05289.

[9] Eller Sattath och Shai Wyborski, "Uncloneable Decryptors from Quantum Copy-Protection", arXiv: 2203.05866.

[10] Andrea Coladangelo och Or Sattath, "A Quantum Money Solution to the Blockchain Scalability Problem", arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery och Mark Zhandry, "Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More", arXiv: 2211.11994.

[12] Andrea Coladangelo, Jiahui Liu, Qipeng Liu och Mark Zhandry, "Hidden Cosets and Applications to Unclonable Cryptography", arXiv: 2107.05692.

[13] Eller Sattath, "Oklonbar kryptografi", arXiv: 2210.14265.

[14] Amit Behera och Or Sattath, "Nästan offentliga kvantmynt", arXiv: 2002.12438.

[15] Anne Broadbent, Sevag Gharibian och Hong-Sheng Zhou, "Mot Quantum One-Time Memories from Stateless Hardware", arXiv: 1810.05226.

[16] Niraj Kumar, "Praktiskt genomförbart robusta kvantpengar med klassisk verifiering", arXiv: 1908.04114.

[17] Eller Sattath och Uriel Shinar, "Quantum Amnesia Leaves Cryptographic Mementos: A Note on Quantum Skepticism", arXiv: 2212.08750.

[18] Nir Bitansky, Zvika Brakerski och Yael Tauman Kalai, "Constructive Post-Quantum Reductions", arXiv: 2203.02314.

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2023-01-20 14:01:05). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2023-01-20 14:01:00).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal