Unconditional Quantum Cryptography with a Bounded Number of Keys

Vipul Goyal; Giulio Malavolta; Bhaskar Roberts

doi:10.62056/ayzoxrxqi

Unconditional Quantum Cryptography with a Bounded Number of Keys

Authors

Vipul Goyal, Giulio Malavolta, Bhaskar Roberts

Vipul Goyal

NTT Research, USA
vipul at vipulgoyal dot org

Giulio Malavolta

Bocconi University, Italy
giulio dot malavolta at hotmail dot it

Bhaskar Roberts

UC Berkeley, USA
bhaskarr at eecs dot berkeley dot edu

Abstract

We construct the following cryptographic primitives with unconditional security in a bounded-key model:

One-time public-key encryption, where the public keys are pure quantum states
One-time signatures, where the verification keys are pure quantum states.

In our model, the adversary is given a bounded number of copies of the public key. We present efficient constructions and nearly-tight lower bounds for the size of the secret keys.

Our security proofs are based on the quantum coupon collector problem, which was originally studied in the context of learning theory. The quantum coupon collector seeks to learn a set of strings (coupons) when given several copies of a superposition over the coupons. We make novel connections between this problem and cryptography.

Our main technical ingredient is a family of coupon states, with randomized phases, that come with strong hardness properties. Our analysis improves on prior work by (i) showing that the number of quantum states needed to learn the entire set of coupons is identical to the number of random coupons needed in the classical coupon collector problem. (ii) Furthermore we prove that this result holds for a randomly chosen set of coupons, whereas prior work only lower-bounded the number of coupon states required to learn the worst-case set of coupons.

References

[ABC⁺20]

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum Coupon Collector. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:17, Dagstuhl, Germany. 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.TQC.2020.10

Google Scholar ePrint

[ABF⁺23]

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum Pseudoentanglement. 2023.

Google Scholar ePrint

[BBSS23]

Amit Behera, Zvika Brakerski, Or Sattath, and Omri Shmueli. Pseudorandomness with Proof of Destruction and Applications. In Guy Rothblum and Hoeteck Wee, editors, Theory of Cryptography, pages 125–154, Cham. 2023. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-48624-1_5

Google Scholar ePrint

[BCWdW01]

Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum Fingerprinting. Phys. Rev. Lett., 87:167902, September 2001. DOI: 10.1103/PhysRevLett.87.167902

Google Scholar ePrint

[BGHD⁺23]

Khashayar Barooti, Alex B. Grilo, Loïs Huguenin-Dumittan, Giulio Malavolta, Or Sattath, Quoc-Huy Vu, and Michael Walter. Public-Key Encryption with Quantum Keys. In Guy Rothblum and Hoeteck Wee, editors, Theory of Cryptography, pages 198–227, Cham. 2023. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-48624-1_8

Google Scholar ePrint

[CW77]

Larry Carter and Mark N. Wegman. Universal Classes of Hash Functions (Extended Abstract). In John E. Hopcroft, Emily P. Friedman, and Michael A. Harrison, editors, Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA, pages 106–112. 1977. ACM. DOI: 10.1145/800105.803400

Google Scholar ePrint

[HKP20]

Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, June 2020. DOI: 10.1038/s41567-020-0932-7

Google Scholar ePrint

[KL14]

Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography, Second Edition. Chapman & Hall/CRC, 2nd edition. 2014.

Google Scholar ePrint

[KMNY24]

Fuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa. Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, pages 93–125, Cham. 2024. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-68394-7_4

Google Scholar ePrint

[MW23]

Giulio Malavolta and Michael Walter. Non-Interactive Quantum Key Distribution. CoRR, abs/2304.02999, 2023. DOI: 10.48550/arXiv.2304.02999

Google Scholar ePrint

[MY22]

Tomoyuki Morimae and Takashi Yamakawa. Quantum Commitments and Signatures Without One-Way Functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 269–295, Cham. 2022. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-15802-5_10

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ayzoxrxqi

History

Submitted: 2024-10-09
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Vipul Goyal, Giulio Malavolta, and Bhaskar Roberts, Unconditional Quantum Cryptography with a Bounded Number of Keys. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ayzoxrxqi.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/ayzoxrxqi,
         author={Vipul Goyal and Giulio Malavolta and Bhaskar Roberts},
         title={Unconditional Quantum Cryptography with a Bounded Number of Keys},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/ayzoxrxqi},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Vipul Goyal
AU  - Giulio Malavolta
AU  - Bhaskar Roberts
PY  - 2025
TI  - Unconditional Quantum Cryptography with a Bounded Number of Keys
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/ayzoxrxqi
UR  - https://doi.org/10.62056/ayzoxrxqi
AB  - <p>    We construct the following cryptographic primitives with unconditional security in a bounded-key model:     </p><ul>         <li>One-time public-key encryption, where the public keys are pure quantum states         </li><li>One-time signatures, where the verification keys are pure quantum states.     </li></ul><p>     In our model, the adversary is given a bounded number of copies of the public key. We present efficient constructions and nearly-tight lower bounds for the size of the secret keys.</p><p>    Our security proofs are based on the quantum coupon collector problem, which was originally studied in the context of learning theory. The quantum coupon collector seeks to learn a set of strings (coupons) when given several copies of a superposition over the coupons. We make novel connections between this problem and cryptography.</p><p>    Our main technical ingredient is a family of coupon states, with randomized phases, that come with strong hardness properties. Our analysis improves on prior work by (i) showing that the number of quantum states needed to learn the entire set of coupons is identical to the number of random coupons needed in the classical coupon collector problem. (ii) Furthermore we prove that this result holds for a randomly chosen set of coupons, whereas prior work only lower-bounded the number of coupon states required to learn the worst-case set of coupons. </p>
ER  -

Vipul Goyal, Giulio Malavolta, and Bhaskar Roberts, Unconditional Quantum Cryptography with a Bounded Number of Keys. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/ayzoxrxqi.