Document Open Access Logo

Uncloneable Quantum Encryption via Oracles

Authors Anne Broadbent , Sébastien Lord

PDF
Thumbnail PDF

File

LIPIcs.TQC.2020.4.pdf
  • Filesize: 0.6 MB
  • 22 pages

Document Identifiers

Author Details

Anne Broadbent
  • Department of Mathematics and Statistics, University of Ottawa, Canada
Sébastien Lord
  • Department of Mathematics and Statistics, University of Ottawa, Canada

Funding

This material is based upon work supported by the U.S. Air Force Office of Scientific Research under award number FA9550-17-1-0083, Canada’s NSERC, an Ontario ERA, and the University of Ottawa’s Research Chairs program.

Cite As Get BibTex

Anne Broadbent and Sébastien Lord. Uncloneable Quantum Encryption via Oracles. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.TQC.2020.4

Abstract

Quantum information is well known to achieve cryptographic feats that are unattainable using classical information alone. Here, we add to this repertoire by introducing a new cryptographic functionality called uncloneable encryption. This functionality allows the encryption of a classical message such that two collaborating but isolated adversaries are prevented from simultaneously recovering the message, even when the encryption key is revealed. Clearly, such functionality is unattainable using classical information alone.
We formally define uncloneable encryption, and show how to achieve it using Wiesner’s conjugate coding, combined with a quantum-secure pseudorandom function (qPRF). Modelling the qPRF as an oracle, we show security by adapting techniques from the quantum one-way-to-hiding lemma, as well as using bounds from quantum monogamy-of-entanglement games.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Cryptographic primitives
  • Security and privacy → Symmetric cryptography and hash functions
Keywords
  • Quantum Cryptography
  • Symmetric Key
  • Monogamy-of-Entanglement

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Scott Aaronson. Quantum copy-protection and quantum money. In 24th Annual Conference on Computational Complexity - CCC 2009, pages 229-242, 2009. URL: https://doi.org/10.1109/CCC.2009.42.
  2. Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In 44th Annual ACM Symposium on Theory of Computing - STOC 2012, pages 41-60, 2012. URL: https://doi.org/10.1145/2213977.2213983.
  3. Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In 30th Annual ACM Symposium on Theory of Computing - STOC 1998, pages 20-30, 1998. URL: https://doi.org/10.1145/276698.276708.
  4. Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, and Michael St. Jules. Computational security of quantum encryption. In Information Theoretic Security: 9th International Conference - ICITS 2016, pages 47-71, 2016. URL: https://doi.org/10.1007/978-3-319-49175-2_3.
  5. Elaine Barker. Recommendation for key management part 1: General (revision 4). Technical Report SP 800-57, National Institute of Standards and Technology, 2016. URL: https://doi.org/10.6028/NIST.SP.800-57pt1r4.
  6. Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In International Conference on Computers, Systems and Signal Processing, pages 175-179, 1984. URL: http://arxiv.org/abs/2003.06557.
  7. Charles H. Bennett, Gilles Brassard, and Seth Breidbart. Quantum cryptography II: How to re-use a one-time pad safely even if P=NP. Natural Computing, 13(4):453-458, 2014. URL: https://doi.org/10.1007/s11047-014-9453-6.
  8. Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Advances in Cryptology - ASIACRYPT 2011, pages 41-69, 2011. URL: https://doi.org/10.1007/978-3-642-25385-0_3.
  9. Anne Broadbent and Christian Schaffner. Quantum cryptography beyond quantum key distribution. Designs, Codes and Cryptography, 78(1):351-382, 2016. URL: https://doi.org/10.1007/s10623-015-0157-4.
  10. Ivan Damgård, Thomas Brochmann Pedersen, and Louis Salvail. A quantum cipher with near optimal key-recycling. In Advances in Cryptology - CRYPTO 2005, pages 494-510, 2005. URL: https://doi.org/10.1007/11535218_30.
  11. D. Dieks. Communication by EPR devices. Physics Letters A, 92(6):271-272, 1982. URL: https://doi.org/10.1016/0375-9601(82)90084-6.
  12. A. Einstein, B. Podolsky, and N. Rosen. Can quantum-mechanical description of physical reality be considered complete? Physical Review Letters, 47(10):777-780, 1935. URL: https://doi.org/10.1103/physrev.47.777.
  13. Serge Fehr and Louis Salvail. Quantum authentication and encryption with key recycling. In Advances in Cryptology - EUROCRYPT 2017, volume 3, pages 311-338, 2017. URL: https://doi.org/10.1007/978-3-319-56617-7_11.
  14. Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270-299, 1984. URL: https://doi.org/10.1016/0022-0000(84)90070-9.
  15. Daniel Gottesman. Uncloneable encryption. Quantum Information & Computation, 3(6):581-602, 2003. URL: http://arxiv.org/abs/quant-ph/0210062.
  16. Sébastien Lord. Uncloneable quantum encryption via random oracles. Master’s thesis, University of Ottawa, 2019. URL: https://doi.org/10.20381/ruor-23107.
  17. Michael A. Nielsen and Issac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  18. James L. Park. The concept of transition in quantum mechanics. Foundations of Physics, 1(1):23-33, 1970. URL: https://doi.org/10.1007/BF00708652.
  19. Peter W. Shor and John Preskill. Simple proof of security of the BB84 quantum key distribution protocol. Physical Review Letters, 85(2):441-444, 2000. URL: https://doi.org/10.1103/physrevlett.85.441.
  20. Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10):103002, 2013. URL: https://doi.org/10.1088/1367-2630/15/10/103002.
  21. Dominique Unruh. Everlasting multi-party computation. In Advances in Cryptology - CRYPTO 2013, volume 2, pages 380-397, 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_22.
  22. Dominique Unruh. Revocable quantum timed-release encryption. Journal of the ACM, 62(6):49, 2015. URL: https://doi.org/10.1145/2817206.
  23. John Watrous. Quantum computational complexity. In Encyclopedia of complexity and systems science, pages 7174-7201. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-27737-5_428-3.
  24. John Watrous. The Theory of Quantum Information. Cambridge University Press, 1superscriptst edition, 2018. Google Scholar
  25. Stephen Wiesner. Conjugate coding. ACM SIGACT News, 15(1):78-88, 1983. URL: https://doi.org/10.1145/1008908.1008920.
  26. W. K. Wootters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299:802-803, 1982. URL: https://doi.org/10.1038/299802a0.
  27. Mark Zhandry. How to construct quantum random functions. In 53rd Annual Symposium on Foundations of Computer Science - FOCS 2012, pages 679-687, 2012. URL: https://doi.org/10.1109/FOCS.2012.37.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact