Commitments are Equivalent to Statistically-Verifiable One-Way State Generators

One-way state generators (OWSG) [MY22a] are natural quantum analogs to classical one-way functions. We consider statistically-verifiable OWSGs (sv-OWSG), which are potentially weaker objects than OWSGs. We show that O ´n logpnq ¯-copy sv-OWSGs (n represents the input length) are equivalent to polypnq-copy sv-OWSGs and to quantum commitments. Since known results show that o ´n logpnq ¯-copy OWSGs cannot imply commitments [CGG `23], this shows that O ´n logpnq ¯-copy sv-OWSGs are the weakest OWSGs from which we can get commitments (and hence much of quantum cryptography).

Our construction follows along the lines of Håstad, Impagliazzo, Levin and Luby [HILL99], who obtained classical pseudorandom generators (PRG) from classical one-way functions (OWF), however with crucial modifications. Our construction, when applied to the classical case, provides an alternative to the construction provided by [HILL99] to obtain a classical mildly non-uniform PRG from any classical OWF. Since we do not argue conditioned on the output f pxq, our construction and analysis is arguably simpler and may be of independent interest. For converting a mildly non-uniform PRG to a uniform PRG, we can use the same construction as [HILL99].

logpnq for some constant c ą 0. An m-copy sv-OWSG implies oblivious transfer and secure multi-party computation for all functionalities.

We show the converse to Corollary 2 is also true.

Combining the above results we get: Corollary 5. The following cryptographic primitives are equivalent:

• polypnq-copy sv-OWSG,

A natural question that can be asked at this point is whether an o ´n logpnq ¯-copy sv-OWSG implies a polypnq-copy sv-OWSG (equivalently EFI)? Cavalar et al. [CGG `23] show that o ´n logpnq ¯copy pure-state output OWSGs (that are potentially stronger than sv-OWSGs) with statistical security exist unconditionally. Hence they cannot imply an EFI unless EFIs also exist unconditionally. This gives the following corollary.

Corollary 6. Unless EFIs exist unconditionally, O ´n logpnq ¯-copy sv-OWSGs are the weakest OWSGs from which we can get an EFI, equivalently, commitment schemes.