Quantum Tokens für digitale Signaturen

Quantum Tokens für digitale Signaturen

Zeitstempel: 19. Januar 2023, 8:49 Uhr
Quellknoten: 1908311

Shalev Ben-David1 und Oder Sattath2

1Universität Waterloo, David R. Cheriton School of Computer Science
2Ben-Gurion-Universität des Negev, Fachbereich Informatik

Findest du dieses Paper interessant oder möchtest du darüber diskutieren? Scite oder hinterlasse einen Kommentar zu SciRate.

Abstrakt

Der Fischer hat einen Quantenfisch gefangen. „Fischer, bitte lass mich gehen“, bat der Fisch, „und ich erfülle dir drei Wünsche“. Der Fischer stimmte zu. Der Fisch gab dem Fischer einen Quantencomputer, drei Quanten-Signatur-Token und seinen klassischen öffentlichen Schlüssel. Der Fisch erklärte: „Um Ihre drei Wünsche zu unterschreiben, verwenden Sie das Token-Signaturschema auf diesem Quantencomputer und zeigen Sie dann Ihre gültige Unterschrift dem König, der mir einen Gefallen schuldet“.
Der Fischer benutzte einen der Unterschriftsmarken, um das Dokument „Gib mir eine Burg!“ zu unterschreiben. und eilte zum Palast. Der König führte den klassischen Verifikationsalgorithmus mit dem öffentlichen Schlüssel des Fisches aus, und da dieser gültig war, willigte der König ein.
Die Frau des Fischers wollte mit ihren zwei verbliebenen Unterschriftsmarken zehn Wünsche unterschreiben. Der Fischer wollte nicht schummeln und segelte heimlich dem Fisch entgegen. „Fisch, meine Frau will noch zehn Wünsche unterschreiben“. Aber der Fisch war unbesorgt: „Ich habe die Quantenkryptographie nach der vorherigen Geschichte (Der Fischer und seine Frau von den Brüdern Grimm) gelernt. Die Quanten-Token werden während des Signierens verbraucht. Ihre polynomische Frau kann nicht einmal vier Wünsche mit den drei Unterschriftsmarken unterschreiben, die ich Ihnen gegeben habe.
"Wie funktioniert es?" fragte sich der Fischer. „Hast du schon mal von Quantengeld gehört? Das sind Quantenzustände, die sich leicht verifizieren lassen, aber schwer zu kopieren sind. Dieses tokenisierte Quantensignaturschema erweitert das Quantengeldschema von Aaronson und Christiano, weshalb die Signaturtoken nicht kopiert werden können.“
„Hat Ihr Schema zusätzliche ausgefallene Eigenschaften?“ fragte der Fischer. „Ja, das Schema hat andere Sicherheitsgarantien: Widerrufbarkeit, Prüfbarkeit und ewige Sicherheit. Wenn Sie außerdem auf See sind und Ihr Quantentelefon nur klassischen Empfang hat, können Sie dieses Schema nutzen, um den Wert des Quantengeldes an Land zu transferieren“, sagte der Fisch und schwamm davon.

[Eingebetteten Inhalt]

► BibTeX-Daten

► Referenzen

