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.