Quantum Tokens για Ψηφιακές Υπογραφές

Quantum Tokens για Ψηφιακές Υπογραφές

Shalev Ben-David1 και Ή Sattath2

1University of Waterloo, David R. Cheriton School of Computer Science
2Πανεπιστήμιο Ben-Gurion του Negev, Τμήμα Επιστήμης Υπολογιστών

Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.

Περίληψη

Ο ψαράς έπιασε ένα κβαντικό ψάρι. «Ψαρά, σε παρακαλώ άσε με», παρακάλεσε το ψάρι, «και θα σου κάνω τρεις ευχές». Ο ψαράς συμφώνησε. Το ψάρι έδωσε στον ψαρά έναν κβαντικό υπολογιστή, τρεις μάρκες κβαντικής υπογραφής και το κλασικό δημόσιο κλειδί του. Το ψάρι εξήγησε: «Για να υπογράψεις τις τρεις επιθυμίες σου, χρησιμοποιήστε το σχέδιο υπογραφών με διακριτικά σε αυτόν τον κβαντικό υπολογιστή και μετά δείξτε την έγκυρη υπογραφή σας στον βασιλιά, ο οποίος μου χρωστάει μια χάρη».
Ο ψαράς χρησιμοποίησε ένα από τα κουπόνια υπογραφής για να υπογράψει το έγγραφο «δώστε μου ένα κάστρο!» και όρμησε στο παλάτι. Ο βασιλιάς εκτέλεσε τον κλασικό αλγόριθμο επαλήθευσης χρησιμοποιώντας το δημόσιο κλειδί του ψαριού και επειδή ήταν έγκυρος, ο βασιλιάς συμμορφώθηκε.
Η σύζυγος του ψαρά ήθελε να υπογράψει δέκα ευχές χρησιμοποιώντας τα δύο κουπόνια υπογραφής που είχαν απομείνει. Ο ψαράς δεν ήθελε να απατήσει και έπλευσε κρυφά για να συναντήσει το ψάρι. «Ψάρι, η γυναίκα μου θέλει να υπογράψει άλλες δέκα ευχές». Αλλά το ψάρι δεν ανησυχούσε: «Έμαθα κβαντική κρυπτογραφία ακολουθώντας την προηγούμενη ιστορία (Ο ψαράς και η σύζυγός του από τους αδερφούς Γκριμ). Τα κβαντικά διακριτικά καταναλώνονται κατά την υπογραφή. Η πολυώνυμη σύζυγός σας δεν μπορεί να υπογράψει ούτε τέσσερις ευχές χρησιμοποιώντας τα τρία διακριτικά υπογραφής που σας έδωσα».
"Πώς λειτουργεί?" αναρωτήθηκε ο ψαράς. «Έχετε ακούσει για το κβαντικό χρήμα; Αυτές είναι κβαντικές καταστάσεις που μπορούν εύκολα να επαληθευτούν αλλά είναι δύσκολο να αντιγραφούν. Αυτό το συμβολικό σχήμα κβαντικής υπογραφής επεκτείνει το σχήμα κβαντικού χρήματος του Aaronson και του Christiano, γι' αυτό δεν μπορούν να αντιγραφούν τα διακριτικά υπογραφής».
"Το σχέδιό σας έχει επιπλέον φανταχτερές ιδιότητες;" ρώτησε ο ψαράς. «Ναι, το σύστημα έχει άλλες εγγυήσεις ασφαλείας: δυνατότητα ανάκλησης, δυνατότητα δοκιμής και διαρκή ασφάλεια. Επιπλέον, αν βρίσκεστε στη θάλασσα και το κβαντικό σας τηλέφωνο έχει μόνο κλασική λήψη, μπορείτε να χρησιμοποιήσετε αυτό το σχέδιο για να μεταφέρετε την αξία του κβαντικού χρήματος στην ακτή», είπε το ψάρι και κολύμπησε μακριά.

[Ενσωματωμένο περιεχόμενο]

► Δεδομένα BibTeX

► Αναφορές

[1] S. Aaronson. Quantum Copy-Protection και Quantum Money. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Παρίσι, Γαλλία, 15-18 Ιουλίου 2009, σελίδες 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan, and L. Vaidman. Έννοια της κυματικής συνάρτησης. Phys. Rev. A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson και P. Christiano. Κβαντικό χρήμα από κρυμμένους υποχώρους. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, Νέα Υόρκη, Νέα Υόρκη, ΗΠΑ, 19 – 22 Μαΐου 2012, σελίδες 41–60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson και P. Christiano. Quantum Money από κρυμμένους υποχώρους. Theory of Computing, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias, and M. Zhandry. One-shot υπογραφές και εφαρμογές στον υβριδικό κβαντικό/​κλασικό έλεγχο ταυτότητας. Στο K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, συντάκτες, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing, σελίδες 255–268. ACM, 2020, Cryptology ePrint Archive: Report 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov και L. Vaidman. Μέτρηση του κύματος Schrödinger ενός μόνο σωματιδίου. Physics Letters A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] Β. Μπαράκ. Ελπίδες, φόβοι και συσκότιση λογισμικού. Commun. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart και S. Wiesner. Κβαντική κρυπτογραφία, ή άχαρα διακριτικά του μετρό. Στο Advances in Cryptology, σελίδες 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski και YT Kalai. Εποικοδομητικές μετα-κβαντικές μειώσεις. Στο Y. Dodis and T. Shrimpton, editors, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part III13509, τόμος 654 Σημειώσεις στην Επιστήμη των Υπολογιστών, σελίδες 683–2022. Springer, XNUMX.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] N. Bitansky, R. Canetti, H. Cohn, S. Goldwasser, YT Kalai, O. Paneth και A. Rosen. Η αδυναμία συσκότισης με βοηθητική είσοδο ή καθολικό προσομοιωτή. Στο JA Garay and R. Gennaro, editors, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II, volume 8617 of Lecture Science, Notes in Computer σελίδες 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, and K. Yang. Για την (α)δυνατότητα συσκότισης προγραμμάτων. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombin. Πύλες Clifford με παραμόρφωση κώδικα. 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. Αναζήτηση σε έναν Quantum Phone Book. Science, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] Α. Behera, Ο. Sattath και U. Shinar. Noise-Tolerant Quantum Tokens για MAC, 2021.
https://doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh και M. Zhandry. Κωδικοί ελέγχου ταυτότητας μηνυμάτων Quantum-Secure. Στο T. Johansson and PQ Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Αθήνα, Ελλάδα, 26-30 Μαΐου 2013. Πρακτικά, τόμος 7881 Σημειώσεις Υπολογιστών Επιστήμη, σελίδες 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve και D. Gottesman. Αποτελεσματικοί υπολογισμοί κωδικοποιήσεων για κβαντική διόρθωση σφαλμάτων. Phys. Rev. A, 56:76–82, Ιούλιος 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai, and V. Zikas. Κρυπτογραφία με Backdoors μιας χρήσης. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Report 2018/​352.
https: / / doi.org/ 10.3390 / κρυπτογραφία3030022

[18] Π. Χριστιάνο. Προσωπική επικοινωνία, 2015.

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

[20] S. Chakraborty, J. Radhakrishnan, and N. Raghunathan. Όρια για μείωση σφαλμάτων με λίγα κβαντικά ερωτήματα. Σε προσέγγιση, τυχαιοποίηση και συνδυαστική βελτιστοποίηση, αλγόριθμους και τεχνικές, 8ο Διεθνές Εργαστήριο για Αλγόριθμους Προσέγγισης για Συνδυαστικά Προβλήματα Βελτιστοποίησης, περίπου 2005 και Random 2005, Berkeley, CA, ΗΠΑ, 22-24 Αυγούστου 2005, Proceedings, σελίδες 245-256, 2005 .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum, and M. Varia. Συσκότιση της ιδιότητας μέλους Hyperplane. Στο D. Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland, February 9-11, 2010. Proceedings, volume 5978 of Lecture Notes in Computer Science, σελίδες 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] Ο W. Diffie and ME Hellman. Νέες κατευθύνσεις στην κρυπτογραφία. IEEE Trans. Information Theory, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding και MO Rabin. Υπερ-κρυπτογράφηση και διαρκής ασφάλεια. Στο H. Alt και A. Ferreira, συντάκτες, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, Γαλλία, 14-16 Μαρτίου 2002, Proceedings, τόμος 2285 of Lecture Notes in Computer Science, σελίδες 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 και P. Shor. Αποκατάσταση κβαντικής κατάστασης και τομογραφία ενός αντιγράφου για εδαφικές καταστάσεις των Hamiltonians. Phys. Rev. Lett., 105:190503, Νοέμβριος 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski και P. Shor. Κβαντικό χρήμα από κόμπους. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, σελίδες 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gavinsky. Κβαντικό χρήμα με κλασική επαλήθευση. Στο IEEE 27th Annual Conference on Computational Complexity, σελίδες 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser και YT Kalai. Σχετικά με την αδυναμία συσκότισης με βοηθητική είσοδο. Στο 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 ​​Οκτωβρίου 2005, Pittsburgh, PA, USA, Proceedings, σελίδες 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] Μ. Γεωργίου και Ι. Κερενίδης. Νέες κατασκευές για το Quantum Money. Στο S. Beigi and R. König, συντάκτες, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, 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] O. Goldreich. The Foundations of Cryptography – Vol. 2, Βασικές Εφαρμογές. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler, and T. Beth. Αποτελεσματικά κβαντικά κυκλώματα για μη Qubit κβαντικούς κωδικούς διόρθωσης σφαλμάτων. Int. J. Βρέθηκε. Υπολογιστής. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz and Y. Lindell. Εισαγωγή στη Σύγχρονη Κρυπτογραφία, Δεύτερη Έκδοση. CRC Press, 2014.

[32] ΝΑ Λιντς. Κατανεμημένοι αλγόριθμοι. Morgan Kaufmann, 1996.

[33] M. Mosca και D. Stebila. Κβαντικά νομίσματα, τόμος 523 του Contemp. Μαθηματικά, σελίδες 35–47. Amer. Μαθηματικά. Soc., 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas και L. Perret. Μη κβαντική κρυπτανάλυση της θορυβώδους έκδοσης του συστήματος κβαντικού χρήματος του Aaronson-Christiano. 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, editor, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-key Cryptography, Gaithersburg, MD, USA, 30 Μαρτίου – 1 Απριλίου 2015, Proceedings, τόμος 9020 Σημειώσεις Διάλεξης στο Computer Science, σελίδες 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] Α. Πρασάντ. Καταμέτρηση υποχώρων ενός πεπερασμένου διανυσματικού χώρου — 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 και JI Cirac. Αχαράκτητα κβαντικά διακριτικά ανθεκτικά στον θόρυβο. Proceedings of the National Academy of Sciences, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian και O. Sattath. Ημι-κβαντικό χρήμα. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Ζυρίχη, Ελβετία, 21-23 Οκτωβρίου 2019, σελίδες 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] R. Radian και O. Sattath. Ημι-κβαντικό χρήμα. Journal of Cryptology, 35(2), Ιανουάριος 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. Uncloneable Cryptography, 2022.
https://doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Κβαντικό χρήμα δημόσιου κλειδιού με κλασική τράπεζα. Στο S. Leonardi και A. Gupta, εκδότες, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Ρώμη, Ιταλία, 20 – 24 Ιουνίου 2022, σελίδες 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Shmueli. Ημι-κβαντικές Tokenized Signatures. Στο Y. Dodis and T. Shrimpton, editors, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I, Part I, τόμος 13507 Notes in Computer Science, σελίδες 296–319. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover, and A. Patel. Ένας νέος αλγόριθμος για κβαντική αναζήτηση σταθερού σημείου. Quantum Information & Computation, 6(6):483–494, 2006.
http://​/portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto, and N. Imoto. Ανώνυμα κβαντικά μετρητά. Στο Συνέδριο ERATO για την Κβαντική Επιστήμη της Πληροφορίας, 2003.

[46] D. Unruh. Ανακλητή Κβαντική Κρυπτογράφηση χρονισμένης απελευθέρωσης. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] D. Unruh. Αιώνιος Υπολογισμός Πολυμερών. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

[48] S. Wiesner. Συζευγμένη κωδικοποίηση. 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] M. Zhandry. Ο κβαντικός κεραυνός δεν χτυπά ποτέ την ίδια κατάσταση δύο φορές, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Ο κβαντικός κεραυνός δεν χτυπά ποτέ την ίδια κατάσταση δύο φορές. Ή: Quantum Money from Cryptographic Assumptions. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Αναφέρεται από

[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 και P. Wallden, «Advances in quantum cryptography», Advances in Optics and Photonics 12 4, 1012 (2020).

[2] Douglas Scott, «Science Spoofs, Physics Pranks and Astronomical Antics», arXiv: 2103.17057.

[3] Thomas Vidick και Tina Zhang, «Κλασικές αποδείξεις κβαντικής γνώσης», arXiv: 2005.01691.

[4] Ή Sattath, «Quantum Prudent Contracts with Applications to Bitcoin», arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry και Ruizhe Zhang, «New Approaches for Quantum Copy-Protection», arXiv: 2004.09674.

[6] Roy Radian και Or Sattath, «Semi-Quantum Money», arXiv: 1908.08889.

[7] Andrea Coladangelo, Shafi Goldwasser και Umesh Vazirani, «Απαγορευμένη κρυπτογράφηση σε έναν κβαντικό κόσμο», arXiv: 2112.14988.

[8] Prabhanjan Ananth και Rolando L. La Placa, “Secure Software Leasing”, arXiv: 2005.05289.

[9] Ή Sattath και Shai Wyborski, «Uncloneable Decryptors from Quantum Copy-Protection», arXiv: 2203.05866.

[10] Andrea Coladangelo και Or Sattath, «A Quantum Money Solution to the Blockchain Scalability Problem», arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery και Mark Zhandry, «Ένας άλλος γύρος Breaking and Making Quantum Money: How to Not Build It from Lattices, and More» arXiv: 2211.11994.

[12] Andrea Coladangelo, Jiahui Liu, Qipeng Liu και Mark Zhandry, «Hidden Cosets and Applications to Unclonable Cryptography», arXiv: 2107.05692.

[13] Ή Sattath, «Uncloneable Cryptography», arXiv: 2210.14265.

[14] Amit Behera και Or Sattath, "Almost Public Quantum Coins", arXiv: 2002.12438.

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

[16] Niraj Kumar, «Πρακτικά εφικτό ισχυρό κβαντικό χρήμα με κλασική επαλήθευση», arXiv: 1908.04114.

[17] Ή Sattath και Uriel Shinar, «Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism», arXiv: 2212.08750.

[18] Nir Bitansky, Zvika Brakerski και Yael Tauman Kalai, «Εποικοδομητικές μετα-κβαντικές μειώσεις», arXiv: 2203.02314.

Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2023-01-20 14:01:05). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.

On Η υπηρεσία παραπομπής του Crossref δεν βρέθηκαν δεδομένα σχετικά με την αναφορά έργων (τελευταία προσπάθεια 2023-01-20 14:01:00).

Σφραγίδα ώρας:

Περισσότερα από Quantum Journal