Quantumtokens voor digitale handtekeningen

Quantumtokens voor digitale handtekeningen

Tijdstempel: 19 januari 2023 8:49 uur
Bronknooppunt: 1908311

Shalev Ben-David1 en Of Sattath2

1Universiteit van Waterloo, David R. Cheriton School of Computer Science
2Ben-Gurion Universiteit van de Negev, afdeling Computerwetenschappen

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

De visser ving een kwantumvis. “Visser, laat me alsjeblieft gaan”, smeekte de vis, “en ik zal je drie wensen vervullen”. De visser was het daarmee eens. De vis gaf de visser een kwantumcomputer, drie kwantumsigneringstokens en zijn klassieke publieke sleutel. De vis legde uit: “Om je drie wensen te ondertekenen, gebruik je het tokenized handtekeningschema op deze kwantumcomputer en toon je je geldige handtekening aan de koning, die mij een gunst verschuldigd is”.
De visser gebruikte een van de tekenfiches om het document “geef me een kasteel!” te ondertekenen. en haastte zich naar het paleis. De koning voerde het klassieke verificatiealgoritme uit met behulp van de openbare sleutel van de vis, en aangezien deze geldig was, voldeed de koning eraan.
De vrouw van de visser wilde tien wensen ondertekenen met de twee resterende tekenfiches. De visser wilde niet vals spelen en zeilde in het geheim de vis tegemoet. “Vis, mijn vrouw wil nog tien wensen tekenen”. Maar de vis maakte zich geen zorgen: “Ik heb kwantumcryptografie geleerd naar aanleiding van het vorige verhaal (De visser en zijn vrouw van de gebroeders Grimm). De kwantumtokens worden verbruikt tijdens de ondertekening. Je polynomiale vrouw kan niet eens vier wensen ondertekenen met de drie tekenfiches die ik je heb gegeven”.
"Hoe werkt het?" vroeg de visser zich af. “Heb je gehoord van kwantumgeld? Dit zijn kwantumtoestanden die gemakkelijk kunnen worden geverifieerd, maar moeilijk te kopiëren zijn. Dit tokenized kwantumhandtekeningschema breidt het kwantumgeldschema van Aaronson en Christiano uit, en daarom kunnen de ondertekeningstokens niet worden gekopieerd”.
"Heeft uw plan nog meer mooie eigenschappen?" vroeg de visser. “Ja, de regeling heeft nog andere veiligheidsgaranties: herroepbaarheid, testbaarheid en eeuwige veiligheid. Bovendien, als je op zee bent en je kwantumtelefoon heeft alleen klassieke ontvangst, kun je dit schema gebruiken om de waarde van het kwantumgeld naar de kust over te brengen”, zei de vis, en zwom weg.

[Ingesloten inhoud]

► BibTeX-gegevens

► Referenties

