[Resource Topic] 2023/282: Quantum trapdoor functions from classical one-way functions

Welcome to the resource topic for 2023/282

Quantum trapdoor functions from classical one-way functions

Authors: Andrea Coladangelo


We introduce 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 exist: (i) a public-key encryption scheme with a quantum public key, and (ii) a two-message key-exchange protocol, assuming an appropriate notion of a quantum authenticated channel.

ePrint: https://eprint.iacr.org/2023/282

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .