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

One-way state generators (OWSG) [1] 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O\left(\frac{n}{\log (n)}\right)$</tex> -copy sv-OWSGs (<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> represents the input length) are equivalent to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$poly (n)$</tex> -copy sv-OWSGs and to quantum commitments. Since known results show that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$o\left(\frac{n}{\log (n)}\right)$</tex> -copy OWSGs cannot imply commitments [2], this shows that <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O\left(\frac{n}{\log(n)}\right)$</tex> -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 Hastad, Impagliazzo, Levin and Luby [3], 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 [3] to obtain a classical mildly non-uniform PRG from any classical OWF. Since we do not argue conditioned on the output <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$f(x)$</tex>, 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 [3].