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 follwing 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.
Short Bio:
Rahul Jain is a Professor at the Computer Science Department, National University of Singapore (NUS). He was an Associate Professor from 2013 to 2019 and an Assistant Professor from 2009 to 2013 at NUS. He obtained his PhD from the Tata Institute of Fundamental Research (TIFR), Mumbai, India, in 2003. He was a post-doctoral researcher at the University of California at Berkeley, USA, from 2004 to 2006 and at the Institute for Quantum Computing (IQC), University of Waterloo, Canada, from 2006 to 2008. He obtained a Bachelor's degree (B.Tech) in Electrical and Electronics Engineering from the Indian Institute of Technology, Mumbai (IITB), India, in 1997. He has been a Principal Investigator at the Centre for Quantum Technologies (CQT) in Singapore since 2009.
