Jetoane cuantice pentru semnături digitale

Jetoane cuantice pentru semnături digitale

Marca temporală: 19 ianuarie 2023 8:49

Shalev Ben-David1 și Sau Sattath2

1Universitatea din Waterloo, David R. Cheriton School of Computer Science
2Universitatea Ben-Gurion din Negev, Departamentul de Informatică

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Pescarul a prins un pește cuantic. „Pescare, te rog, dă-mi drumul”, a rugat peștele, „și-ți voi îndeplini trei dorințe”. Pescarul a fost de acord. Peștele i-a oferit pescarului un computer cuantic, trei jetoane de semnare cuantică și cheia publică clasică. Peștele a explicat: „Pentru a vă semna cele trei dorințe, utilizați schema de semnătură tokenizată pe acest computer cuantic, apoi arătați semnătura dvs. valabilă regelui, care îmi datorează o favoare”.
Pescarul a folosit unul dintre jetoanele de semnare pentru a semna documentul „Dă-mi un castel!” și s-a repezit la palat. Regele a executat algoritmul clasic de verificare folosind cheia publică a peștelui și, întrucât era valabilă, regele s-a conformat.
Soția pescarului a vrut să semneze zece dorințe folosind cele două jetoane de semnare rămase. Pescarul nu a vrut să înșele și a navigat în secret să întâlnească peștele. „Pește, soția mea vrea să mai semneze zece urări”. Însă peștele nu a fost îngrijorat: „Am învățat criptografia cuantică urmând povestea anterioară (The Fisherman and His Wife de frații Grimm). Jetoanele cuantice sunt consumate în timpul semnării. Soția ta polinom nu poate semna nici măcar patru dorințe folosind cele trei jetoane de semnare pe care ți le-am dat”.
"Cum functioneazã?" se întrebă pescarul. „Ai auzit de bani cuantici? Acestea sunt stări cuantice care pot fi ușor verificate, dar sunt greu de copiat. Această schemă de semnătură cuantică tokenizată extinde schema monetară cuantică a lui Aaronson și Christiano, motiv pentru care jetoanele de semnătură nu pot fi copiate”.
„Schema dvs. are proprietăți luxoase suplimentare?” întrebă pescarul. „Da, schema are alte garanții de securitate: revocabilitate, testabilitate și securitate veșnică. În plus, dacă ești pe mare și telefonul tău cuantic are doar recepție clasică, poți folosi această schemă pentru a transfera valoarea banilor cuantici la țărm”, a spus peștele și a înotat.

Quantum Tokens for Digital Signatures PlatoBlockchain Data Intelligence. Vertical Search. Ai.

[Conținutul încorporat]

► Date BibTeX

► Referințe

[1] S. Aaronson. Protecție la copiere cuantică și bani cuantici. În Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, Franța, 15-18 iulie 2009, paginile 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharov, J. Anandan și L. Vaidman. Înțelesul funcției de undă. Fiz. Rev. A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson şi P. Christiano. Bani cuantici din subspații ascunse. În Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, SUA, 19 – 22 mai 2012, paginile 41–60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson şi P. Christiano. Bani cuantici din subspații ascunse. Theory of Computing, 9:349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias și M. Zhandry. Semnături unice și aplicații pentru autentificarea hibridă cuantică/clasică. În K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath și J. Chuzhoy, editori, Proccedings of the Annual ACM SIGACT Symposium on Theory of Computing, paginile 255–268. ACM, 2020, Cryptology ePrint Archive: Raport 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharov şi L. Vaidman. Măsurarea undei Schrödinger a unei singure particule. Literele de fizică A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Speranțe, temeri și ofuscarea software-ului. comun. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] CH Bennett, G. Brassard, S. Breidbart și S. Wiesner. Criptografia cuantică sau jetoane de metrou de nefalsificat. În Advances in Cryptology, paginile 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski și YT Kalai. Reduceri constructive post-cuantice. În Y. Dodis și T. Shrimpton, editori, Advances in Cryptology – CRYPTO 2022 – 42th Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, SUA, 15-18 august 2022, Proceedings, Part III, volumul 13509 din Lecture Notes in Computer Science, paginile 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 și A. Rosen. Imposibilitatea ofucării cu intrare auxiliară sau cu un simulator universal. În JA Garay și R. Gennaro, editori, Advances in Cryptology – CRYPTO 2014 – 34th Annual Cryptology Conference, Santa Barbara, CA, SUA, 17-21 august 2014, Proceedings, Part II, volumul 8617 din Lecture Notes in Computer Science, paginile 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 și K. Yang. Despre (im)posibilitatea de a ofusca programele. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombin. Porți Clifford prin deformarea codului. 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. Căutarea într-o agendă telefonică Quantum. Science, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / science.275.5300.627

[14] A. Behera, O. Sattath și U. Shinar. Jetoane cuantice tolerante la zgomot pentru MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh și M. Zhandry. Codurile de autentificare a mesajelor Quantum-Secure. În T. Johansson și PQ Nguyen, editori, Advances in Cryptology – EUROCRYPT 2013, 32th Annual International Conference on theory and Applications of Cryptographic Techniques, Atena, Grecia, 26-30 mai 2013. Proceedings, volumul 7881 din Computer Lecture Notes Știință, paginile 592–608. Springer, 2013.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve şi D. Gottesman. Calcule eficiente ale codificărilor pentru corectarea erorilor cuantice. Fiz. Rev. A, 56:76–82, iulie 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai și V. Zikas. Criptografie cu uși din spate de unică folosință. Cryptogr., 3(3):22, 2019, Cryptology ePrint Archive: Raport 2018/​352.
https://​/​doi.org/​10.3390/​cryptography3030022

[18] P. Christiano. Comunicare personală, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu și M. Zhandry. Coseturi și aplicații ascunse la criptografia neclonabilă, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan și N. Raghunathan. Limite pentru reducerea erorilor cu puține interogări cuantice. În Aproximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Aproximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and RANDOM 2005, Berkeley, CA, SUA, 22-24 august 2005, Proceedings, 245-256, 2005-XNUMX, XNUMX .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, GN Rothblum și M. Varia. Obscurcarea apartenenței la hiperplan. În D. Micciancio, editor, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zurich, Elveția, 9-11 februarie 2010. Proceedings, volumul 5978 din Lecture Notes in Computer Science, paginile 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie și ME Hellman. Noi direcții în criptografie. IEEE Trans. Teoria informației, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding și MO Rabin. Hyper-criptare și securitate veșnică. În H. Alt și A. Ferreira, editori, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes – Juan les Pins, Franța, 14-16 martie 2002, Proceedings, volumul 2285 din Lecture Notes in Computer Science, paginile 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 și P. Shor. Restaurarea stării cuantice și tomografie cu o singură copie pentru statele fundamentale ale hamiltonienilor. Fiz. Rev. Lett., 105:190503, noiembrie 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski și P. Shor. Bani cuantici din noduri. În Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, paginile 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gavinsky. Bani cuantici cu verificare clasică. În a 27-a Conferință anuală IEEE privind complexitatea computațională, paginile 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser și YT Kalai. Despre imposibilitatea ofucării cu intrare auxiliară. În 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 ​​octombrie 2005, Pittsburgh, PA, SUA, Proceedings, paginile 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou şi I. Kerenidis. Construcții noi pentru bani cuantici. În S. Beigi și R. König, editori, 10th Conference on the Quantum Computation, Communication and Cryptography, TQC 2015, 20-22 mai 2015, Bruxelles, Belgia, volumul 44 din LIPIcs, paginile 92–110. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2015.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] O. Goldreich. Fundamentele criptografiei – Vol. 2, Aplicații de bază. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler și T. Beth. Circuite cuantice eficiente pentru coduri de corectare a erorilor cuantice non-Qubit. Int. J. Găsit. Calculator. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz şi Y. Lindell. Introducere în criptografia modernă, ediția a doua. CRC Press, 2014.

[32] NA Lynch. Algoritmi distribuiti. Morgan Kaufmann, 1996.

[33] M. Mosca si D. Stebila. Monede cuantice, volumul 523 din Contemp. Math., paginile 35–47. Amer. Matematică. Soc., 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas și L. Perret. Criptanaliză non-cuantică a versiunii zgomotoase a schemei monetare cuantice a lui 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 și L. Perret. Criptanaliza algebrică a unei scheme monetare cuantice Cazul fără zgomot. În J. Katz, editor, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, SUA, 30 martie – 1 aprilie 2015, Proceedings, volumul 9020 din Note de curs în Informatică, paginile 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Numărarea subspațiilor unui spațiu vectorial finit — 1. Rezonanță, 15(11):977–987, 2010.
https:/​/​doi.org/​10.1007/​s12045-010-0114-5

[37] F. Pastawski, NY Yao, L. Jiang, MD Lukin și JI Cirac. Jetoane cuantice de nefalsificat tolerante la zgomot. Proceedings of the National Academy of Sciences, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian şi O. Sattath. Bani semi-cuantici. În Proceedings of the 1st ACM Conference on Advances in Financial Technologies, AFT 2019, Zurich, Elveția, 21-23 octombrie 2019, paginile 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] R. Radian şi O. Sattath. Bani semi-cuantici. Journal of Cryptology, 35(2), ianuarie 2022, arXiv: 1908.08889.
https:/​/​doi.org/​10.1007/​s00145-021-09418-8
arXiv: 1908.08889

[40] O. Sattath. Contracte Quantum Prudent cu aplicații la Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. Criptografie neclonabilă, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Shmueli. Bani cuantici cu cheie publică cu o bancă clasică. În S. Leonardi și A. Gupta, editori, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Roma, Italia, 20 – 24 iunie 2022, paginile 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Shmueli. Semnături tokenizate semi-cuantice. În Y. Dodis și T. Shrimpton, editori, Advances in Cryptology – CRYPTO 2022 – 42th Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, SUA, 15-18 august 2022, Proceedings, Part I, volumul 13507 din Lecture Notes in Computer Science, paginile 296–319. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, LK Grover și A. Patel. Un nou algoritm pentru căutarea cuantică în punct fix. Quantum Information & Computation, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto și N. Imoto. Numerar cuantic anonim. În Conferința ERATO despre Știința Informației Cuantice, 2003.

[46] D. Unruh. Criptare revocabilă Quantum cu lansare temporizată. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] D. Unruh. Calcul etern cu mai multe partide. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

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

[49] WK Wootters și WH Zurek. Un singur cuantic nu poate fi clonat. Nature, 299(5886):802–803, 1982.

[50] M. Zhong, MP Hedges, RL Ahlefeldt, JG Bartholomew, SE Beavan, SM Wittig, JJ Longdell și MJ Sellars. Nucleare adresabile optic se rotesc într-un solid cu un timp de coerență de șase ore. Nature, 517(7533):177–180, ianuarie 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M. Zhandry. Fulgerul cuantic nu lovește de două ori aceeași stare, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Fulgerul cuantic nu lovește niciodată aceeași stare de două ori. Sau: bani cuantici din ipoteze criptografice. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Citat de

[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 și P. Wallden, „Advances in quantum cryptography”, Progrese în optică și fotonică 12 4, 1012 (2020).

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

[3] Thomas Vidick și Tina Zhang, „Dovezi clasice ale cunoașterii cuantice”, arXiv: 2005.01691.

[4] Sau Sattath, „Contracte cuantice prudente cu aplicații la Bitcoin”, arXiv: 2204.12806.

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

[6] Roy Radian și Or Sattath, „Bani semi-cuantici”, arXiv: 1908.08889.

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

[8] Prabhanjan Ananth și Rolando L. La Placa, „Secure Software Leasing”, arXiv: 2005.05289.

[9] Sau Sattath și Shai Wyborski, „Unclonaable Decryptors from Quantum Copy-Protection”, arXiv: 2203.05866.

[10] Andrea Coladangelo și Or Sattath, „A Quantum Money Solution to the Blockchain Scalability Problem”, arXiv: 2002.11998.

[11] Jiahui Liu, Hart Montgomery și Mark Zhandry, „O altă rundă de spargere și câștigare de bani cuantici: cum să nu-l construiți din zăbrele și multe altele”, arXiv: 2211.11994.

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

[13] Sau Sattath, „Criptografie neclonabilă”, arXiv: 2210.14265.

[14] Amit Behera și Or Sattath, „Almost Public Quantum Coins”, arXiv: 2002.12438.

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

[16] Niraj Kumar, „Bani cuantici robusti, practic, fezabil cu verificare clasică”, arXiv: 1908.04114.

[17] Sau Sattath și Uriel Shinar, „Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism”, arXiv: 2212.08750.

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

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2023-01-20 14:01:05). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2023-01-20 14:01:00).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic