Can you sign a quantum state?

Gorjan Alagic1,2, Tommaso Gagliardoni3, and Christian Majenz4

1QuICS, University of Maryland, College Park, MD, USA
2National Institute of Standards and Technology, Gaithersburg, MD, USA
3Kudelski Security, Zurich, Switzerland
4Centrum Wiskunde & Informatica and QuSoft, Amsterdam, Netherlands

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

► 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] Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song, "Quantum-secure message authentication via blind-unforgeability", arXiv:1803.03761.

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

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

The above citations are from SAO/NASA ADS (last updated successfully 2022-01-23 09:19:42). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2022-01-23 09:19:40).