Can you sign a quantum state?

Gorjan Alagic; Tommaso Gagliardoni; Christian Majenz

doi:10.22331/q-2021-12-16-603

Can you sign a quantum state?

Gorjan Alagic^1,2, Tommaso Gagliardoni³, and Christian Majenz⁴

¹QuICS, University of Maryland, College Park, MD, USA
²National Institute of Standards and Technology, Gaithersburg, MD, USA
³Kudelski Security, Zurich, Switzerland
⁴Centrum Wiskunde & Informatica and QuSoft, Amsterdam, Netherlands

Published:	2021-12-16, volume 5, page 603
Eprint:	arXiv:1811.11858v5
Doi:	https://doi.org/10.22331/q-2021-12-16-603
Citation:	Quantum 5, 603 (2021).

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

Abstract

Cryptography with quantum states exhibits a number of surprising and counterintuitive features. In a 2002 work, Barnum et al. argue that these features imply that digital signatures for quantum states are impossible (Barnum et al., FOCS 2002). In this work, we ask: can all forms of signing quantum data, even in a possibly weak sense, be completely ruled out? We give two results which shed significant light on this basic question.
First, we prove an impossibility result for digital signatures for quantum data, which extends the result of Barnum et al. Specifically, we show that no nontrivial combination of correctness and security requirements can be fulfilled, beyond what is achievable simply by measuring the quantum message and then signing the outcome. In other words, $\textit{only classical signature schemes exist}$.
We then show a positive result: a quantum state can be signed with the same security guarantees as classically, provided that it is also encrypted with the public key of the intended recipient. Following classical nomenclature, we call this notion $\textit{quantum signcryption}$. Classically, signcryption is only interesting if it provides superior performance to encypt-then-sign. Quantumly, it is far more interesting: it is the only signing method available. We develop "as-strong-as-classical" security definitions for quantum signcryption and give secure constructions based on post-quantum public-key primitives. Along the way, we show that a natural hybrid method of combining classical and quantum schemes can be used to "upgrade" a secure classical scheme to the fully-quantum setting, in a wide range of cryptographic settings including signcryption, authenticated encryption, and CCA security.

► BibTeX data

@article{Alagic2021canyousignquantum,
  doi = {10.22331/q-2021-12-16-603},
  url = {https://doi.org/10.22331/q-2021-12-16-603},
  title = {Can you sign a quantum state?},
  author = {Alagic, Gorjan and Gagliardoni, Tommaso and Majenz, Christian},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {603},
  month = dec,
  year = {2021}
}

► References

[1] Dorit Aharonov, Michael Ben-Or, and Elad Eban. Interactive proofs for quantum computations. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings, pages 453–469, 2010. doi:10.1007/978-3-540-24587-2_1.
https://doi.org/10.1007/978-3-540-24587-2_1

[2] 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, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers, pages 47–71, 2016. doi:10.1007/978-3-319-49175-2_3.
https://doi.org/10.1007/978-3-319-49175-2_3

[3] Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Unforgeable quantum encryption. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, pages 489–519, Cham, 2018. Springer International Publishing. doi:10.1007/978-3-319-78372-7_16.
https://doi.org/10.1007/978-3-319-78372-7_16

[4] Gorjan Alagic and Christian Majenz. Quantum non-malleability and authentication. In Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part II, pages 310–341, 2017. doi:10.1007/978-3-319-63715-0_11.
https://doi.org/10.1007/978-3-319-63715-0_11

[5] Jee Hea An, Yevgeniy Dodis, and Tal Rabin. On the security of joint signature and encryption. In Lars R. Knudsen, editor, Advances in Cryptology — EUROCRYPT 2002, pages 83–107, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. doi:10.1007/3-540-46035-7_6.
https://doi.org/10.1007/3-540-46035-7_6

[6] Fabio Banfi, Ueli Maurer, Christopher Portmann, and Jiamin Zhu. Composable and finite computational security of quantum message transmission. In Dennis Hofheinz and Alon Rosen, editors, Theory of Cryptography, pages 282–311, Cham, 2019. Springer International Publishing. doi:10.1007/978-3-030-36030-6_12.
https://doi.org/10.1007/978-3-030-36030-6_12

[7] Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam D. Smith, and Alain Tapp. Authentication of quantum messages. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 449–458, 2002. doi:10.1109/SFCS.2002.1181969.
https://doi.org/10.1109/SFCS.2002.1181969

[8] Anne Broadbent and Stacey Jeffery. Quantum homomorphic encryption for circuits of low t-gate complexity. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, pages 609–629, 2015. doi:10.1007/978-3-662-48000-7_30.
https://doi.org/10.1007/978-3-662-48000-7_30

[9] Anne Broadbent and Evelyn Wainewright. Efficient simulation for quantum message authentication. In Information Theoretic Security - 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers, pages 72–91, 2016. doi:10.1007/978-3-319-49175-2_4.
https://doi.org/10.1007/978-3-319-49175-2_4

[10] Yfke Dulek and Florian Speelman. Quantum Ciphertext Authentication and Key Recycling with the Trap Code. In Stacey Jeffery, editor, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018), volume 111 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. doi:10.4230/LIPIcs.TQC.2018.1.
https://doi.org/10.4230/LIPIcs.TQC.2018.1

