Paper 2015/385

Feasibility and Completeness of Cryptographic Tasks in the Quantum World

Serge Fehr, Jonathan Katz, Fang Song, Hong-Sheng Zhou, and Vassilis Zikas

Abstract

It is known that cryptographic feasibility results can change by moving from the classical to the quantum world. With this in mind, we study the feasibility of realizing functionalities in the framework of universal composability, with respect to both computational and information-theoretic security. With respect to computational security, we show that existing feasibility results carry over unchanged from the classical to the quantum world; a functionality is “trivial” (i.e., can be realized without setup) in the quantum world if and only if it is trivial in the classical world. The same holds with regard to functionalities that are complete (i.e., can be used to realize arbitrary other functionalities). In the information-theoretic setting, the quantum and classical worlds differ. In the quantum world, functionalities in the class we consider are either complete, trivial, or belong to a family of simultaneous-exchange functionalities (e.g., XOR). However, other results in the information-theoretic setting remain roughly unchanged.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in TCC 2013
Keywords
cryptographic reductionsquantum security
Contact author(s)
fang song @ uwaterloo ca
History
2015-04-29: revised
2015-04-28: received
See all versions
Short URL
https://ia.cr/2015/385
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/385,
      author = {Serge Fehr and Jonathan Katz and Fang Song and Hong-Sheng Zhou and Vassilis Zikas},
      title = {Feasibility and Completeness of Cryptographic Tasks in the Quantum World},
      howpublished = {Cryptology ePrint Archive, Paper 2015/385},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/385}},
      url = {https://eprint.iacr.org/2015/385}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.