[1] S. Aaronson. Quanten-Kopierschutz und Quantengeld. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, Frankreich, 15.–18. Juli 2009, Seiten 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan und L. Vaidman. Bedeutung der Wellenfunktion. Phys. Rev. A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson und P. Christiano. Quantengeld aus verborgenen Unterräumen. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19. – 22. Mai 2012, Seiten 41–60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson und P. Christiano. Quantengeld aus verborgenen Unterräumen. Theory of Computing, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias und M. Zhandry. One-Shot-Signaturen und Anwendungen für hybride Quanten-/​klassische Authentifizierung. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath und J. Chuzhoy, Herausgeber, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing, Seiten 255–268. ACM, 2020, Cryptology ePrint Archive: Report 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov und L. Vaidman. Messung der Schrödingerwelle eines einzelnen Teilchens. Physics Letters A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Hoffnungen, Ängste und Software-Verschleierung. Kommun. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart und S. Wiesner. Quantenkryptographie oder fälschungssichere U-Bahn-Token. In Fortschritte in der Kryptologie, Seiten 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski und YT Kalai. Konstruktive Post-Quantum-Reduktionen. In Y. Dodis und T. Shrimpton, Herausgeber, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15.–18. August 2022, Proceedings, Teil III, Band 13509 des Vortrags Anmerkungen in der Informatik, Seiten 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 und A. Rosen. Die Unmöglichkeit der Verschleierung mit Hilfseingabe oder einem Universalsimulator. In JA Garay und R. Gennaro, Herausgeber, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, USA, 17.–21. August 2014, Proceedings, Teil II, Band 8617 von Lecture Notes in Computer Science, Seiten 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 und K. Yang. Über die (Un-)Möglichkeit der Verschleierung von Programmen. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombe. Clifford-Gates durch Codedeformation. Neues 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. Durchsuchen eines Quantum-Telefonbuchs. Science, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] A. Behera, O. Sattath und U. Shinar. Rauschtolerante Quantentoken für MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh und M. Zhandry. Quantum-Secure Message Authentication Codes. In T. Johansson und PQ Nguyen, Herausgeber, Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athen, Griechenland, 26.-30. Mai 2013. Proceedings, Band 7881 von Lecture Notes in Computer Wissenschaft, Seiten 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve und D. Gottesmann. Effiziente Berechnungen von Kodierungen für die Quantenfehlerkorrektur. Phys. Rev. A, 56:76–82, Juli 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai und V. Zikas. Kryptografie mit Einweg-Hintertüren. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] P.Christian. Persönliche Mitteilung, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu und M. Zhandry. Hidden Cosets and Applications to Unclonable Cryptography, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan und N. Raghunathan. Grenzen für die Fehlerreduzierung mit wenigen Quantenabfragen. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 und RANDOM 2005, Berkeley, CA, USA, 22.-24. August 2005, Proceedings, Seiten 245–256, 2005 .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum und M. Varia. Verschleierung der Hyperplane-Mitgliedschaft. In D. Micciancio, Herausgeber, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zürich, Schweiz, 9.–11. Februar 2010. Proceedings, Band 5978 der Lecture Notes in Computer Science, Seiten 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie und ME Hellman. Neue Richtungen in der Kryptographie. IEEE-Trans. Informationstheorie, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding und MO Rabin. Hyperverschlüsselung und dauerhafte Sicherheit. In H. Alt und A. Ferreira, Herausgeber, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, Frankreich, 14.-16. März 2002, Proceedings, Band 2285 von Lecture Notes in Computer Science, Seiten 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 und P. Shor. Quantenzustandswiederherstellung und Einzelkopie-Tomographie für Grundzustände von Hamiltonianern. Phys. Rev. Lett., 105:190503, Nov. 2010.
https://doi.org/ 10.1103/PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski und P. Shor. Quantengeld aus Knoten. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Seiten 276–289. AKM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gawinsky. Quantengeld mit klassischer Verifikation. In IEEE 27th Annual Conference on Computational Complexity, Seiten 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser und YT Kalai. Über die Unmöglichkeit der Verschleierung mit Hilfsinput. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23.–25. Oktober 2005, Pittsburgh, PA, USA, Proceedings, Seiten 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou und I. Kerenidis. Neubauten für Quantengeld. In S. Beigi und R. König, Herausgeber, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, 20.-22. Mai 2015, Brüssel, Belgien, Band 44 von LIPIcs, Seiten 92–110. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015.
https: // doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] O. Goldreich. Die Grundlagen der Kryptographie - Vol. 2, Grundlegende Anwendungen. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler und T. Beth. Effiziente Quantenschaltkreise für Nicht-Qubit-Quantenfehlerkorrekturcodes. Int. J. gefunden. Berechnung. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz und Y. Lindell. Einführung in die moderne Kryptographie, 2014. Auflage. CRC Press, XNUMX.

[32] NA Lynch. Verteilte Algorithmen. Morgan Kaufmann, 1996.

[33] M. Mosca und D. Stebila. Quantenmünzen, Band 523 von Contemp. Math., Seiten 35–47. Amer. Mathematik. Gesellschaft, 2010.

[34] MC Pena, RD Diaz, J. Faugère, LH Encinas und L. Perret. Nicht-Quanten-Kryptanalyse der lauten Version von Aaronson-Christianos Quantengeld-Schema. IET Informationssicherheit, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère und L. Perret. Algebraische Kryptoanalyse eines Quantengeldschemas Der rauschfreie Fall. In J. Katz, Herausgeber, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, 30. März – 1. April 2015, Proceedings, Band 9020 der Vorlesungsunterlagen in Informatik, Seiten 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Zählen von Unterräumen eines endlichen Vektorraums – 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 und JI Cirac. Unfälschbare rauschtolerante Quantentoken. Proceedings of the National Academy of Sciences, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

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

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