[1] S. Aaronson. Quantum-kopieerbeveiliging en Quantum Money. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Parijs, Frankrijk, 15-18 juli 2009, pagina's 229-242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan en L. Vaidman. Betekenis van de golffunctie. Fys. Rev.A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson en P. Christiano. Kwantumgeld uit verborgen deelruimten. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, VS, 19 - 22 mei 2012, pagina's 41-60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson en P. Christiano. Kwantumgeld uit verborgen subruimten. Theorie van computergebruik, 9: 349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias en M. Zhandry. One-shot handtekeningen en toepassingen voor hybride kwantum/klassieke authenticatie. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath en J. Chuzhoy, redacteuren, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing, pagina's 255-268. ACM, 2020, Cryptologie ePrint-archief: rapport 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov en L. Vaidman. Meting van de Schrödingergolf van een enkel deeltje. Natuurkundebrieven A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Hoop, angst en softwareverduistering. Gemeenschappelijk. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart en S. Wiesner. Kwantumcryptografie, of onvervalsbare metrotokens. In Advances in Cryptology, pagina's 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski en YT Kalai. Constructieve post-kwantumreducties. In Y. Dodis en T. Shrimpton, redacteuren, Advances in Cryptology – CRYPTO 2022 – 42e jaarlijkse internationale cryptologieconferentie, CRYPTO 2022, Santa Barbara, CA, VS, 15-18 augustus 2022, Proceedings, deel III, deel 13509 van de lezing Aantekeningen in computerwetenschappen, pagina's 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 en A. Rosen. De onmogelijkheid van verduistering met hulpinvoer of een universele simulator. In J.A. Garay en R. Gennaro, redacteuren, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, VS, 17-21 augustus 2014, Proceedings, Deel II, deel 8617 van Lecture Notes in Computer Science, pagina's 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 en K. Yang. Over de (on)mogelijkheid om programma’s te verdoezelen. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombin. Clifford-poorten door codevervorming. Nieuw 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. Zoeken in een Quantum-telefoonboek. Wetenschap, 275(5300):627-628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] A. Behera, O. Sattath en U. Shinar. Geluidstolerante Quantum Tokens voor MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh en M. Zhandry. Quantum-veilige berichtauthenticatiecodes. In T. Johansson en P. Q. Nguyen, redacteuren, Advances in Cryptology – EUROCRYPT 2013, 32e jaarlijkse internationale conferentie over de theorie en toepassingen van cryptografische technieken, Athene, Griekenland, 26-30 mei 2013. Proceedings, deel 7881 van Lecture Notes in Computer Wetenschap, pagina's 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve en D. Gottesman. Efficiënte berekeningen van coderingen voor kwantumfoutcorrectie. Fys. Rev. A, 56:76–82, juli 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai en V. Zikas. Cryptografie met wegwerpachterdeurtjes. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archief: Rapport 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] P. Christiano. Persoonlijke communicatie, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu en M. Zhandry. Verborgen nevenklassen en toepassingen voor niet-kloneerbare cryptografie, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan en N. Raghunathan. Grenzen voor foutreductie met weinig kwantumquery's. In Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8e Internationale Workshop over Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 en RANDOM 2005, Berkeley, CA, VS, 22-24 augustus 2005, Proceedings, pagina's 245-256, 2005 .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum en M. Varia. Verduistering van het hyperplane-lidmaatschap. In D. Micciancio, redacteur, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zürich, Zwitserland, 9-11 februari 2010. Proceedings, deel 5978 van Lecture Notes in Computer Science, pagina's 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie en ME Hellman. Nieuwe richtingen in cryptografie. IEEE Trans. Informatietheorie, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] Y. Z. Ding en M. O. Rabin. Hyper-encryptie en eeuwige beveiliging. In H. Alt en A. Ferreira, redacteuren, STACS 2002, 19e jaarlijkse symposium over theoretische aspecten van computerwetenschappen, Antibes – Juan les Pins, Frankrijk, 14-16 maart 2002, Proceedings, deel 2285 van Lecture Notes in Computer Science, pagina's 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 en P. Shor. Quantum State Restoration en Single-Copy Tomography voor grondstaten van Hamiltonianen. Fys. Rev. Lett., 105:190503, november 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski en P. Shor. Kwantumgeld uit knopen. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pagina's 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gavinsky. Kwantumgeld met klassieke verificatie. In IEEE 27e jaarlijkse conferentie over computationele complexiteit, pagina's 42-52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser en YT Kalai. Over de onmogelijkheid van verduistering met hulpinput. In het 46e jaarlijkse IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 ​​oktober 2005, Pittsburgh, PA, VS, Proceedings, pagina's 553-562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou en ik. Kerenidis. Nieuwe constructies voor kwantumgeld. In S. Beigi en R. König, redacteuren, 10e conferentie over de theorie van kwantumcomputatie, communicatie en cryptografie, TQC 2015, 20-22 mei 2015, Brussel, België, deel 44 van LIPIcs, pagina's 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, basistoepassingen. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler en T. Beth. Efficiënte kwantumcircuits voor niet-Qubit kwantumfoutcorrigerende codes. Int. J. Gevonden. Computer. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz en Y. Lindell. Inleiding tot moderne cryptografie, tweede editie. CRC Press, 2014.

[32] N.A. Lynch. Gedistribueerde algoritmen. Morgan Kaufmann, 1996.

