{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T20:25:00Z","timestamp":1754598300029,"version":"3.40.5"},"reference-count":33,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T00:00:00Z","timestamp":1688601600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001321","name":"National Research Foundation","doi-asserted-by":"crossref","award":["NRF-NRFF2013-13"],"award-info":[{"award-number":["NRF-NRFF2013-13"]}],"id":[{"id":"10.13039\/501100001321","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education, Singapore","doi-asserted-by":"crossref","award":["MOE2012- T3-1-009"],"award-info":[{"award-number":["MOE2012- T3-1-009"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Research Foundation and Agence Nationale de la Recherche","award":["NRF2017-NRF-ANR004"],"award-info":[{"award-number":["NRF2017-NRF-ANR004"]}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["20QT21_18772"],"award-info":[{"award-number":["20QT21_18772"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["FA9550-19-1-0202"],"award-info":[{"award-number":["FA9550-19-1-0202"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We study the task of encryption with certified deletion (ECD) introduced by Broadbent and Islam (2020), but in a device-independent setting: we show that it is possible to achieve this task even when the honest parties do not trust their quantum devices. Moreover, we define security for the ECD task in a composable manner and show that our ECD protocol satisfies conditions that lead to composable security. Our protocol is based on device-independent quantum key distribution (DIQKD), and in particular the parallel DIQKD protocol based on the magic square non-local game, given by Jain, Miller and Shi (2020). To achieve certified deletion, we use a property of the magic square game observed by Fu and Miller (2018), namely that a two-round variant of the game can be used to certify deletion of a single random bit. In order to achieve certified deletion security for arbitrarily long messages from this property, we prove a parallel repetition theorem for two-round non-local games, which may be of independent interest.<\/jats:p>","DOI":"10.22331\/q-2023-07-06-1047","type":"journal-article","created":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T13:29:18Z","timestamp":1688650158000},"page":"1047","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":3,"title":["Composably secure device-independent encryption with certified deletion"],"prefix":"10.22331","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8630-0113","authenticated-orcid":false,"given":"Srijita","family":"Kundu","sequence":"first","affiliation":[{"name":"Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4872-158X","authenticated-orcid":false,"given":"Ernest Y.-Z.","family":"Tan","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Physics, ETH Z\u00fcrich, Switzerland."},{"name":"Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2023,7,6]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Nati Aharon, Andr\u00e9 Chailloux, Iordanis Kerenidis, Serge Massar, Stefano Pironio, and Jonathan Silman, ``Weak coin flipping in a device-independent setting'' Theory of Quantum Computation, Communication, and Cryptography 1-12 (2014).","DOI":"10.1007\/978-3-642-54429-3_1"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Rotem Arnon-Friedman, Fr\u00e9d\u00e9ric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick, ``Practical device-independent quantum cryptography via entropy accumulation'' Nature Communications 9, 459 (2018).","DOI":"10.1038\/s41467-017-02307-4"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Nati Aharon, Serge Massar, Stefano Pironio, and Jonathan Silman, ``Device-independent bit commitment based on the CHSH inequality'' New Journal of Physics 18, 025014 (2016).","DOI":"10.1088\/1367-2630\/18\/2\/025014"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Charles H. Bennettand Gilles Brassard ``Quantum cryptography: Public key distribution and coin tossing'' Proceedings of International Conference on Computers, Systems and Signal Processing 175 (1984).","DOI":"10.1016\/j.tcs.2011.08.039"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Jonathan Barrett, Roger Colbeck, and Adrian Kent, ``Memory Attacks on Device-Independent Quantum Cryptography'' Physical Review Letters 110, 010503 (2013).","DOI":"10.1103\/PhysRevLett.110.010503"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Anne Broadbentand Rabib Islam ``Quantum Encryption with Certified Deletion'' Theory of Cryptography 92\u2013122 (2020).","DOI":"10.1007\/978-3-030-64381-2_4"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Michael Ben-Or, Micha\u0142 Horodecki, Debbie W. Leung, Dominic Mayers, and Jonathan Oppenheim, ``The Universal Composable Security of Quantum Key Distribution'' Theory of Cryptography 386\u2013406 (2005).","DOI":"10.1007\/978-3-540-30576-7_21"},{"key":"7","unstructured":"Mohammad Bavarian, Thomas Vidick, and Henry Yuen, ``Anchoring Games for Parallel Repetition'' https:\/\/arxiv.org\/abs\/1509.07466 (2015)."},{"key":"8","doi-asserted-by":"publisher","unstructured":"Mohammad Bavarian, Thomas Vidick, and Henry Yuen, ``Hardness Amplification for Entangled Games via Anchoring'' Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing 303\u2013316 (2017).","DOI":"10.1145\/3055399.3055433"},{"key":"9","doi-asserted-by":"publisher","unstructured":"J. Lawrence Carterand Mark N. Wegman ``Universal classes of hash functions'' Journal of Computer and System Sciences 18, 143\u2013154 (1979).","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Honghao Fuand Carl A. Miller ``Local randomness: Examples and application'' Physical Review A 97, 032324 (2018).","DOI":"10.1103\/PhysRevA.97.032324"},{"key":"11","unstructured":"Alexandru Gheorghiu, Tony Metger, and Alexander Poremba, ``Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more'' https:\/\/arxiv.org\/abs\/2201.13445 (2022)."},{"key":"12","doi-asserted-by":"publisher","unstructured":"Thomas Holenstein ``Parallel Repetition: Simplifications and the No-Signaling Case'' Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing 411\u2013419 (2007).","DOI":"10.1145\/1250790.1250852"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Rahul Jainand Srijita Kundu ``A Direct Product Theorem for One-Way Quantum Communication'' Proceedings of the 36th IEEE Annual Computational Complexity Conference (CCC 2021) 27:1\u201327:28 (2021).","DOI":"10.4230\/LIPIcs.CCC.2021.27"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Rahul Jain, Carl A. Miller, and Yaoyun Shi, ``Parallel Device-Independent Quantum Key Distribution'' IEEE Transactions on Information Theory 66, 5567\u20135584 (2020).","DOI":"10.1109\/TIT.2020.2986740"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Rahul Jain, Attila Pereszl\u00e9nyi, and Penghui Yao, ``A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions'' 2014 IEEE 29th Conference on Computational Complexity (CCC '14) 209\u2013216 (2014).","DOI":"10.1109\/CCC.2014.29"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick, ``Entangled Games are Hard to Approximate'' 2008 49th Annual IEEE Symposium on Foundations of Computer Science 447\u2013456 (2008).","DOI":"10.1109\/FOCS.2008.8"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan, ``A device-independent protocol for XOR oblivious transfer'' Quantum 6, 725 (2022).","DOI":"10.22331\/q-2022-05-30-725"},{"key":"18","unstructured":"Srijita Kunduand Ernest Y.-Z. Tan ``Device-independent uncloneable encryption'' https:\/\/arxiv.org\/abs\/2210.01058 (2022)."},{"key":"19","doi-asserted-by":"publisher","unstructured":"Norbert L\u00fctkenhaus, Ashutosh Marwah, and Dave Touchette, ``Erasable Bit Commitment From Temporary Quantum Trust'' IEEE Journal on Selected Areas in Information Theory 1, 536\u2013554 (2020).","DOI":"10.1109\/JSAIT.2020.3017054"},{"key":"20","unstructured":"Ueli Maurerand Renato Renner ``Abstract Cryptography'' The Second Symposium on Innovations in Computer Science, ICS 2011 1\u201321 (2011)."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Stefano Pironio, Antonio Ac\u00edn, Nicolas Brunner, Nicolas Gisin, Serge Massar, and Valerio Scarani, ``Device-independent quantum key distribution secure against collective attacks'' New Journal of Physics 11, 045021 (2009).","DOI":"10.1088\/1367-2630\/11\/4\/045021"},{"key":"22","unstructured":"Christopher Portmannand Renato Renner ``Cryptographic security of quantum key distribution'' https:\/\/arxiv.org\/abs\/1409.3525 (2014)."},{"key":"23","doi-asserted-by":"publisher","unstructured":"Anup Rao ``Parallel Repetition in Projection Games and a Concentration Bound'' Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing 1\u201310 (2008).","DOI":"10.1145\/1374376.1374378"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Ran Raz ``A Parallel Repetition Theorem'' Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing 447\u2013456 (1995).","DOI":"10.1145\/225058.225181"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Renato Renner ``Security of Quantum Key Distribution'' thesis (2005).","DOI":"10.3929\/ethz-a-005115027"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Jonathan Silman, Andr\u00e9 Chailloux, Nati Aharon, Iordanis Kerenidis, Stefano Pironio, and Serge Massar, ``Fully distrustful quantum bit commitment and coin flipping'' Physical Review Letters 106, 220501 (2011).","DOI":"10.1103\/PhysRevLett.106.220501"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Marco Tomamicheland Anthony Leverrier ``A largely self-contained and complete security proof for quantum key distribution'' Quantum 1, 14 (2017).","DOI":"10.22331\/q-2017-07-14-14"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Dominique Unruh ``Revocable Quantum Timed-Release Encryption'' Advances in Cryptology \u2013 EUROCRYPT 2014 129\u2013146 (2014).","DOI":"10.1007\/978-3-642-55220-5_8"},{"key":"29","unstructured":"Bart van der Vecht, Xavier Coiteaux-Roy, and Boris \u0160kori\u0107, ``Can't Touch This: unconditional tamper evidence from short keys'' https:\/\/arxiv.org\/abs\/2006.02476 (2020)."},{"key":"30","unstructured":"Thomas Vidick ``Parallel DIQKD from parallel repetition'' https:\/\/arxiv.org\/abs\/1703.08508 (2017)."},{"key":"31","doi-asserted-by":"publisher","unstructured":"Vilasini Venkatesh, Christopher Portmann, and L\u00eddia del Rio, ``Composable security in relativistic quantum cryptography'' New Journal of Physics 21, 043057 (2019).","DOI":"10.1088\/1367-2630\/ab0e3b"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Stephen Wiesner ``Conjugate Coding'' SIGACT News 15, 78\u201388 (1983).","DOI":"10.1145\/1008908.1008920"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-07-06-1047\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,7,6]],"date-time":"2023-07-06T13:29:30Z","timestamp":1688650170000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-07-06-1047\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,6]]},"references-count":33,"URL":"https:\/\/doi.org\/10.22331\/q-2023-07-06-1047","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2023,7,6]]},"article-number":"1047"}}