Composably secure device-independent encryption with certified deletion

Srijita Kundu1 and Ernest Y.-Z. Tan2,3

1Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.
2Institute for Theoretical Physics, ETH Zürich, Switzerland.
3Institute 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.


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.

► BibTeX data

► 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).

[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).

[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).

[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).

[5] Jonathan Barrett, Roger Colbeck, and Adrian Kent, ``Memory Attacks on Device-Independent Quantum Cryptography'' Physical Review Letters 110, 010503 (2013).

[6] Anne Broadbentand Rabib Islam ``Quantum Encryption with Certified Deletion'' Theory of Cryptography 92–122 (2020).

[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).

[8] Mohammad Bavarian, Thomas Vidick, and Henry Yuen, ``Anchoring Games for Parallel Repetition'' https:/​/​​abs/​1509.07466 (2015).

[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).

[10] J. Lawrence Carterand Mark N. Wegman ``Universal classes of hash functions'' Journal of Computer and System Sciences 18, 143–154 (1979).

[11] Honghao Fuand Carl A. Miller ``Local randomness: Examples and application'' Physical Review A 97, 032324 (2018).

[12] Alexandru Gheorghiu, Tony Metger, and Alexander Poremba, ``Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more'' https:/​/​​abs/​2201.13445 (2022).

[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).

[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).

[15] Rahul Jain, Carl A. Miller, and Yaoyun Shi, ``Parallel Device-Independent Quantum Key Distribution'' IEEE Transactions on Information Theory 66, 5567–5584 (2020).

[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).

[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).

[18] Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan, ``A device-independent protocol for XOR oblivious transfer'' Quantum 6, 725 (2022).

[19] Srijita Kunduand Ernest Y.-Z. Tan ``Device-independent uncloneable encryption'' https:/​/​​abs/​2210.01058 (2022).

[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).

[21] Ueli Maurerand Renato Renner ``Abstract Cryptography'' The Second Symposium on Innovations in Computer Science, ICS 2011 1–21 (2011).

[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).

[23] Christopher Portmannand Renato Renner ``Cryptographic security of quantum key distribution'' https:/​/​​abs/​1409.3525 (2014).

[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).

[25] Ran Raz ``A Parallel Repetition Theorem'' Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing 447–456 (1995).

[26] Renato Renner ``Security of Quantum Key Distribution'' thesis (2005).

[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).

[28] Marco Tomamicheland Anthony Leverrier ``A largely self-contained and complete security proof for quantum key distribution'' Quantum 1, 14 (2017).

[29] Dominique Unruh ``Revocable Quantum Timed-Release Encryption'' Advances in Cryptology – EUROCRYPT 2014 129–146 (2014).

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

[31] Thomas Vidick ``Parallel DIQKD from parallel repetition'' https:/​/​​abs/​1703.08508 (2017).

[32] Vilasini Venkatesh, Christopher Portmann, and Lídia del Rio, ``Composable security in relativistic quantum cryptography'' New Journal of Physics 21, 043057 (2019).

[33] Stephen Wiesner ``Conjugate Coding'' SIGACT News 15, 78–88 (1983).

Cited by

[1] Tony Metger, Omar Fawzi, David Sutter, and Renato Renner, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 844 (2022) ISBN:978-1-6654-5519-0.

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

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

[4] 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).

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

[6] Ernest Y. -Z. Tan, "Prospects for device-independent quantum key distribution", arXiv:2111.11769, (2021).

[7] Taiga Hiroka, Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Tapas Pal, and Takashi Yamakawa, "Certified Everlasting Secure Collusion-Resistant Functional Encryption, and More", arXiv:2302.10354, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 13:37:58) and SAO/NASA ADS (last updated successfully 2024-05-21 13:37:59). The list may be incomplete as not all publishers provide suitable and complete citation data.