Commitments are equivalent to statistically-verifiable one-way state generators
Rahul Jain | Centre for Quantum Technologies
One-way state generators (OWSG) 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/log(n))-copy sv-OWSGs (n represents the input length) are equivalent to poly(n)-copy sv-OWSGs and to quantum commitments. Since known results show that o(n/log(n))-copy OWSGs cannot imply commitments (unless they exist unconditionally), this shows that O(n/log(n))-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 [HILL 99], 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 classical construction to obtain a classical mildly non-uniform PRG from any classical OWF (from which a uniform PRG can be obtained following along [HILL 99]). Since we do not argue conditioned on the output, our construction and analysis are arguably simpler and may be of independent interest.
Talk based on:
Commitments are equivalent to one-way state generators. Rishabh Batra, Rahul Jain. FOCS, 2024. QCrypt, 2024. TQC, 2025. ArXiv:2404.03220.
Location
-
QNC 1201
-
-
Meeting ID: 981 9955 0326
-
Passcode: 202908
-