1Afdeling Wiskunde en Statistiek, Universiteit van Ottawa, Ontario, Canada
2Afdeling Computerwetenschappen, Universiteit Paderborn, Duitsland
3Afdeling Computerwetenschappen, Virginia Commonwealth University, Virginia, VS.
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Een centraal principe van theoretische cryptografie is de studie van de minimale aannames die nodig zijn om een bepaalde cryptografische primitief te implementeren. Eén zo'n primitief is het eenmalige geheugen (OTM), geïntroduceerd door Goldwasser, Kalai en Rothblum [CRYPTO 2008], een klassieke functionaliteit gemodelleerd naar een niet-interactieve 1-op-2 onbewuste overdracht, en dat is compleet voor eenmalige klassieke en kwantumprogramma's. Het is bekend dat veilige OTM's niet bestaan in het standaardmodel, zowel in de klassieke als in de kwantuminstellingen. Hier stellen we een schema voor voor het gebruik van kwantuminformatie, samen met de aanname van staatloze ($ ie $, herbruikbare) hardwaretokens, om statistisch veilige OTM's te bouwen. Via het semidefiniete programmeergebaseerde kwantumgamesraamwerk van Gutoski en Watrous [STOC 2007], bewijzen we de veiligheid voor een kwaadwillende ontvanger die maximaal 0.114 $ n $ adaptieve zoekopdrachten doet aan het token (voor $ n $ de sleutelgrootte), in het kwantum universeel composability-raamwerk, maar laat de kwestie van beveiliging open voor een veelvoud aan queries. Vergeleken met alternatieve schema's die zijn afgeleid uit de literatuur over kwantumgeld, is ons schema technologisch eenvoudig omdat het van het type "voorbereiden en meten" is. We geven ook twee onmogelijkheidsresultaten, waaruit blijkt dat bepaalde aannames in ons schema niet kunnen worden versoepeld.
Populaire samenvatting
► BibTeX-gegevens
► Referenties
[1] Scott Aaronson en Paul Christiano "Quantum Money from Hidden Subspaces" Proc. 44e symposium over computertheorie (STOC) 2012 41-60 (2012).
https: / / doi.org/ 10.1145 / 2213977.2213983
[2] Charles H. Bennett en Gilles Brassard "Kwantumcryptografie: distributie van openbare sleutels en munten gooien" Internationale conferentie over computers, systemen en signaalverwerking 175–179 (1984).
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025
[3] Shalev Ben-David en of Sattath "Quantum Tokens for Digital Signatures" (2018) arXiv: 1609.09047.
[4] Donald Beaver "Secure Multiparty Protocols and Zero-Knowledge Proof Systems Tolerating a Faulty Minority" Journal of Cryptology 4, 75-122 (1991).
https: / / doi.org/ 10.1007 / BF00196771
[5] Charles H. Bennett, Gilles Brassard, Claude Crépeau en Marie-Hélène Skubiszewska, "Practical Quantum Oblivious Transfer" CRYPTO'91 576, 351-366 (1992).
[6] Manuel Blum, Paul Feldman en Silvio Micali, "Non-Interactive Zero-Knowledge and Its Applications" 20e ACM STOC 103–112 (1988).
https: / / doi.org/ 10.1145 / 62212.62222
[7] Anne Broadbent, Gus Gutoski en Douglas Stebila, "Quantum One-Time Programmes" CRYPTO 2013, deel II 8043, 344-360 (2013).
https://doi.org/10.1007/978-3-642-40084-1_20
[8] Anne Broadbent, Sevag Gharibian en Hong-Sheng Zhou, "Quantum One-Time Memories from Stateless Hardware" (2015) arXiv: 1511.01363.
[9] Manuel Blum en Silvio Micali "Hoe cryptografisch sterke reeksen van pseudo-willekeurige bits te genereren" 23e FOCS 112–117 (1982).
https: / / doi.org/ 10.1137 / 0213053
[10] Anne Broadbent en Christian Schaffner "Quantum Cryptography Beyond Quantum Key Distribution" Designs, Codes and Cryptography 78, 351-382 (2016).
https://doi.org/10.1007/s10623-015-0157-4
[11] Stephen Boyd en Lieven Vandenberghe "Convex Optimization" Cambridge University Press (2004).
[12] Ran Canetti "Beveiliging en samenstelling van multiparty cryptografische protocollen" Journal of Cryptology 13, 143–202 (2000).
https: / / doi.org/ 10.1007 / s001459910006
[13] Ran Canetti "Universeel samengestelde beveiliging: een nieuw paradigma voor cryptografische protocollen" 42e FOCS 136–145 (2001).
https: / / doi.org/ 10.1109 / SFCS.2001.959888
[14] Ran Canetti, Yehuda Lindell, Rafail Ostrovsky en Amit Sahai, "Universeel samen te stellen beveiligde berekening voor twee en meerdere partijen" 34e ACM STOC 494-503 (2002).
https: / / doi.org/ 10.1145 / 509907.509980
[15] Ran Canetti, Yevgeniy Dodis, Rafael Pass en Shabsi Walfish, "Universeel samengestelde beveiliging met wereldwijde instellingen" TCC 2007 4392, 61–85 (2007).
https://doi.org/10.1007/978-3-540-70936-7_4
[16] Nishanth Chandran, Vipul Goyal en Amit Sahai, "Nieuwe constructies voor UC Secure Computation met Tamper-Proof Hardware" EUROCRYPT 2008 4965, 545-562 (2008).
https: / / doi.org/ 10.5555 / 1788414.1788445
[17] Seung Geol Choi, Jonathan Katz, Dominique Schröder, Arkady Yerukhimovich en Hong-Sheng Zhou, "(Efficient) Universally Composable Oblivious Transfer using a Minimal Number of Stateless Tokens" TCC 2014 8349, 638–662 (2014).
https://doi.org/10.1007/978-3-642-54242-8_27
[18] Man-Duen Choi "Volledig positieve lineaire kaarten op complexe matrices" Lineair Alg. Appl. 10, 285 (1975).
https://doi.org/10.1016/0024-3795(75)90075-0
[19] Kai-Min Chung, Marios Georgiou, Ching-Yi Lai en Vassilis Zikas, "Cryptography with Disposable Backdoors" Cryptography 3, 22 (2019).
https: / / doi.org/ 10.3390 / cryptography3030022
[20] Christian Cachin en Ueli Maurer "Onvoorwaardelijke beveiliging tegen aan het geheugen gebonden tegenstanders" Advances in Cryptology - CRYPTO 1997 292–306 (1997).
https: / / doi.org/ 10.1007 / BFb0052243
[21] Ivan Damgård, Serge Fehr, Louis Salvail en Christian Schaffner, "Cryptography In the Bounded Quantum-Storage Model" Symposium on Foundations of Computer Science - FOCS 2005 449-458 (2005).
https: / / doi.org/ 10.1109 / SFCS.2005.30
[22] Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail en Christian Schaffner, "Verbetering van de beveiliging van kwantumprotocollen via Commit-and-Open" CRYPTO 2009 5677, 408-427 (2009).
https://doi.org/10.1007/978-3-642-03356-8_24
[23] Frédéric Dupuis, Jesper Buus Nielsen en Louis Salvail, "Veilige tweepartijen kwantumevaluatie van unitairen tegen misdadigers" Vooruitgang in cryptologie - Proc. CRYPTO 2010-685 (706).
https://doi.org/10.1007/978-3-642-14623-7_37
[24] Frédéric Dupuis, Jesper Buus Nielsen en Louis Salvail, "Actief beveiligde evaluatie van twee partijen van elke kwantumoperatie" Vooruitgang in cryptologie - Proc. CRYPTO 2012 7417, 794-811 (2012).
https://doi.org/10.1007/978-3-642-32009-5_46
[25] Ivan Damgård en Alessandra Scafuro "Onvoorwaardelijk veilige en universeel samengestelde verplichtingen uit fysieke veronderstellingen" ASIACRYPT 2013, deel II 8270, 100–119 (2013).
https://doi.org/10.1007/978-3-642-42045-0_6
[26] Serge Fehr, Jonathan Katz, Fang Song, Hong-Sheng Zhou en Vassilis Zikas, "Feasibility and Completeness of Cryptographic Tasks in the Quantum World" TCC 2013 7785, 281–296 (2013).
https://doi.org/10.1007/978-3-642-36594-2_16
[27] Bill Fefferman en Shelby Kimmel "Quantum vs. Classical Proofs and Subset Verification" 43e International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) 117, 22: 1–22: 23 (2018).
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2018.22
[28] Dmitry Gavinsky "Quantum Money with Classical Verification" Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on 42–52 (2012).
https: / / doi.org/ 10.1109 / CCC.2012.10
[29] Shafi Goldwasser, Yael Tauman Kalai en Guy N. Rothblum, "Eenmalige programma's" CRYPTO 2008 5157, 39–56 (2008).
https://doi.org/10.1007/978-3-540-85174-5_3
[30] Shafi Goldwasser en Leonid A. Levin "Eerlijke berekening van algemene functies in aanwezigheid van immorele meerderheid" CRYPTO'90 537, 77–93 (1991).
https://doi.org/10.1007/3-540-38424-3_6
[31] Oded Goldreich, Silvio Micali en Avi Wigderson, "Hoe een mentaal spel of een volledigheidsstelling voor protocollen met eerlijke meerderheid te spelen", 19e ACM STOC 218–229 (1987).
https: / / doi.org/ 10.1145 / 3335741.3335755
[32] Vipul Goyal, Yuval Ishai, Amit Sahai, Ramarathnam Venkatesan en Akshay Wadia, "Founding Cryptography on Tamper-Proof Hardware Tokens" TCC 2010 5978, 308-326 (2010).
https://doi.org/10.1007/978-3-642-11799-2_19
[33] Gus Gutoski en John Watrous "Toward a general theory of quantum games" Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007) 565–574 (2007).
https: / / doi.org/ 10.1145 / 1250790.1250873
[34] Werner Heisenberg "Schwankungserscheinungen und Quantenmechanik" Zeitschrift fuer Physik 40, 501–506 (1927).
https: / / doi.org/ 10.1007 / BF01440827
[35] Sean Hallgren, Adam Smith en Fang Song, "Classical Cryptographic Protocols in a Quantum World" CRYPTO 2011 6841, 411-428 (2011).
https://doi.org/10.1007/978-3-642-22792-9_23
[36] Yuval Ishai, Manoj Prabhakaran en Amit Sahai, "Founding Cryptography on Oblivious Transfer - Efficiently" CRYPTO 2008 5157, 572-591 (2008).
https://doi.org/10.1007/978-3-540-85174-5_32
[37] Andrzej Jamiołkowski "Lineaire transformaties die sporen en positieve semi-definiëring van operators behouden" Rep. Math. Phys. 3, 275 (1972).
https://doi.org/10.1016/0034-4877(72)90011-0
[38] Jonathan Katz "Universeel samengestelde berekeningen van meerdere partijen met behulp van fraudebestendige hardware" EUROCRYPT 2007 4515, 115–128 (2007).
https://doi.org/10.1007/978-3-540-72540-4_7
[39] Joe Kilian "Founding Cryptography on Oblivious Transfer" 20e ACM STOC 20-31 (1988).
https: / / doi.org/ 10.1145 / 62212.62215
[40] Daniel Kraschewski en Jörn Müller-Quade "Compleetheidstheorema's met constructieve bewijzen voor eindige deterministische 2-partijfuncties" TCC 2011 6597, 364-381 (2011).
https://doi.org/10.1007/978-3-642-19571-6_22
[41] Daniel Kraschewski, Hemanta K. Maji, Manoj Prabhakaran en Amit Sahai, "A Full Characterization of Completeness for Two-Party Randomized Function Evaluation" EUROCRYPT 2014 8441, 659-676 (2014).
https://doi.org/10.1007/978-3-642-55220-5_36
[42] Yi-Kai Liu "Eenmalige herinneringen opbouwen uit geïsoleerde qubits" ITCS 2014 269–286 (2014).
https: / / doi.org/ 10.1145 / 2554797.2554823
[43] Yi-Kai Liu "Eenmalige beveiliging voor eenmalige herinneringen in het geïsoleerde Qubits-model" CRYPTO 2014, deel II 8617, 19–36 (2014).
https://doi.org/10.1007/978-3-662-44381-1_2
[44] Yi-Kai Liu "Privacy Amplification in the Isolated Qubits Model" EUROCRYPT 2015, Part II 9057, 785-814 (2015).
https://doi.org/10.1007/978-3-662-46803-6_26
[45] Huijia Lin, Rafael Pass en Muthuramakrishnan Venkitasubramaniam, "Een uniform raamwerk voor gelijktijdige beveiliging: universele composability vanuit stand-alone niet-kneedbaarheid" 41e ACM STOC 179-188 (2009).
https: / / doi.org/ 10.1145 / 1536414.1536441
[46] Ueli M. Maurer "Protocollen voor geheime sleutelovereenkomst door openbare discussie op basis van gemeenschappelijke informatie" Advances in Cryptology - CRYPTO 1992 740, 461-470 (1992).
https://doi.org/10.1007/3-540-48071-4_32
[47] Hemanta K. Maji, Manoj Prabhakaran en Mike Rosulek, "Complexiteit van computerproblemen met meerdere partijen: de zaak van symmetrische veilige functie-evaluatie door twee partijen" TCC 2 2009, 5444–256 (273).
https://doi.org/10.1007/978-3-642-00457-5_16
[48] Hemanta K. Maji, Manoj Prabhakaran en Mike Rosulek, "A Zero-One Law for Cryptographic Complexity with Respect to Computational UC Security" CRYPTO 2010 6223, 595–612 (2010).
https://doi.org/10.1007/978-3-642-14623-7_32
[49] Ueli Maurer en Renato Renner "Abstracte cryptografie" ICS 2011 1-21 (2011).
[50] Silvio Micali en Phillip Rogaway "Secure Computation (Abstract)" CRYPTO'91 576, 392-404 (1992).
https://doi.org/10.1007/3-540-46766-1_32
[51] Abel Molina, Thomas Vidick en John Watrous, "Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money" Theory of Quantum Computation, Communication, and Cryptography 7582, 45–64 (2013).
https://doi.org/10.1007/978-3-642-35656-8_4
[52] MA Nielsen en IL Chuang "Quantum Computation and Quantum Information" Cambridge University Press (2000).
[53] Fernando Pastawski, Norman Y Yao, Liang Jiang, Mikhail D Lukin en J Ignacio Cirac, "Onvergetelijke geluidstolerante kwantumtokens" Proceedings of the National Academy of Sciences 109, 16079-16082 (2012).
https: / / doi.org/ 10.1073 / pnas.1203552109
[54] Manoj Prabhakaran en Mike Rosulek "Cryptografische complexiteit van rekenproblemen met meerdere partijen: classificaties en scheidingen" CRYPTO 2008 5157, 262–279 (2008).
https://doi.org/10.1007/978-3-540-85174-5_15
[55] Manoj Prabhakaran en Amit Sahai "Nieuwe noties van veiligheid: bereiken van universele composability zonder betrouwbare setup" 36e ACM STOC 242–251 (2004).
https: / / doi.org/ 10.1145 / 1007352.1007394
[56] Birgit Pfitzmann en Michael Waidner "Een model voor asynchrone reactieve systemen en de toepassing ervan om berichtoverdracht te beveiligen" Proc. 22e IEEE-symposium over beveiliging en privacy (S&P) 2001-184 (200).
https: / / doi.org/ 10.1109 / SECPRI.2001.924298
[57] Marco Túlio Quintino, Qingxiuxiong Dong, Atsushi Shimbo, Akihito Soeda en Mio Murao, "Onbekende kwantumtransformaties omkeren: universeel kwantumcircuit voor het omkeren van algemene unitaire operaties" Phys. Rev. Lett. 123, 210502 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.123.210502
[58] Renato Renner "Security of Quantum Key Distribution" -scriptie (2008).
https: / / doi.org/ 10.1142 / S0219749908003256
[59] Dominique Unruh "Universally Composable Quantum Multi-party Computation" EUROCRYPT 2010 6110, 486-505 (2010).
https://doi.org/10.1007/978-3-642-13190-5_25
[60] Dominique Unruh "Everlasting Multi-party Computation" CRYPTO 2013, Part II 8043, 380–397 (2013).
https://doi.org/10.1007/978-3-642-40084-1_22
[61] Dominique Unruh "Revocable Quantum Timed-Release Encryption" EUROCRYPT 2014 8441, 129–146 (2014).
https://doi.org/10.1007/978-3-642-55220-5_8
[62] John Watrous "Lecture 7: Semidefinite programming" (2011) Laatste versie beschikbaar op: https: / / cs.uwaterloo.ca/ watrous / TQI-notes /.
https: / / cs.uwaterloo.ca/ ~ watrous / TQI-notes /
[63] Stephen Wiesner "Conjugate coding" ACM SIGACT News 15, 78–88 (1983) Origineel artikel geschreven rond 1970.
https: / / doi.org/ 10.1145 / 1008908.1008920
[64] Andreas Winter "Coderingsstelling en sterke conversie voor kwantumkanalen" IEEE Transactions on Information Theory 45, 2481–2485 (1999).
https: / / doi.org/ 10.1109 / 18.796385
[65] Stephanie Wehner, Christian Schaffner en Barbara M. Terhal, "Cryptography from Noisy Storage" Physical Review Letters 100, 220502 (2008).
https: / / doi.org/ 10.1103 / PhysRevLett.100.220502
[66] Stephanie Wehner en Andreas Winter "Entropische onzekerheidsrelaties - een onderzoek" New J. Phys. 12, 025009 (2010).
https://doi.org/10.1088/1367-2630/12/2/025009
[67] William K. Wootters en Wojciech H. Zurek "Een enkel kwantum kan niet worden gekloond" Nature 299, 802-803 (1982).
https: / / doi.org/ 10.1038 / 299802a0
[68] Andrew Chi-Chih Yao "Theorie en toepassingen van luikfuncties" 23e FOCS 80–91 (1982).
https: / / doi.org/ 10.1109 / SFCS.1982.45
Geciteerd door
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.
Coinsmart. Beste Bitcoin-beurs in Europa
Bron: https://quantum-journal.org/papers/q-2021-04-08-429/