[33] M. Mosca en D. Stebila. Quantummunten, deel 523 van Contemp. Wiskunde, pagina's 35–47. Amer. Wiskunde. Soc., 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas en L. Perret. Niet-kwantumcryptanalyse van de luidruchtige versie van Aaronson-Christiano's Quantum Money Scheme. IET Informatiebeveiliging, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère en L. Perret. Algebraïsche cryptanalyse van een kwantumgeldplan Het ruisvrije geval. In J. Katz, redacteur, Public-Key Cryptography – PKC 2015 – 18e IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, VS, 30 maart – 1 april 2015, Proceedings, volume 9020 van Lecture Notes in Computerwetenschappen, pagina's 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Deelruimten van een eindige vectorruimte tellen - 1. Resonance, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski, N. Y. Yao, L. Jiang, M.D. Lukin en J.I. Cirac. Onvervalsbare ruistolerante kwantumtokens. Proceedings van de National Academy of Sciences, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian en O. Sattath. Semi-kwantumgeld. In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zürich, Zwitserland, 21-23 oktober 2019, pagina's 132-146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

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

[40] O. Satath. Quantum Prudent-contracten met toepassingen voor Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Satath. Onkloonbare cryptografie, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Public-key Quantum-geld bij een klassieke bank. In S. Leonardi en A. Gupta, redacteuren, STOC ’22: 54e jaarlijkse ACM SIGACT Symposium on Theory of Computing, Rome, Italië, 20 – 24 juni 2022, pagina’s 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Shmueli. Semi-kwantum tokenized handtekeningen. In Y. Dodis en T. Shrimpton, redacteuren, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, VS, 15-18 augustus 2022, Proceedings, deel I, deel 13507 van de lezing Notes in Computer Science, pagina's 296–319. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover en A. Patel. Een nieuw algoritme voor kwantumzoeken met een vast punt. Kwantuminformatie en berekeningen, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto en N. Imoto. Anoniem kwantumgeld. Tijdens de ERATO-conferentie over kwantuminformatiewetenschappen, 2003.

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

[47] D. Unruh. Eeuwige computergebruik met meerdere partijen. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

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

[49] WK Wootters en WH Zurek. Eén enkel kwantum kan niet worden gekloond. Natuur, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell en MJ Sellars. Optisch adresseerbare kernspins in een vaste stof met een coherentietijd van zes uur. Nature, 517(7533):177–180, januari 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M. Zhandry. Kwantumbliksem treft nooit tweemaal dezelfde toestand, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Kwantumbliksem treft nooit twee keer dezelfde toestand. Of: Kwantumgeld uit cryptografische aannames. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Geciteerd door

[1] S. Pirandola, U.L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, J.L. Pereira, M. Razavi, J Shamsul Shaari, M. Tomamichel, VC Usenko, G. Vallone, P. Villoresi en P. Wallden, “Vooruitgang in kwantumcryptografie”, Vooruitgang in optica en fotonica 12 4, 1012 (2020).

[2] Douglas Scott, “Wetenschappelijke parodie, natuurkundige grappen en astronomische capriolen”, arXiv: 2103.17057.

[3] Thomas Vidick en Tina Zhang, "Klassieke bewijzen van kwantumkennis", arXiv: 2005.01691.

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

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry en Ruizhe Zhang, "Nieuwe benaderingen voor kwantumkopieerbeveiliging", arXiv: 2004.09674.

[6] Roy Radian en Or Sattath, “Semi-kwantumgeld”, arXiv: 1908.08889.

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

[8] Prabhanjan Ananth en Rolando L. La Placa, “Veilige softwarelease”, arXiv: 2005.05289.

[9] Of Sattath en Shai Wyborski, “Onkloonbare decryptors van Quantum Copy-Protection”, arXiv: 2203.05866.

[10] Andrea Coladangelo en Or Sattath, "Een kwantumgeldoplossing voor het schaalbaarheidsprobleem van Blockchain", arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery en Mark Zhandry, "Nog een ronde van het breken en verdienen van kwantumgeld: hoe je het niet kunt opbouwen vanuit roosters, en meer", arXiv: 2211.11994.

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

[13] Of Sattath, “Onkloonbare cryptografie”, arXiv: 2210.14265.

[14] Amit Behera en Or Sattath, “Bijna openbare kwantummunten”, arXiv: 2002.12438.

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

[16] Niraj Kumar, “Praktisch haalbaar robuust kwantumgeld met klassieke verificatie”, arXiv: 1908.04114.

[17] Of Sattath en Uriel Shinar, “Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism”, arXiv: 2212.08750.

[18] Nir Bitansky, Zvika Brakerski en Yael Tauman Kalai, “Constructieve post-kwantumreducties”, arXiv: 2203.02314.

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2023-01-20 14:01:05). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2023-01-20 14:01:00).

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.

Tijdstempel:

Meer van Quantum Journaal