Kvanttitunnukset digitaalisille allekirjoituksille

Kvanttitunnukset digitaalisille allekirjoituksille

Aikaleima: 19. tammikuuta 2023 8

Shalev Ben-David1 ja Tai Sattath2

1Waterloon yliopisto, David R. Cheriton School of Computer Science
2Negevin Ben-Gurion-yliopisto, tietojenkäsittelytieteen laitos

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Kalastaja sai kvanttikalan. "Kalastaja, anna minun mennä", pyysi kala, "ja minä täytän sinulle kolme toivetta". Kalastaja suostui. Kala antoi kalastajalle kvanttitietokoneen, kolme kvanttiallekirjoitusmerkkiä ja hänen klassisen julkisen avaimensa. Kala selitti: "Allekirjoita kolme toivettasi käyttämällä tokenoitua allekirjoitusjärjestelmää tällä kvanttitietokoneella ja näytä sitten voimassa oleva allekirjoituksesi kuninkaalle, joka on minulle palveluksen velkaa".
Kalastaja käytti yhtä allekirjoitustokeista allekirjoittaakseen asiakirjan "Anna minulle linna!" ja ryntäsi palatsiin. Kuningas suoritti klassisen varmistusalgoritmin kalan julkisella avaimella, ja koska se oli voimassa, kuningas noudatti sitä.
Kalastajan vaimo halusi allekirjoittaa kymmenen toivetta kahdella jäljellä olevalla allekirjoitusmerkillä. Kalastaja ei halunnut huijata ja purjehti salaa tapaamaan kaloja. "Kala, vaimoni haluaa allekirjoittaa vielä kymmenen toivetta". Mutta kala ei ollut huolissaan: ”Olen oppinut kvanttisalauksen edellisen tarinan (Grimmin veljesten Kalastaja ja hänen vaimonsa) jälkeen. Kvanttimerkit kulutetaan allekirjoituksen aikana. Polynomivaimosi ei voi edes allekirjoittaa neljää toivetta niillä kolmella allekirjoitusmerkillä, jotka annoin sinulle."
"Kuinka se toimii?" kalastaja ihmetteli. "Oletko kuullut kvanttirahasta? Nämä ovat kvanttitiloja, jotka voidaan helposti todentaa, mutta joita on vaikea kopioida. Tämä tokenoitu kvanttiallekirjoitusjärjestelmä laajentaa Aaronsonin ja Christianon kvanttirahajärjestelmää, minkä vuoksi allekirjoitustokeneja ei voi kopioida.
"Onko suunnitelmassasi muita hienoja ominaisuuksia?" kalastaja kysyi. ”Kyllä, järjestelmällä on muita turvallisuustakuita: peruutettavuus, testattavuus ja ikuinen turvallisuus. Lisäksi, jos olet merellä ja kvanttipuhelimessasi on vain klassinen vastaanotto, voit tällä menetelmällä siirtää kvanttirahojen arvon rantaan”, kala sanoi ja ui pois.

Quantum Tokens digitaalisille allekirjoituksille PlatoBlockchain Data Intelligence. Pystysuuntainen haku. Ai.

[Upotetun sisällön]

► BibTeX-tiedot

► Viitteet

[1] S. Aaronson. Kvanttikopiosuojaus ja kvanttiraha. Julkaisussa Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Pariisi, Ranska, 15.–18, sivut 2009–229, 242.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan ja L. Vaidman. Aaltofunktion merkitys. Phys. Rev. A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson ja P. Christiano. Kvanttiraha piilotetuista aliavaruuksista. Teoksessa Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19.–22, sivut 2012–41, 60.
https: / / doi.org/ 10.1145 / +2213977.2213983

[4] S. Aaronson ja P. Christiano. Kvanttiraha piilotetuista aliavaruuksista. Theory of Computing, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias ja M. Zhandry. Kertaluonteiset allekirjoitukset ja sovellukset hybridi-kvantti/klassinen todennus. Teoksessa K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath ja J. Chuzhoy, toimittajat, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing, sivut 255–268. ACM, 2020, Cryptology ePrint Archive: Raportti 2020/​107.
https: / / doi.org/ 10.1145 / +3357713.3384304

[6] Y. Aharonov ja L. Vaidman. Yhden hiukkasen Schrödingerin aallon mittaus. Physics Letters A, 178(1):38-42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Toiveita, pelkoja ja ohjelmistojen hämärtymistä. Commun. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / +2757276

