Pseudo-Deterministic One-Way Functions from Pseudorandom States

Quantum cryptography has shed light on the potential redundancy of one-way functions (OWFs) in certain applications, where it would otherwise be required classically. It has been revealed that many such cryptographic primitives can be constructed using the concept of pseudorandom quantum states (PRSs), which represent a potentially weaker foundational assumption. In this work, we aim to investigate and provide a more comprehensive understanding of the relationship between PRSs and OWFs. To begin, we introduce the novel notion of pseudo-deterministic one-way functions (QPD-OWFs). These are similar to conventional OWFs with the exception that the output is deterministic only with high probability. Our study demonstrates that QPD-OWFs can indeed be derived from PRSs, utilizing recent developments in the construction of pseudo-deterministic pseudorandom functions from PRSs. As a direct outcome of this revelation, we present a (many-time) digital signature scheme for classical messages with classical signatures, thereby addressing a previously unresolved question posed in Morimae and Yamakawa's work (Crypto, 2022). Furthermore, we devise a quantum public-key encryption scheme featuring reusable public-keys, constructed from pseudorandom function-like states. This contribution supersedes previous constructions, which relied on stronger assumptions or failed to ensure reusability.