2023/11/01 by Barhoush, Mohammed, Behera, Amit, Ozer, Lior +2
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.00847
Different flavors of quantum pseudorandomness have proven useful for various cryptographic applications, with the compelling feature that these primitives are potentially weaker than post-quantum one-way functions. Ananth, Lin, and Yuen (2023) have shown that logarithmic pseudorandom states can be used to construct a pseudo-deterministic PRG: informally, for a fixed seed, the output is the same with 1-1/poly probability. In this work, we introduce new definitions for \bot-PRG and \bot-PRF. The correctness guarantees are that, for a fixed seed, except with negligible probability, the output is either the same (with probability 1-1/poly) or recognizable abort, denoted \bot. Our approach admits a natural definition of multi-time PRG security, as well as the adaptive security of a PRF. We construct a \bot-PRG from any pseudo-deterministic PRG and, from that, a \bot-PRF. Even though most mini-crypt primitives, such as symmetric key encryption, commitments, MAC, and length-restricted one-time digital signatures, have been shown based on various quantum pseudorandomness assumptions, digital signatures remained elusive. Our main application is a (quantum) digital signature scheme with classical public keys and signatures, thereby addressing a previously unresolved question posed in Morimae and Yamakawa's work (Crypto, 2022). Additionally, we construct CPA secure public-key encryption with tamper-resilient quantum public keys.