Abstract:
One-way functions are central to classical cryptography. They are both
necessary for the existence of non-trivial classical cryptosystems, and
sufficient to realize meaningful primitives including commitments, pseudorandom
generators and digital signatures. At the same time, a mounting body of
evidence suggests that assumptions even weaker than one-way functions may
suffice for many cryptographic tasks of interest in a quantum world, including
bit commitments and secure multi-party computation. This work studies one-way
state generators [Morimae-Yamakawa, CRYPTO 2022], a natural quantum relaxation
of one-way functions. Given a secret key, a one-way state generator outputs a
hard to invert quantum state. A fundamental question is whether this type of
quantum one-wayness suffices to realize quantum cryptography. We obtain an
affirmative answer to this question, by proving that one-way state generators
with pure state outputs imply quantum bit commitments and secure multiparty co
mputation. Along the way, we build an intermediate primitive with classical
outputs, which we call a (quantum) one-way puzzle. Our main technical
contribution is a proof that one-way puzzles imply quantum bit commitments.
Joint work with Dakshita Khurana. arxiv.org/abs/2310.11526 .