[40] O. Sattath. Quantenumsichtige Verträge mit Anwendungen für Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. Nicht klonbare Kryptographie, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Public-Key-Quantengeld bei einer klassischen Bank. In S. Leonardi und A. Gupta, Herausgeber, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rom, Italien, 20.–24. Juni 2022, Seiten 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Shmueli. Semiquanten-tokenisierte Signaturen. In Y. Dodis und T. Shrimpton, Herausgeber, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15.–18. August 2022, Proceedings, Teil I, Band 13507 des Vortrags Anmerkungen in der Informatik, Seiten 296–319. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover und A. Patel. Ein neuer Algorithmus für die Festkomma-Quantensuche. Quantum Information & Computation, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto und N. Imoto. Anonymes Quantenbargeld. In ERATO-Konferenz über Quanteninformationswissenschaft, 2003.

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

[47] D. Unruh. Ewige Mehrparteien-Berechnung. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

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

[49] WK Wootters und WH Zurek. Ein einzelnes Quant kann nicht geklont werden. Nature, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell und MJ Sellars. Optisch adressierbare Kernspins in einem Festkörper mit einer Kohärenzzeit von sechs Stunden. Nature, 517(7533):177–180, Januar 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M. Zhandry. Quantenblitz trifft nie zweimal denselben Zustand, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Quantenblitze schlagen nie zweimal im selben Zustand ein. Oder: Quantengeld aus kryptografischen Annahmen. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Zitiert von

[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 und P. Wallden, „Fortschritte in der Quantenkryptographie“, Fortschritte in Optik und Photonik 12 4, 1012 (2020).

[2] Douglas Scott, „Wissenschaftsparodien, Physikstreiche und astronomische Eskapaden“, arXiv: 2103.17057.

[3] Thomas Vidick und Tina Zhang, „Klassische Beweise für Quantenwissen“, arXiv: 2005.01691.

[4] Oder Sattath, „Quantum Prudent Contracts with Applications to Bitcoin“, arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry und Ruizhe Zhang, „Neue Ansätze für Quantenkopierschutz“, arXiv: 2004.09674.

[6] Roy Radian und Or Sattath, „Semi-Quantum Money“, arXiv: 1908.08889.

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

[8] Prabhanjan Ananth und Rolando L. La Placa, „Sicheres Software-Leasing“, arXiv: 2005.05289.

[9] Oder Sattath und Shai Wyborski, „Uncloneable Decryptors from Quantum Copy-Protection“, arXiv: 2203.05866.

[10] Andrea Coladangelo und Or Sattath, „Eine Quantengeldlösung für das Blockchain-Skalierbarkeitsproblem“, arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery und Mark Zhandry, „Eine weitere Runde, Quantengeld zu brechen und zu verdienen: Wie man es nicht aus Gittern baut und mehr“, arXiv: 2211.11994.

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

[13] Oder Sattath, „Uncloneable Cryptography“, arXiv: 2210.14265.

[14] Amit Behera und Or Sattath, „Fast öffentliche Quantenmünzen“, arXiv: 2002.12438.

[15] Anne Broadbent, Sevag Gharibian und Hong-Sheng Zhou, „Towards Quantum One-Time Memories from Stateless Hardware“, arXiv: 1810.05226.

[16] Niraj Kumar, „Praxistaugliches robustes Quantengeld mit klassischer Verifikation“, arXiv: 1908.04114.

[17] Oder Sattath und Uriel Shinar, „Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism“, arXiv: 2212.08750.

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

Die obigen Zitate stammen von SAO / NASA ADS (Zuletzt erfolgreich aktualisiert am 2023, 01:20:14 Uhr). Die Liste ist möglicherweise unvollständig, da nicht alle Verlage geeignete und vollständige Zitationsdaten bereitstellen.

On Der von Crossref zitierte Dienst Es wurden keine Daten zum Zitieren von Werken gefunden (letzter Versuch 2023-01-20 14:01:00).

Dieses Papier ist in Quantum unter dem veröffentlicht Creative Commons Namensnennung 4.0 International (CC BY 4.0) Lizenz. Das Copyright verbleibt bei den ursprünglichen Copyright-Inhabern wie den Autoren oder deren Institutionen.

Zeitstempel:

Mehr von Quantenjournal