[8] CH Bennett, G. Brassard, S. Breidbart ja S. Wiesner. Kvanttisalaus eli väärentämättömät metrotunnukset. Teoksessa Advances in Cryptology, sivut 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski ja YT Kalai. Rakentavat post-kvanttivähennykset. Toimittajat Y. Dodis ja T. Shrimpton, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15.-18, Proceedings, osa III, osa 2022 Notes in Computer Science, sivut 13509–654. Kevät, 683.
https:/​/​doi.org/​10.1007/​978-3-031-15982-4_22

[10] N. Bitansky, R. Canetti, H. Cohn, S. Goldwasser, YT Kalai, O. Paneth ja A. Rosen. Hämärtämisen mahdottomuus lisätulon tai yleissimulaattorin avulla. Julkaisussa JA Garay ja R. Gennaro, toimittajat, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, USA, 17.-21, Proceedings, Part II, Volume 2014 of Lecture Notes in Computer Science, sivut 8617-71. Kevät, 89.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, SP Vadhan ja K. Yang. Ohjelmien hämärtämisen (mahdottomuudesta). J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / +2160158.2160159

[12] H. Bombin. Clifford-portit koodin muodonmuutoksella. 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. Etsitään Quantum-puhelinluettelosta. Science, 275(5300): 627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] A. Behera, O. Sattath ja U. Shinar. Noise-Tolerant Quantum Tokens for MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh ja M. Zhandry. Quantum-Secure viestien todennuskoodit. Teoksessa T. Johansson ja PQ Nguyen, toimittajat, Advances in Cryptology – EUROCRYPT 2013, 32nd Annual International Conference on theory and Applications of Cryptographic Techniques, Ateena, Kreikka, 26.-30. Proceedings, nide 2013 Computer Notes in Lecture Tiede, sivut 7881–592. Kevät, 608.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve ja D. Gottesman. Tehokkaat koodausten laskelmat kvanttivirheen korjausta varten. Phys. Rev. A, 56:76–82, heinäkuu 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai ja V. Zikas. Kryptografia kertakäyttöisillä takaovilla. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Raportti 2018/​352.
https: / / doi.org/ 10.3390 / cryptography3030022

[18] P. Christiano. Henkilökohtainen viestintä, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu ja M. Zhandry. Piilotetut tarvikkeet ja sovellukset kloonaamattomaan kryptografiaan, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan ja N. Raghunathan. Virheiden vähentämisen rajat muutamalla kvanttikyselyllä. Teoksessa Approximation, Randomization and Combinatoral Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatoral Optimization Problems, APPROX 2005 ja RANDOM 2005, Berkeley, CA, USA, 22.-24. elokuuta 2005, 245, 256-2005, XNUMX, XNUMX, XNUMX, XNUMX, XNUMX, XNUMX, XNUMX, XNUMX, XNUMX .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum ja M. Varia. Hyperplane-jäsenyyden hämärtäminen. Teoksessa D. Micciancio, toimittaja, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zürich, Sveitsi, 9.–11. helmikuuta 2010. Proceedings, nide 5978 of Lecture Notes in Computer Science, sivut 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie ja ME Hellman. Uusia suuntauksia kryptografiassa. IEEE Trans. Information Theory, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding ja MO Rabin. Hypersalaus ja ikuinen suojaus. Teoksessa H. Alt ja A. Ferreira, toimittajat, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, Ranska, 14.-16. maaliskuuta 2002, Proceedings, nide 2285 of Lecture Notes in Computer Science, sivut 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 ja P. Shor. Quantum State Restoration ja Single Copy Tomography for Ground State of Hamiltonians. Phys. Rev. Lett., 105:190503, marraskuu 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski ja P. Shor. Kvanttiraha solmuista. Teoksessa Proceedings of the 3rd Innovations in Theoretical Computer Science, sivut 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / +2090236.2090260

[26] D. Gavinsky. Kvanttiraha klassisella todennuksella. Julkaisussa IEEE 27th Annual Conference on Computational Complexity, sivut 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser ja YT Kalai. Hämärtämisen mahdottomuudesta lisätulolla. 46. ​​vuotuisessa IEEE-symposiumissa tietojenkäsittelytieteen perusteista (FOCS 2005), 23.–25. lokakuuta 2005, Pittsburgh, PA, USA, Proceedings, sivut 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou ja I. Kerenidis. Uudet rakenteet kvanttirahalle. S. Beigi ja R. König, toimittajat, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2015, 20.-22, Bryssel, Belgia, LIPIcsin osa 2015, sivut 44–92. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 110.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] O. Goldreich. Salauskirjan perusteet - Vuosikerta 2, Perussovellukset. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler ja T. Beth. Tehokkaat kvanttipiirit ei-Qubit-kvanttivirheitä korjaaville koodeille. Int. J. Löytyi. Comput. Sei., 14(5):757-776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz ja Y. Lindell. Johdatus nykyaikaiseen salaustekniikkaan, toinen painos. CRC Press, 2014.

[32] NA Lynch. Hajautetut algoritmit. Morgan Kaufmann, 1996.

[33] M. Mosca ja D. Stebila. Kvanttikolikot, nide 523 Contemp. Math., sivut 35–47. Amer. Matematiikka. Soc., 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas ja L. Perret. Aaronson-Christianon kvanttirahasuunnitelman meluisan version ei-kvantti kryptaanalyysi. IET Information Security, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère ja L. Perret. Kvanttirahajärjestelmän algebrallinen kryptaanalyysi Meluton tapaus. Teoksessa J. Katz, toimittaja, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, 30. maaliskuuta – 1. huhtikuuta 2015, Proceedings, luku 9020 of Lecture Notes in Computer Science, sivut 194–213. Kevät, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Äärillisen vektoriavaruuden aliavaruuksien laskeminen — 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 ja JI Cirac. Väärentämättömät melua kestävät kvanttimerkit. Proceedings of the National Academy of Sciences, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian ja O. Sattath. Puolikvanttiraha. Teoksessa Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zürich, Sveitsi, 21.–23, sivut 2019–132. ACM, 146, arXiv: 2019.
https: / / doi.org/ 10.1145 / +3318041.3355462
arXiv: 1908.08889

[39] R. Radian ja O. Sattath. Puolikvanttiraha. Journal of Cryptology, 35(2), tammikuu 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. Kloonaamaton kryptografia, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Julkisen avaimen kvanttiraha perinteisellä pankilla. S. Leonardi ja A. Gupta, toimittajat, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rooma, Italia, 20.–24. kesäkuuta 2022, sivut 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / +3519935.3519952

[43] O. Shmueli. Puolikvanttitokenisoidut allekirjoitukset. julkaisussa Y. Dodis ja T. Shrimpton, toimittajat, Advances in Cryptology – CRYPTO 2022 – 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, 15.–18. elokuuta 2022, Proceedings, osa I, osa 13507 Notes in Computer Science, sivut 296–319. Kevät, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover ja A. Patel. Uusi algoritmi kiinteän pisteen kvanttihakuun. Quantum Information & Computation, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto ja N. Imoto. Anonyymi kvanttiraha. ERATO-konferenssissa kvanttitietotieteestä, 2003.

[46] D. Unruh. Kumottava kvanttiajastettu julkaisusalaus. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / +2817206

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

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

[49] WK Wootters ja WH Zurek. Yhtä kvanttia ei voida kloonata. Nature, 299(5886):802-803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell ja MJ Sellars. Optisesti osoitettava ydin pyörii kiinteässä tilassa kuuden tunnin koherenssiajalla. Nature, 517(7533):177–180, tammikuu 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M. Zhandry. Kvanttisalama ei koskaan iske samaan tilaan kahdesti, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Kvanttisalama ei koskaan iske samaan tilaan kahdesti. Tai: Kvanttiraha kryptografisista oletuksista. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Viitattu

[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 ja 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 ja Tina Zhang, "Kvanttitiedon klassiset todisteet", arXiv: 2005.01691.

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

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

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

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

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

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

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

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

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

[13] Tai Sattath, "Uncloneable Cryptography", arXiv: 2210.14265.

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

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

[16] Niraj Kumar, "Käytännössä toteutettavissa oleva vankka kvanttiraha klassisella verifioinnilla", arXiv: 1908.04114.

[17] Tai Sattath ja Uriel Shinar, "Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism", arXiv: 2212.08750.

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

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2023-01-20 14:01:05). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

On Crossrefin siteerattu palvelu tietoja teosten viittaamisesta ei löytynyt (viimeinen yritys 2023-01-20 14:01:00).

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

Aikaleima:

Lisää aiheesta Quantum Journal