quantum-computing

How to Sign Quantum Messages

Quantum Science and Technology (arXiv overlay)

19 min read

0 likes

⚡ Quantum Brief

Researchers Mohammed Barhoush and Louis Salvail have broken new ground by demonstrating quantum message signing is possible, overturning long-held assumptions about its impossibility. Their work introduces the first publicly verifiable quantum signatures. The team pioneered time-dependent (TD) signatures, where signing and verification rely on temporal parameters. This approach uses post-quantum secure one-way functions and time-lock puzzles to ensure authenticity. A second method eliminates time-lock puzzles by employing dynamic verification keys that evolve over time, maintaining security while simplifying implementation. In bounded quantum storage models, the researchers achieved information-theoretic security, proving quantum messages can be signed even when adversaries have limited quantum memory capacity. The work extends to practical applications, including tamper-resistant quantum public key encryption and a novel time-dependent quantum money scheme, both built solely on post-quantum secure one-way functions.

Summarize this article with:

AbstractSigning quantum messages has long been considered impossible even under computational assumptions. In this work, we challenge this notion and provide three innovative approaches to sign quantum messages that are the first to ensure authenticity with public verifiability. Our contributions can be summarized as follows: 1) We introduce the concept of time-dependent (TD) signatures, where the signature of a quantum message depends on the time of signing and the verification process depends on the time of the signature reception. We construct this primitive assuming the existence of post-quantum secure one-way functions (pq-OWFs) and time-lock puzzles (TLPs). 2) By utilizing verification keys that evolve over time, we eliminate the need for TLPs in our construction. This leads to TD signatures from pq-OWFs with dynamic verification keys. 3) We then consider the bounded quantum storage model, where adversaries are limited with respect to their quantum memories. We show that quantum messages can be signed with information-theoretic security in this model. Moreover, we leverage TD signatures to achieve the following objectives, relying solely on pq-OWFs: (a) We design a public key encryption scheme featuring authenticated quantum public keys that resist adversarial tampering. (b) We present a novel TD public-key quantum money scheme.► BibTeX data@article{Barhoush2026howtosignquantum, doi = {10.22331/q-2026-01-22-1980}, url = {https://doi.org/10.22331/q-2026-01-22-1980}, title = {How to {S}ign {Q}uantum {M}essages}, author = {Barhoush, Mohammed and Salvail, Louis}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1980}, month = jan, year = {2026} }► References [1] Scott Aaronson, Yosi Atia, and Leonard Susskind, ``On the hardness of detecting macroscopic superpositions'' arXiv preprint arXiv:2009.07450 (2020). https://doi.org/10.48550/arXiv.2009.07450 [2] Scott Aaronsonand Paul Christiano ``Quantum money from hidden subspaces'' Proceedings of the forty-fourth annual ACM symposium on Theory of computing 41–60 (2012). https://doi.org/10.1145/2213977.2213983 [3] Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, and Michael St. Jules, ``Computational security of quantum encryption'' Information Theoretic Security: 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers 9 47–71 (2016). https://doi.org/10.1007/978-3-319-49175-2_3 [4] Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz, ``Can you sign a quantum state?'' Quantum 5, 603 (2021). https://doi.org/10.22331/q-2021-12-16-603 [5] Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz, ``Unforgeable quantum encryption'' Advances in Cryptology–EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part III 489–519 (2018). https://doi.org/10.1007/978-3-319-78372-7_16 [6] Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba, ``On quantum chosen-ciphertext attacks and learning with errors'' Cryptography 4, 10 (2020). https://doi.org/10.3390/cryptography4010010 [7] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen, ``Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications'' Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I 237–265 (2022). https://doi.org/10.1007/978-3-031-22318-1_9 [8] Prabhanjan Ananth, Zihan Hu, and Henry Yuen, ``On the (Im) plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions'' arXiv preprint arXiv:2301.09236 (2023). https://doi.org/10.48550/arXiv.2301.09236 [9] Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai, ``Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification'' Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 284–332 (2019). https://doi.org/10.1007/978-3-030-26954-8_10 [10] Prabhanjan Ananth, Luowen Qian, and Henry Yuen, ``Cryptography from pseudorandom quantum states'' Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I 208–236 (2022). https://doi.org/10.1007/978-3-031-15802-5_8 [11] Mohammed Barhoushand Louis Salvail ``Powerful Primitives in the Bounded Quantum Storage Model'' arXiv preprint arXiv:2302.05724 (2023). https://doi.org/10.48550/arXiv.2302.05724 [12] Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp, ``Authentication of quantum messages'' The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 449–458 (2002). https://doi.org/10.1109/SFCS.2002.1181969 [13] Mihir Bellareand Phillip Rogaway ``Random oracles are practical: A paradigm for designing efficient protocols'' Proceedings of the 1st ACM Conference on Computer and Communications Security 62–73 (1993). https://doi.org/10.1145/168588.168596 [14] Charles H.

Bennettand Gilles Brassard ``Quantum cryptography: Public key distribution and coin tossing'' Theoretical Computer Science 560, 7–11 (2014) Original work published 1984. https://doi.org/10.1016/j.tcs.2014.05.025 [15] Andriyan Bilyk, Javad Doliskani, and Zhiyong Gong, ``Cryptanalysis of three quantum money schemes'' Quantum Information Processing 22, 177 (2023). https://doi.org/10.1007/s11128-023-03919-0 [16] Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters, ``Time-lock puzzles from randomized encodings'' Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science 345–356 (2016). https://doi.org/10.1145/2840728.2840745 [17] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry, ``Random oracles in a quantum world'' Advances in Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17 41–69 (2011). https://doi.org/10.1007/978-3-642-25385-0_3 [18] Dan Bonehand Mark Zhandry ``Secure signatures and chosen ciphertext security in a quantum computing world'' Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II 361–379 (2013). https://doi.org/10.1007/978-3-642-40084-1_21 [19] Tore Vincent Carstens, Ehsan Ebrahimi, Gelo Noel Tabia, and Dominique Unruh, ``Relationships between quantum IND-CPA notions'' Theory of Cryptography: 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part I 240–272 (2021). https://doi.org/10.1007/978-3-030-90459-3_9 [20] Céline Chevalier, Ehsan Ebrahimi, and Quoc-Huy Vu, ``On security notions for encryption in a quantum world'' Progress in Cryptology–INDOCRYPT 2022: 23rd International Conference on Cryptology in India, Kolkata, India, December 11–14, 2022, Proceedings 592–613 (2023). https://doi.org/10.1007/978-3-031-22912-1_26 [21] Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao, ``On the compressed-oracle technique, and post-quantum security of proofs of sequential work'' Annual International Conference on the Theory and Applications of Cryptographic Techniques 598–629 (2021). https://doi.org/10.1007/978-3-030-77886-6_21 [22] Andrea Coladangelo ``Quantum trapdoor functions from classical one-way functions'' arXiv preprint arXiv:2302.12821 (2023). https://doi.org/10.48550/arXiv.2302.12821 [23] Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner, ``Cryptography in the Bounded-Quantum-Storage Model'' SIAM Journal on Computing 37, 1865–1890 (2008). https://doi.org/10.1137/060651343 [24] Yevgeniy Dodis, Willy Quach, and Daniel Wichs, ``Authentication in the Bounded Storage Model'' Annual International Conference on the Theory and Applications of Cryptographic Techniques 737–766 (2022). https://doi.org/10.1007/978-3-031-07082-2_26 [25] Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor, ``Quantum money from knots'' Proceedings of the 3rd Innovations in Theoretical Computer Science Conference 276–289 (2012). https://doi.org/10.1145/2090236.2090260 [26] Christopher A Fuchsand Jeroen Van De Graaf ``Cryptographic distinguishability measures for quantum-mechanical states'' IEEE Transactions on Information Theory 45, 1216–1227 (1999). https://doi.org/10.1109/18.761271 [27] Romain Gayand Rafael Pass ``Indistinguishability obfuscation from circular security'' Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 736–749 (2021). https://doi.org/10.1145/3406325.3451070 [28] Daniel Gottesmanand Isaac Chuang ``Quantum digital signatures'' arXiv preprint quant-ph/0105032 (2001). https://doi.org/10.48550/arXiv.quant-ph/0105032 [29] Alex B Grilo, Or Sattath, and Quoc-Huy Vu, ``Encryption with Quantum Public Keys'' arXiv preprint arXiv:2303.05368 (2023). https://doi.org/10.48550/arXiv.2303.05368 [30] Sam Hopkins, Aayush Jain, and Huijia Lin, ``Counterexamples to new circular security assumptions underlying iO'' Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part II 41 673–700 (2021). https://doi.org/10.1007/978-3-030-84245-1_23 [31] Russell Impagliazzoand Steven Rudich ``Limits on the provable consequences of one-way permutations'' Proceedings of the twenty-first annual ACM symposium on Theory of computing 44–61 (1989). https://doi.org/10.1145/73007.73012 [32] Aayush Jain, Huijia Lin, and Amit Sahai, ``Indistinguishability obfuscation from LPN over $F_p$, DLIN, and PRGs in $NC_0$'' Advances in Cryptology–EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30–June 3, 2022, Proceedings, Part I 670–699 (2022). https://doi.org/10.1007/978-3-031-06944-4_23 [33] Aayush Jain, Huijia Lin, and Amit Sahai, ``Indistinguishability obfuscation from well-founded assumptions'' Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 60–73 (2021). https://doi.org/10.1145/3406325.3451093 [34] Zhengfeng Ji, Yi-Kai Liu, and Fang Song, ``Pseudorandom Quantum States'' Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III 38 126–152 (2018). https://doi.org/10.1007/978-3-319-96878-0_5 [35] Daniel M Kane, Shahed Sharif, and Alice Silverberg, ``Quantum money from quaternion algebras'' arXiv preprint arXiv:2109.12643 (2021). https://doi.org/10.48550/arXiv.2109.12643 [36] Andrey Boris Khesin, Jonathan Z Lu, and Peter W Shor, ``Publicly verifiable quantum money from random lattices'' arXiv preprint arXiv:2207.13135 (2022). https://doi.org/10.48550/arXiv.2207.13135 [37] Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa, ``Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions'' (2023). https://doi.org/10.48550/arXiv.2304.01800 [38] Robert Konig, Renato Renner, and Christian Schaffner, ``The operational meaning of min-and max-entropy'' IEEE Transactions on Information theory 55, 4337–4347 (2009). https://doi.org/10.1109/TIT.2009.2025545 [39] William Kretschmer ``Quantum Pseudorandomness and Classical Complexity'' 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (2021). https://doi.org/10.4230/LIPIcs.TQC.2021.2 [40] Qipeng Liu ``Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More'' 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) (2023). https://doi.org/10.4230/LIPIcs.ITCS.2023.82 [41] Tomoyuki Morimae, Alexander Poremba, and Takashi Yamakawa, ``Revocable quantum digital signatures'' arXiv preprint arXiv:2312.13561 (2023). https://doi.org/10.48550/arXiv.2312.13561 [42] Tomoyuki Morimaeand Takashi Yamakawa ``Quantum commitments and signatures without one-way functions'' Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I 269–295 (2022). https://doi.org/10.1007/978-3-031-15802-5_10 [43] Roy Radianand Or Sattath ``Semi-quantum money'' Proceedings of the 1st ACM Conference on Advances in Financial Technologies 132–146 (2019). https://doi.org/10.1145/3318041.3355462 [44] Renato Rennerand Robert König ``Universally Composable Privacy Amplification Against Quantum Adversaries'' (2005). https://doi.org/10.1007/978-3-540-30576-7_22 [45] Ronald L Rivest, Adi Shamir, and David A Wagner, ``Time-lock puzzles and timed-release crypto'' (1996). [46] Bhaskar Robertsand Mark Zhandry ``Franchised quantum money'' Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part I 27 549–574 (2021). https://doi.org/10.1007/978-3-030-92062-3_19 [47] John Rompel ``One-way functions are necessary and sufficient for secure signatures'' Proceedings of the twenty-second annual ACM symposium on Theory of computing 387–394 (1990). https://doi.org/10.1145/100216.100269 [48] Omri Shmueli ``Public-Key Quantum Money With a Classical Bank'' Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 790–803 (2022). https://doi.org/10.1145/3519935.3519952 [49] Marco Tomamichel, Serge Fehr, Jedrzej Kaniewski, and Stephanie Wehner, ``A monogamy-of-entanglement game with applications to device-independent quantum cryptography'' New Journal of Physics 15, 103002 (2013). https://doi.org/10.1088/1367-2630/15/10/103002 [50] Hoeteck Weeand Daniel Wichs ``Candidate obfuscation via oblivious LWE sampling'' Advances in Cryptology–EUROCRYPT 2021: 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17–21, 2021, Proceedings, Part III 127–156 (2021). https://doi.org/10.1007/978-3-030-77883-5_5 [51] Stephen Wiesner ``Conjugate coding'' ACM Sigact News 15, 78–88 (1983). https://doi.org/10.1145/1008908.1008920 [52] Mark Zhandry ``How to construct quantum random functions'' 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science 679–687 (2012). https://doi.org/10.1109/FOCS.2012.37 [53] Mark Zhandry ``Quantum lightning never strikes the same state twice. or: quantum money from cryptographic assumptions'' Journal of Cryptology 34, 1–56 (2021). https://doi.org/10.1007/s00145-020-09372-xCited byCould not fetch Crossref cited-by data during last attempt 2026-01-22 09:12:49: cURL error 28: Operation timed out after 10001 milliseconds with 0 bytes received Could not fetch ADS cited-by data during last attempt 2026-01-22 09:12:59: No response from ADS or unable to decode the received json data when getting the list of citing works.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. AbstractSigning quantum messages has long been considered impossible even under computational assumptions. In this work, we challenge this notion and provide three innovative approaches to sign quantum messages that are the first to ensure authenticity with public verifiability. Our contributions can be summarized as follows: 1) We introduce the concept of time-dependent (TD) signatures, where the signature of a quantum message depends on the time of signing and the verification process depends on the time of the signature reception. We construct this primitive assuming the existence of post-quantum secure one-way functions (pq-OWFs) and time-lock puzzles (TLPs). 2) By utilizing verification keys that evolve over time, we eliminate the need for TLPs in our construction. This leads to TD signatures from pq-OWFs with dynamic verification keys. 3) We then consider the bounded quantum storage model, where adversaries are limited with respect to their quantum memories. We show that quantum messages can be signed with information-theoretic security in this model. Moreover, we leverage TD signatures to achieve the following objectives, relying solely on pq-OWFs: (a) We design a public key encryption scheme featuring authenticated quantum public keys that resist adversarial tampering. (b) We present a novel TD public-key quantum money scheme.► BibTeX data@article{Barhoush2026howtosignquantum, doi = {10.22331/q-2026-01-22-1980}, url = {https://doi.org/10.22331/q-2026-01-22-1980}, title = {How to {S}ign {Q}uantum {M}essages}, author = {Barhoush, Mohammed and Salvail, Louis}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1980}, month = jan, year = {2026} }► References [1] Scott Aaronson, Yosi Atia, and Leonard Susskind, ``On the hardness of detecting macroscopic superpositions'' arXiv preprint arXiv:2009.07450 (2020). https://doi.org/10.48550/arXiv.2009.07450 [2] Scott Aaronsonand Paul Christiano ``Quantum money from hidden subspaces'' Proceedings of the forty-fourth annual ACM symposium on Theory of computing 41–60 (2012). https://doi.org/10.1145/2213977.2213983 [3] Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, and Michael St. Jules, ``Computational security of quantum encryption'' Information Theoretic Security: 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers 9 47–71 (2016). https://doi.org/10.1007/978-3-319-49175-2_3 [4] Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz, ``Can you sign a quantum state?'' Quantum 5, 603 (2021). https://doi.org/10.22331/q-2021-12-16-603 [5] Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz, ``Unforgeable quantum encryption'' Advances in Cryptology–EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29-May 3, 2018 Proceedings, Part III 489–519 (2018). https://doi.org/10.1007/978-3-319-78372-7_16 [6] Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba, ``On quantum chosen-ciphertext attacks and learning with errors'' Cryptography 4, 10 (2020). https://doi.org/10.3390/cryptography4010010 [7] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen, ``Pseudorandom (Function-Like) Quantum State Generators: New Definitions and Applications'' Theory of Cryptography: 20th International Conference, TCC 2022, Chicago, IL, USA, November 7–10, 2022, Proceedings, Part I 237–265 (2022). https://doi.org/10.1007/978-3-031-22318-1_9 [8] Prabhanjan Ananth, Zihan Hu, and Henry Yuen, ``On the (Im) plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions'' arXiv preprint arXiv:2301.09236 (2023). https://doi.org/10.48550/arXiv.2301.09236 [9] Prabhanjan Ananth, Aayush Jain, Huijia Lin, Christian Matt, and Amit Sahai, ``Indistinguishability obfuscation without multilinear maps: new paradigms via low degree weak pseudorandomness and security amplification'' Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 284–332 (2019). https://doi.org/10.1007/978-3-030-26954-8_10 [10] Prabhanjan Ananth, Luowen Qian, and Henry Yuen, ``Cryptography from pseudorandom quantum states'' Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part I 208–236 (2022). https://doi.org/10.1007/978-3-031-15802-5_8 [11] Mohammed Barhoushand Louis Salvail ``Powerful Primitives in the Bounded Quantum Storage Model'' arXiv preprint arXiv:2302.05724 (2023). https://doi.org/10.48550/arXiv.2302.05724 [12] Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp, ``Authentication of quantum messages'' The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 449–458 (2002). https://doi.org/10.1109/SFCS.2002.1181969 [13] Mihir Bellareand Phillip Rogaway ``Random oracles are practical: A paradigm for designing efficient protocols'' Proceedings of the 1st ACM Conference on Computer and Communications Security 62–73 (1993). https://doi.org/10.1145/168588.168596 [14] Charles H.

Read Original

Source Information

Source: Quantum Science and Technology (arXiv overlay)

Website: https://quantum-journal.org/feed