Paper 2022/1323

On Constructing One-Way Quantum State Generators, and More

Abstract

As a quantum analogue of one-way function, the notion of one-way quantum state generator is recently proposed by Morimae and Yamakawa (CRYPTO'22), which is proved to be implied by the pseudorandom state and can be used to devise the one-time secure digital signature. Due to Kretschmer's result (TQC'20), it's believed that pseudorandom state generator requires less than post-quantum secure one-way function. Unfortunately, it remains to be unknown how to achieve the one-way quantum state generator without the existence of post-quantum secure one-way function. In this paper, we mainly study that problem and obtain the following results: Two variants of one-way quantum state generator are proposed, called the weak one-way quantum state generator and distributionally one-way quantum state generator. Then the equivalence between weak and strong one-way state generator is obtained, and the equivalence between weak and distributionally one-way quantum state generator is shown in the symmetric setting. We construct the symmetric distributionally one-way quantum state generator from average-case hardness assumption of a promise problem belongs to $\textsf{QSZK}$. We construct quantum bit commitment with statistical binding (sum-binding) and computational hiding directly from the average-case hardness of $\textsf{QSZK}$. To show the non-triviality of the constructions above, a quantum oracle $\mathcal{U}$ is devised relative to which such promise problem in $ \textsf{QSZK}$ doesn't belong to $\mathsf{QMA}^{\mathcal{U}}$. Our results present the first non-trivial construction of one-way quantum state generator from the hardness assumption of complexity class, and give another evidence that one-way quantum state generator probably requires less than post-quantum secure one-way function.

Note: We have been reminded of a technical flaw in Polarization Lemma (Lemma 7). Despite our efforts to rectify the issue, we have been unsuccessful in doing so. As a temporary solution, we are only able to establish the equivalence between weak and distributional OWSG in a "symmetric" setting. We have updated the revised version and remain hopeful that the general results regarding the relationship between weak and distributional OWSG can be eventually ascertained.