[11] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Secure two-party quantum evaluation of unitaries against specious adversaries. In Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings, pages 685–706, 2010. doi:10.1007/978-3-642-14623-7_37.
https://doi.org/10.1007/978-3-642-14623-7_37

[12] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Actively secure two-party evaluation of any quantum operation. In Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, pages 794–811, 2012. doi:10.1007/978-3-642-32009-5_46.
https://doi.org/10.1007/978-3-642-32009-5_46

[13] Daniel Gottesman and Isaac Chuang. Quantum digital signatures. arXiv preprint quant-ph/0105032, 2001. URL: https://arxiv.org/abs/2012.15493.
arXiv:quant-ph/0105032
https://arxiv.org/abs/2012.15493

[14] Patrick Hayden, Debbie W. Leung, and Dominic Mayers. The universal composable security of quantum message authentication with key recyling. arXiv quant-ph/1610.09434, 2016. URL: https://arxiv.org/abs/1610.09434.
arXiv:quant-ph/1610.09434
https://arxiv.org/abs/1610.09434

[15] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. CRC Press, 2014. doi:10.1201/b17668.
https://doi.org/10.1201/b17668

[16] Dennis Kretschmann, Dirk Schlingemann, and Reinhard F. Werner. The information-disturbance tradeoff and the continuity of stinespring's representation. IEEE Transactions on Information Theory, 54(4):1708–1717, 2008. doi:10.1109/TIT.2008.917696.
https://doi.org/10.1109/TIT.2008.917696

[17] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. doi:10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[18] Christopher Portmann. Quantum authentication with key recycling. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT 2017, pages 339–368, Cham, 2017. Springer International Publishing. URL: https://doi.org/10.1007/978-3-319-56617-7_12.
https://doi.org/10.1007/978-3-319-56617-7_12

[19] Tom Shrimpton. A characterization of authenticated-encryption as a form of chosen-ciphertext security. IACR Cryptology ePrint Archive, 2004:272, 2004. URL: http://eprint.iacr.org/2004/272.
http://eprint.iacr.org/2004/272

[20] Andreas J. Winter. Coding theorem and strong converse for quantum channels. IEEE Trans. Information Theory, 45(7):2481–2485, 1999. doi:10.1109/18.796385.
https://doi.org/10.1109/18.796385

[21] Yuliang Zheng. Digital signcryption or how to achieve cost(signature & encryption) $\ll$ cost(signature) + cost(encryption). In Burton S. Kaliski, editor, Advances in Cryptology — CRYPTO 1997, pages 165–179, Berlin, Heidelberg, 1997. Springer Berlin Heidelberg. doi:10.1007/BFb0052234.
https://doi.org/10.1007/BFb0052234

Cited by

[1] Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin, Lecture Notes in Computer Science 14654, 226 (2024) ISBN:978-3-031-58736-8.

[2] Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa, Lecture Notes in Computer Science 14926, 93 (2024) ISBN:978-3-031-68393-0.

[3] Yi-Kai Liu and Dustin Moody, "Post-quantum cryptography and the quantum future of cybersecurity", Physical Review Applied 21 4, 040501 (2024).

[4] Davide Li Calsi, Paul Kohl, JinHyeock Choi, and Janis Nötzel, "The impact of message losses and retransmissions on quantum cryptographic protocols", Computer Networks 253, 110735 (2024).

[5] Giulio Malavolta and Michael Walter, Lecture Notes in Computer Science 14926, 126 (2024) ISBN:978-3-031-68393-0.

[6] Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song, "Quantum-secure message authentication via blind-unforgeability", arXiv:1803.03761, (2018).

[7] Siyu Xiong, Bangying Tang, Hui Han, Jinquan Huang, Mingqiang Bai, Fangzhao Li, Wanrong Yu Zhiwen Mo, and Bo Liu, "Efficient Arbitrated Quantum Digital Signature with Multi-Receiver Verification", arXiv:2406.07824, (2024).

[8] Jiahui Liu, Qipeng Liu, and Luowen Qian, "Beating Classical Impossibility of Position Verification", arXiv:2109.07517, (2021).

[9] Christian Majenz, Christian Schaffner, and Jeroen van Wier, "Non-malleability for quantum public-key encryption", arXiv:1905.05490, (2019).

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

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.