2023/02/24 by Andrea Coladangelo, Coladangelo, Andrea · 2 citations
Computer Science · #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.2302.12821
openalex publication_date 2023/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We formalize and study the notion of a quantum trapdoor function. This is an efficiently computable unitary that takes as input a "public" quantum state and a classical string x, and outputs a quantum state. This map is such that (i) it is hard to invert, in the sense that it is hard to recover x given the output state (and many copies of the public state), and (ii) there is a classical trapdoor that allows efficient inversion. We show that a quantum trapdoor function can be constructed from any quantum-secure one-way function. A direct consequence of this result is that, assuming just the existence of quantum-secure one-way functions, there exists a public-key encryption scheme with a (pure) quantum public key.