Paper 2021/1691

Quantum commitments and signatures without one-way functions

Tomoyuki Morimae and Takashi Yamakawa

Abstract

All known constructions of classical or quantum commitments require at least one-way functions. Are one-way functions really necessary for commitments? In this paper, we show that non-interactive quantum commitments (for classical messages) with computational hiding and statistical binding exist if pseudorandom quantum states exist. Pseudorandom quantum states are sets of quantum states that are efficiently generated but computationally indistinguishable from Haar random states [Z. Ji, Y.-K. Liu, and F. Song, CRYPTO 2018]. It is known that pseudorandom quantum states exist even if BQP=QMA (relative to a quantum oracle) [W. Kretschmer, TQC 2021], which means that pseudorandom quantum states can exist even if no quantum-secure classical cryptographic primitive exists. Our result therefore shows that quantum commitments can exist even if no quantum-secure classical cryptographic primitive exists. In particular, quantum commitments can exist even if no quantum-secure one-way function exists. We also show that one-time secure signatures with quantum public keys exist if pseudorandom quantum states exist. In the classical setting, the existence of signatures is equivalent to the existence of one-way functions. Our result, on the other hand, suggests that quantum signatures can exist even if no quantum-secure classical cryptographic primitive (including quantum-secure one-way functions) exists.