Kvantni žetoni za digitalne podpise

Kvantni žetoni za digitalne podpise

Časovni žig: 19. januar 2023 8

Šalev Ben-David1 in Ali Sattath2

1Univerza Waterloo, Šola računalništva David R. Cheriton
2Univerza Ben-Gurion v Negevu, oddelek za računalništvo

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Ribič je ujel kvantno ribo. "Ribič, prosim, izpusti me," je rotila riba, "in izpolnila ti bom tri želje." Ribič se je strinjal. Riba je ribiču dala kvantni računalnik, tri kvantne podpisne žetone in svoj klasični javni ključ. Riba je pojasnila: »da podpišeš svoje tri želje, uporabi tokenizirano podpisno shemo na tem kvantnem računalniku, nato pa pokaži svoj veljaven podpis kralju, ki mi dolguje uslugo«.
Ribič je z enim od podpisnih žetonov podpisal dokument »daj mi grad!« in odhitel v palačo. Kralj je izvedel klasični verifikacijski algoritem z uporabo ribjega javnega ključa in ker je bil veljaven, se je kralj odločil.
Ribičeva žena je želela podpisati deset želja z njunima preostalima podpisnima žetonoma. Ribič ni hotel goljufati in je skrivaj odplul ribi naproti. "Riba, moja žena želi podpisati še deset želja." A ribe ni skrbelo: »Kvantne kriptografije sem se naučil po prejšnji zgodbi (Ribiča in njegova žena bratov Grimm). Kvantni žetoni se porabijo med podpisovanjem. Tvoja polinomska žena ne more niti podpisati štirih želja s tremi podpisnimi žetoni, ki sem ti jih dal.
"Kako deluje?" se je začudil ribič. »Ste že slišali za kvantni denar? To so kvantna stanja, ki jih je mogoče zlahka preveriti, vendar jih je težko kopirati. Ta tokenizirana shema kvantnega podpisa razširja shemo kvantnega denarja Aaronsona in Christiana, zato podpisnih žetonov ni mogoče kopirati.
"Ali ima vaša shema dodatne modne lastnosti?" je vprašal ribič. »Da, shema ima druga varnostna jamstva: preklicnost, možnost testiranja in večno varnost. Poleg tega, če ste na morju in ima vaš kvantni telefon samo klasičen sprejem, lahko uporabite to shemo za prenos vrednosti kvantnega denarja na obalo,« je rekla ribica in odplavala.

Kvantni žetoni za digitalne podpise PlatoBlockchain Data Intelligence. Navpično iskanje. Ai.

[Vgrajeni vsebina]

► BibTeX podatki

► Reference

[1] S. Aaronson. Kvantna zaščita pred kopiranjem in kvantni denar. V zborniku 24. letne konference IEEE o računalniški kompleksnosti, CCC 2009, Pariz, Francija, 15.–18. julij 2009, strani 229–242, 2009.
https: / / doi.org/ 10.1109 / CCC.2009.42

[2] Y. Aharonov, J. Anandan in L. Vaidman. Pomen valovne funkcije. Phys. Rev. A, 47:4616–4626, 1993.
https: / / doi.org/ 10.1103 / PhysRevA.47.4616

[3] S. Aaronson in P. Christiano. Kvantni denar iz skritih podprostorov. V zborniku 44. simpozija o teoriji računalništva, STOC 2012, New York, NY, ZDA, 19. – 22. maj 2012, strani 41–60, 2012.
https: / / doi.org/ 10.1145 / 2213977.2213983

[4] S. Aaronson in P. Christiano. Kvantni denar iz skritih podprostorov. Teorija računalništva, 9: 349–401, 2013.
https: / / doi.org/ 10.4086 / toc.2013.v009a009

[5] R. Amos, M. Georgiou, A. Kiayias in M. Zhandry. Enkratni podpisi in aplikacije za hibridno kvantno/klasično avtentikacijo. V K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath in J. Chuzhoy, uredniki, Zbornik letnega simpozija ACM SIGACT o teoriji računalništva, strani 255–268. ACM, 2020, arhiv ePrint za kriptologijo: poročilo 2020/​107.
https: / / doi.org/ 10.1145 / 3357713.3384304

[6] Y. Aharonov in L. Vaidman. Merjenje Schrödingerjevega valovanja posameznega delca. Physics Letters A, 178(1):38 – 42, 1993.
https:/​/​doi.org/​10.1016/​0375-9601(93)90724-E

[7] B. Barak. Upi, strahovi in ​​zamegljenost programske opreme. Komun. ACM, 59(3):88–96, 2016.
https: / / doi.org/ 10.1145 / 2757276

[8] C. H. Bennett, G. Brassard, S. Breidbart in S. Wiesner. Kvantna kriptografija ali neponareljivi žetoni podzemne železnice. V Napredek v kriptologiji, strani 267–275. Springer, 1983.
https:/​/​doi.org/​10.1007/​978-1-4757-0602-4_26

[9] N. Bitansky, Z. Brakerski in YT Kalai. Konstruktivne postkvantne redukcije. V Y. Dodis in T. Shrimpton, urednika, Advances in Cryptology – CRYPTO 2022 – 42. letna mednarodna kriptološka konferenca, CRYPTO 2022, Santa Barbara, CA, ZDA, 15.–18. avgust 2022, zbornik, del III, zvezek 13509 predavanja Notes in Computer Science, strani 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 in A. Rosen. Nezmožnost zakrivanja s pomožnim vhodom ali univerzalnim simulatorjem. V JA Garay in R. Gennaro, urednika, Advances in Cryptology – CRYPTO 2014 – 34. letna konferenca o kriptologiji, Santa Barbara, CA, ZDA, 17.–21. strani 2014–8617. Springer, 71.
https:/​/​doi.org/​10.1007/​978-3-662-44381-1_5

[11] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan in K. Yang. O (ne)možnosti zamegljevanja programov. J. ACM, 59(2):6, 2012.
https: / / doi.org/ 10.1145 / 2160158.2160159

[12] H. Bombin. Cliffordova vrata z deformacijo kode. 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. Iskanje po kvantnem telefonskem imeniku. Znanost, 275(5300):627–628, 1997.
https: / / doi.org/ 10.1126 / znanost.275.5300.627

[14] A. Behera, O. Sattath in U. Shinar. Kvantni žetoni, odporni na hrup za MAC, 2021.
https://​/​doi.org/​10.48550/​ARXIV.2105.05016

[15] D. Boneh in M. Zhandry. Kode za preverjanje pristnosti sporočil Quantum-Secure. V T. Johansson in PQ Nguyen, urednika, Advances in Cryptology – EUROCRYPT 2013, 32. letna mednarodna konferenca o teoriji in aplikacijah kriptografskih tehnik, Atene, Grčija, 26.–30. Znanost, strani 2013–7881. Springer, 592.
https:/​/​doi.org/​10.1007/​978-3-642-38348-9_35

[16] R. Cleve in D. Gottesman. Učinkoviti izračuni kodiranja za kvantno popravljanje napak. Phys. Rev. A, 56:76–82, julij 1997.
https: / / doi.org/ 10.1103 / PhysRevA.56.76

[17] K. Chung, M. Georgiou, C. Lai in V. Zikas. Kriptografija z zakulisnimi vrati za enkratno uporabo. Cryptogr., 3(3):22, 2019, Arhiv ePrint za kriptologijo: poročilo 2018/​352.
https: / / doi.org/ 10.3390 / kriptografija 3030022

[18] P. Christiano. Osebna komunikacija, 2015.

[19] A. Coladangelo, J. Liu, Q. Liu in M. Zhandry. Skrite kozete in aplikacije za kriptografijo, ki je ni mogoče klonirati, 2021, arXiv: 2107.05692.
arXiv: 2107.05692

[20] S. Chakraborty, J. Radhakrishnan in N. Raghunathan. Meje za zmanjšanje napak z nekaj kvantnimi poizvedbami. V Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8. mednarodna delavnica o aproksimacijskih algoritmih za probleme kombinatorne optimizacije, APPROX 2005 in RANDOM 2005, Berkeley, CA, ZDA, 22. in 24. avgust 2005, zbornik, strani 245–256, 2005 .
https: / / doi.org/ 10.1007 / 11538462_21

[21] R. Canetti, G. N. Rothblum in M. Varia. Zakrivanje članstva v hiperravnini. V D. Micciancio, urednik, Theory of Cryptography, 7th Theory of Cryptography Conference, TCC 2010, Zürich, Švica, 9.–11. februar 2010. Zbornik predavanj, zvezek 5978 Lecture Notes in Computer Science, strani 72–89. Springer, 2010.
https:/​/​doi.org/​10.1007/​978-3-642-11799-2_5

[22] W. Diffie in M. E. Hellman. Nove smeri v kriptografiji. IEEE Trans. Teorija informacij, 22(6):644–654, 1976.
https: / / doi.org/ 10.1109 / TIT.1976.1055638

[23] YZ Ding in MO Rabin. Hiperšifriranje in večna varnost. V H. Alt in A. Ferreira, urednika, STACS 2002, 19. letni simpozij o teoretičnih vidikih računalništva, Antibes – Juan les Pins, Francija, 14.–16. marec 2002, Zbornik predavanj, zvezek 2285 zapiskov predavanj iz računalništva, strani 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 in P. Shor. Kvantna obnovitev stanja in tomografija ene kopije za osnovna stanja hamiltonianov. Phys. Rev. Lett., 105:190503, november 2010.
https: / / doi.org/ 10.1103 / PhysRevLett.105.190503

[25] E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski in P. Shor. Kvantni denar iz vozlov. V zborniku 3. konference o inovacijah v teoretični računalniški znanosti, strani 276–289. ACM, 2012.
https: / / doi.org/ 10.1145 / 2090236.2090260

[26] D. Gavinskega. Kvantni denar s klasičnim preverjanjem. Na 27. letni konferenci IEEE o računalniški kompleksnosti, strani 42–52. IEEE, 2012.
https: / / doi.org/ 10.1109 / CCC.2012.10

[27] S. Goldwasser in Y. T. Kalai. O nezmožnosti zakrivanja s pomožnim vnosom. Na 46. letnem simpoziju IEEE o temeljih računalništva (FOCS 2005), 23.–25. oktober 2005, Pittsburgh, PA, ZDA, zbornik, strani 553–562, 2005.
https: / / doi.org/ 10.1109 / SFCS.2005.60

[28] M. Georgiou in I. Kerenidis. Novogradnje za kvantni denar. V S. Beigi in R. König, urednika, 10. konferenca o teoriji kvantnega računalništva, komunikacije in kriptografije, TQC 2015, 20.–22. maj 2015, Bruselj, Belgija, 44. zvezek LIPIcs, strani 92–110. Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2015.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2015.92

[29] O. Goldreich. Temelji kriptografije – Vol. 2, Osnovne aplikacije. Cambridge University Press, 2004.

[30] M. Grassl, M. Rötteler in T. Beth. Učinkovita kvantna vezja za ne-Qubit kvantne kode za popravljanje napak. Int. J. Najdeno. Računalništvo. Sci., 14(5):757–776, 2003.
https: / / doi.org/ 10.1142 / S0129054103002011

[31] J. Katz in Y. Lindell. Uvod v sodobno kriptografijo, druga izdaja. CRC Press, 2014.

[32] N. A. Lynch. Porazdeljeni algoritmi. Morgan Kaufmann, 1996.

[33] M. Mosca in D. Stebila. Kvantni kovanci, zvezek 523 Contemp. Math., strani 35–47. Amer. matematika Soc., 2010.

[34] MC Pena, RD Díaz, J. Faugère, LH Encinas in L. Perret. Nekvantna kriptoanaliza hrupne različice Aaronson-Christianove sheme kvantnega denarja. IET Information Security, 13(4):362–366, 2019.
https://​/​doi.org/​10.1049/​iet-ifs.2018.5307

[35] MC Pena, J. Faugère in L. Perret. Algebraična kriptoanaliza kvantne denarne sheme. Primer brez šuma. V J. Katzu, uredniku, Public-Key Cryptography – PKC 2015 – 18th IACR International Conference on Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, ZDA, 30. marec – 1. april 2015, zbornik, zvezek 9020 zapiskov predavanj v Računalništvu, strani 194–213. Springer, 2015.
https:/​/​doi.org/​10.1007/​978-3-662-46447-2_9

[36] A. Prasad. Štetje podprostorov končnega vektorskega prostora — 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 in J. I. Cirac. Neponareljivi kvantni žetoni, odporni na hrup. Zbornik Nacionalne akademije znanosti, 109(40):16079–16082, 2012.
https: / / doi.org/ 10.1073 / pnas.1203552109

[38] R. Radian in O. Sattath. Polkvantni denar. V zborniku 1. konference ACM o napredku v finančnih tehnologijah, AFT 2019, Zürich, Švica, 21.–23. oktober 2019, strani 132–146. ACM, 2019, arXiv: 1908.08889.
https: / / doi.org/ 10.1145 / 3318041.3355462
arXiv: 1908.08889

[39] R. Radian in O. Sattath. Polkvantni denar. 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. Quantum Prudent Contracts z aplikacijami za Bitcoin, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2204.12806

[41] O. Sattath. Neklonirana kriptografija, 2022.
https://​/​doi.org/​10.48550/​ARXIV.2210.14265

[42] O. Šmueli. Kvantni denar z javnim ključem s klasično banko. V S. Leonardi in A. Gupta, urednika, STOC '22: 54. letni simpozij ACM SIGACT o teoriji računalništva, Rim, Italija, 20. – 24. junij 2022, strani 790–803. ACM, 2022.
https: / / doi.org/ 10.1145 / 3519935.3519952

[43] O. Šmueli. Polkvantni tokenizirani podpisi. V Y. Dodis in T. Shrimpton, urednika, Advances in Cryptology – CRYPTO 2022 – 42. letna mednarodna kriptološka konferenca, CRYPTO 2022, Santa Barbara, CA, ZDA, 15.–18. avgust 2022, zbornik, I. del, zvezek 13507 predavanja Notes in Computer Science, strani 296–319. Springer, 2022.
https:/​/​doi.org/​10.1007/​978-3-031-15802-5_11

[44] T. Tulsi, L. K. Grover in A. Patel. Nov algoritem za kvantno iskanje s fiksno točko. Kvantne informacije in računanje, 6(6):483–494, 2006.
http://​/​portal.acm.org/​citation.cfm?id=2011693

[45] Y. Tokunaga, T. Okamoto in N. Imoto. Anonimni kvantni denar. Na konferenci ERATO o kvantni informacijski znanosti, 2003.

[46] D. Unruh. Preklicno kvantno časovno sproščeno šifriranje. J. ACM, 62(6):49:1–49:76, 2015.
https: / / doi.org/ 10.1145 / 2817206

[47] D. Unruh. Večno večstransko računanje. J. Cryptol., 31(4):965–1011, 2018.
https: / / doi.org/ 10.1007 / s00145-018-9278-z

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

[49] W. K. Wootters in W. H. Zurek. Enega kvanta ni mogoče klonirati. Narava, 299(5886):802–803, 1982.

[50] M. Zhong, M. P. Hedges, R. L. Ahlefeldt, J. G. Bartholomew, S. E. Beavan, S. M. Wittig, J. J. Longdell in M. J. Sellars. Optično naslovljivi jedrski vrtljaji v trdni snovi s šesturnim koherenčnim časom. Narava, 517(7533):177–180, januar 2015.
https: / / doi.org/ 10.1038 / nature14025

[51] M. Zhandry. Kvantna strela nikoli ne udari dvakrat v isto stanje, 2017, arXiv: 1711.02276.
arXiv: 1711.02276

[52] M. Zhandry. Kvantna strela nikoli ne udari dvakrat v isto stanje. Ali: Kvantni denar iz kriptografskih predpostavk. J. Cryptol., 34(1):6, 2021, arXiv: 1711.02276.
https: / / doi.org/ 10.1007 / s00145-020-09372-x
arXiv: 1711.02276

Navedel

[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 in P. Wallden, »Napredek v kvantni kriptografiji«, Napredek v optiki in fotoniki 12 4, 1012 (2020).

[2] Douglas Scott, "Znanstvene prevare, fizikalne potegavščine in astronomske norčije", arXiv: 2103.17057.

[3] Thomas Vidick in Tina Zhang, "Klasični dokazi kvantnega znanja", arXiv: 2005.01691.

[4] Ali Sattath, »Kvantno preudarne pogodbe z aplikacijami za Bitcoin«, arXiv: 2204.12806.

[5] Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry in Ruizhe Zhang, »Novi pristopi za kvantno zaščito pred kopiranjem«, arXiv: 2004.09674.

[6] Roy Radian in Or Sattath, »Polkvantni denar«, arXiv: 1908.08889.

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

[8] Prabhanjan Ananth in Rolando L. La Placa, »Varni zakup programske opreme«, arXiv: 2005.05289.

[9] Ali Sattath in Shai Wyborski, »Uncloneable Decryptors from Quantum Copy-Protection«, arXiv: 2203.05866.

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

[11] Jiahui Liu, Hart Montgomery in Mark Zhandry, »Še en krog razbijanja in ustvarjanja kvantnega denarja: kako ga ne zgraditi iz rešetk in še več«, arXiv: 2211.11994.

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

[13] Ali Sattath, »Neklonirana kriptografija«, arXiv: 2210.14265.

[14] Amit Behera in Or Sattath, "Skoraj javni kvantni kovanci", arXiv: 2002.12438.

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

[16] Niraj Kumar, "Praktično izvedljiv robusten kvantni denar s klasično verifikacijo", arXiv: 1908.04114.

[17] Ali Sattath in Uriel Shinar, »Kvantna amnezija pušča kriptografske spomine: Opomba o kvantnem skepticizmu«, arXiv: 2212.08750.

[18] Nir Bitansky, Zvika Brakerski in Yael Tauman Kalai, »Konstruktivne postkvantne redukcije«, arXiv: 2203.02314.

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2023-01-20 14:01:05). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2023-01-20 14:01:00).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal