Quantum computational cryptography

Akinori Kawachi*, Takeshi Koshiba

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapter


As computational approaches to classical cryptography have succeeded in the establishment of the foundation of the network security, computational approaches even to quantum cryptography are promising, since quantum computational cryptography could offer richer applications than the quantum key distribution. Our project focused especially on the quantum one-wayness and quantum public-key cryptosystems. The one-wayness of functions (or permutations) is one of the most important notions in computational cryptography. First, we give an algorithmic characterization of quantum one-way permutations. In other words, we show a necessary and sufficient condition for quantum one-way permutations in terms of reflection operators. Second, we introduce a problem of distinguishing between two quantum states as a new underlying problem that is harder to solve than the graph automorphism problem. The new problem is a natural generalization of the distinguishability problem between two probability distributions, which are commonly used in computational cryptography. We show that the problem has several cryptographic properties and they enable us to construct a quantum public-key cryptosystem, which is likely to withstand any attack of a quantum adversary.

Original languageEnglish
Title of host publicationQuantum Computation and Information
Subtitle of host publicationFrom Theory to Experiment
EditorsHiroshi Imai, Masahito Hayashi
Number of pages18
Publication statusPublished - 2006 Jun 10
Externally publishedYes

Publication series

NameTopics in Applied Physics
ISSN (Print)0303-4216
ISSN (Electronic)1437-0859

ASJC Scopus subject areas

  • Physics and Astronomy (miscellaneous)


Dive into the research topics of 'Quantum computational cryptography'. Together they form a unique fingerprint.

Cite this