Composably Secure Device-independent Encryption With Certified Deletion

Republished By Plato

Followers: 0

¹Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
²Institute for Theoretical Physics, ETH Zürich, Switzerland.
³Institute for Quantum Computing and Department of Physics and Astronomy, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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.

Composably secure device-independent encryption with certified deletion PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Featured image: Construction of simulator to prove composable security

► BibTeX data

@article{Kundu2023composablysecure, doi = {10.22331/q-2023-07-06-1047}, url = {https://doi.org/10.22331/q-2023-07-06-1047}, title = {Composably secure device-independent encryption with certified deletion}, author = {Kundu, Srijita and Tan, Ernest Y.-Z.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1047}, month = jul, year = {2023}<br /> }

► References

[1] Nati Aharon, André 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).
https://doi.org/10.1007/978-3-642-54429-3_1

[2] Rotem Arnon-Friedman, Frédéric Dupuis, Omar Fawzi, Renato Renner, and Thomas Vidick, “Practical device-independent quantum cryptography via entropy accumulation” Nature Communications 9, 459 (2018).
https://doi.org/10.1038/s41467-017-02307-4
https://www.nature.com/articles/s41467-017-02307-4

[3] 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).
https://doi.org/10.1088/1367-2630/18/2/025014

[4] 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).
https://doi.org/10.1016/j.tcs.2011.08.039

[5] Jonathan Barrett, Roger Colbeck, and Adrian Kent, “Memory Attacks on Device-Independent Quantum Cryptography” Physical Review Letters 110, 010503 (2013).
https://doi.org/10.1103/PhysRevLett.110.010503

[6] Anne Broadbentand Rabib Islam “Quantum Encryption with Certified Deletion” Theory of Cryptography 92–122 (2020).
https://doi.org/10.1007/978-3-030-64381-2_4

[7] Michael Ben-Or, Michał Horodecki, Debbie W. Leung, Dominic Mayers, and Jonathan Oppenheim, “The Universal Composable Security of Quantum Key Distribution” Theory of Cryptography 386–406 (2005).
https://doi.org/10.1007/978-3-540-30576-7_21

[8] Mohammad Bavarian, Thomas Vidick, and Henry Yuen, “Anchoring Games for Parallel Repetition” https://arxiv.org/abs/1509.07466 (2015).
https://arxiv.org/abs/1509.07466

[9] 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–316 (2017).
https://doi.org/10.1145/3055399.3055433

[10] J. Lawrence Carterand Mark N. Wegman “Universal classes of hash functions” Journal of Computer and System Sciences 18, 143–154 (1979).
https://doi.org/10.1016/0022-0000(79)90044-8

[11] Honghao Fuand Carl A. Miller “Local randomness: Examples and application” Physical Review A 97, 032324 (2018).
https://doi.org/10.1103/PhysRevA.97.032324

[12] 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).
https://arxiv.org/abs/2201.13445

[13] Thomas Holenstein “Parallel Repetition: Simplifications and the No-Signaling Case” Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing 411–419 (2007).
https://doi.org/10.1145/1250790.1250852

[14] 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–27:28 (2021).
https://doi.org/10.4230/LIPIcs.CCC.2021.27
https://drops.dagstuhl.de/opus/volltexte/2021/14301

[15] Rahul Jain, Carl A. Miller, and Yaoyun Shi, “Parallel Device-Independent Quantum Key Distribution” IEEE Transactions on Information Theory 66, 5567–5584 (2020).
https://doi.org/10.1109/TIT.2020.2986740

[16] Rahul Jain, Attila Pereszlényi, 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–216 (2014).
https://doi.org/10.1109/CCC.2014.29

[17] 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–456 (2008).
https://doi.org/10.1109/FOCS.2008.8

[18] Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan, “A device-independent protocol for XOR oblivious transfer” Quantum 6, 725 (2022).
https://doi.org/10.22331/q-2022-05-30-725

[19] Srijita Kunduand Ernest Y.-Z. Tan “Device-independent uncloneable encryption” https://arxiv.org/abs/2210.01058 (2022).
https://arxiv.org/abs/2210.01058

[20] Norbert Lütkenhaus, Ashutosh Marwah, and Dave Touchette, “Erasable Bit Commitment From Temporary Quantum Trust” IEEE Journal on Selected Areas in Information Theory 1, 536–554 (2020).
https://doi.org/10.1109/JSAIT.2020.3017054

[21] Ueli Maurerand Renato Renner “Abstract Cryptography” The Second Symposium on Innovations in Computer Science, ICS 2011 1–21 (2011).
https://crypto.ethz.ch/publications/MauRen11.html

[22] Stefano Pironio, Antonio Acín, 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).
https://doi.org/10.1088/1367-2630/11/4/045021

[23] Christopher Portmannand Renato Renner “Cryptographic security of quantum key distribution” https://arxiv.org/abs/1409.3525 (2014).
https://arxiv.org/abs/1409.3525

[24] Anup Rao “Parallel Repetition in Projection Games and a Concentration Bound” Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing 1–10 (2008).
https://doi.org/10.1145/1374376.1374378

[25] Ran Raz “A Parallel Repetition Theorem” Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing 447–456 (1995).
https://doi.org/10.1145/225058.225181

[26] Renato Renner “Security of Quantum Key Distribution” thesis (2005).
https://doi.org/10.3929/ethz-a-005115027

[27] Jonathan Silman, André Chailloux, Nati Aharon, Iordanis Kerenidis, Stefano Pironio, and Serge Massar, “Fully distrustful quantum bit commitment and coin flipping” Physical Review Letters 106, 220501 (2011).
https://doi.org/10.1103/PhysRevLett.106.220501

[28] Marco Tomamicheland Anthony Leverrier “A largely self-contained and complete security proof for quantum key distribution” Quantum 1, 14 (2017).
https://doi.org/10.22331/q-2017-07-14-14

[29] Dominique Unruh “Revocable Quantum Timed-Release Encryption” Advances in Cryptology – EUROCRYPT 2014 129–146 (2014).
https://doi.org/10.1007/978-3-642-55220-5_8

[30] Bart van der Vecht, Xavier Coiteaux-Roy, and Boris Škorić, “Can’t Touch This: unconditional tamper evidence from short keys” https://arxiv.org/abs/2006.02476 (2020).
https://arxiv.org/abs/2006.02476

[31] Thomas Vidick “Parallel DIQKD from parallel repetition” https://arxiv.org/abs/1703.08508 (2017).
https://arxiv.org/abs/1703.08508

[32] Vilasini Venkatesh, Christopher Portmann, and Lídia del Rio, “Composable security in relativistic quantum cryptography” New Journal of Physics 21, 043057 (2019).
https://doi.org/10.1088/1367-2630/ab0e3b

[33] Stephen Wiesner “Conjugate Coding” SIGACT News 15, 78–88 (1983).
https://doi.org/10.1145/1008908.1008920

Cited by

[1] Tony Metger, Omar Fawzi, David Sutter, and Renato Renner, “Generalised entropy accumulation”, arXiv:2203.04989, (2022).

[2] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa, “Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication”, arXiv:2105.05393, (2021).

[3] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa, “Certified Everlasting Functional Encryption”, arXiv:2207.13878, (2022).

[4] Rahul Jain and Srijita Kundu, “A direct product theorem for quantum communication complexity with applications to device-independent cryptography”, arXiv:2106.04299, (2021).

The above citations are from SAO/NASA ADS (last updated successfully 2023-07-06 13:26:29). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-07-06 13:26:27: Could not fetch cited-by data for 10.22331/q-2023-07-06-1047 from Crossref. This is normal if the DOI was registered recently.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.