Quantum trapdoor functions from classical one-way functions

Andrea Coladangelo

Paper 2023/282

Quantum trapdoor functions from classical one-way functions

Andrea Coladangelo

, University of Washington

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: quantum cryptography one-way functions trapdoor functions
Contact author(s): coladan @ cs washington edu
History: 2023-02-27: approved; 2023-02-24: received; See all versions
Short URL: https://ia.cr/2023/282
License: CC BY

BibTeX

@misc{cryptoeprint:2023/282,
      author = {Andrea Coladangelo},
      title = {Quantum trapdoor functions from classical one-way functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/282},
      year = {2023},
      url = {https://eprint.iacr.org/2023/282}
}