{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:40:39Z","timestamp":1763811639286,"version":"3.41.2"},"reference-count":11,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T00:00:00Z","timestamp":1728432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,3,11]]},"abstract":"<jats:p>    We construct the following cryptographic primitives with unconditional security in a bounded-key model:     <\/jats:p>\n            <jats:p>* One-time public-key encryption, where the public keys are pure quantum states         <\/jats:p>\n            <jats:p>* One-time signatures, where the verification keys are pure quantum states.     <\/jats:p>\n          <jats: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.<\/jats:p>\n          <jats: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.<\/jats:p>\n          <jats: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. <\/jats:p>","DOI":"10.62056\/ayzoxrxqi","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:23:17Z","timestamp":1744147397000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["Unconditional Quantum Cryptography with a Bounded Number of Keys"],"prefix":"10.62056","volume":"2","author":[{"given":"Vipul","family":"Goyal","sequence":"first","affiliation":[{"name":"NTT Research","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9737-0094","authenticated-orcid":false,"given":"Giulio","family":"Malavolta","sequence":"additional","affiliation":[{"name":"Bocconi University","place":["Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4057-5952","authenticated-orcid":false,"given":"Bhaskar","family":"Roberts","sequence":"additional","affiliation":[{"name":"UC Berkeley","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:ABC+20","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2020.10","article-title":"Quantum Coupon Collector","volume":"158","author":"Srinivasan Arunachalam","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959771467","ISSN":"https:\/\/id.crossref.org\/issn\/1868-8969","issn-type":"electronic"},{"key":"ref2:BGH+23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/978-3-031-48624-1_8","article-title":"Public-Key Encryption with\u00a0Quantum Keys","author":"Khashayar Barooti","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031486241"},{"key":"ref3:SWAP","doi-asserted-by":"publisher","first-page":"167902","DOI":"10.1103\/PhysRevLett.87.167902","article-title":"Quantum Fingerprinting","volume":"87","author":"Harry Buhrman","year":"2001","journal-title":"Phys. Rev. Lett."},{"key":"ref4:C:MorYam22","isbn-type":"print","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-031-15802-5_10","article-title":"Quantum Commitments and\u00a0Signatures Without One-Way\n  Functions","author":"Tomoyuki Morimae","year":"2022","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031158025"},{"key":"ref5:Tamper","isbn-type":"print","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-031-68394-7_4","article-title":"Quantum Public-Key Encryption with\u00a0Tamper-Resilient Public\n  Keys from\u00a0One-Way Functions","author":"Fuyuki Kitagawa","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031683947"},{"key":"ref6:NIQKD","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.02999","article-title":"Non-Interactive Quantum Key Distribution","volume":"abs\/2304.02999","author":"Giulio Malavolta","year":"2023","journal-title":"CoRR"},{"key":"ref7:ITMACs","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1145\/800105.803400","article-title":"Universal Classes of Hash Functions (Extended Abstract)","author":"Larry Carter","year":"1977"},{"key":"ref8:BBSS23","isbn-type":"print","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-031-48624-1_5","article-title":"Pseudorandomness with\u00a0Proof of\u00a0Destruction\n  and\u00a0Applications","author":"Amit Behera","year":"2023","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031486241"},{"key":"ref9:KL14","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1201\/b17668","volume-title":"Introduction to Modern Cryptography, Second Edition","author":"Jonathan Katz","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/1466570261"},{"volume-title":"Quantum Pseudoentanglement","year":"2023","author":"Scott Aaronson","key":"ref10:ABFGVZZ23"},{"key":"ref11:HKP20","doi-asserted-by":"publisher","first-page":"1050","DOI":"10.1038\/s41567-020-0932-7","article-title":"Predicting many properties of a quantum system from very few\n  measurements","volume":"16","author":"Hsin-Yuan Huang","year":"2020","journal-title":"Nature Physics"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T21:23:30Z","timestamp":1744147410000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":11,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/ayzoxrxqi","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2024-10-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-4-56"}}