Feasibility and completeness of cryptographic tasks in the quantum world

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.

Original languageEnglish
Title of host publicationTheory of Cryptography
Subtitle of host publication10th Theory of Cryptography Conference, TCC 2013, Proceedings
EditorsAmit Sahai
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages281-296
Number of pages16
ISBN (Electronic)978-3-642-36594-2
ISBN (Print)978-3-642-36593-5
DOIs
Publication statusPublished - 21 Feb 2013
Event10th Theory of Cryptography Conference - Tokyo, Japan
Duration: 3 Mar 20136 Mar 2013
https://www.iacr.org/workshops/tcc2013/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer, Berlin, Heidelberg
Volume7785
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th Theory of Cryptography Conference
Abbreviated titleTCC 2013
Country/TerritoryJapan
CityTokyo
Period3/03/136/03/13
Internet address

Fingerprint

Dive into the research topics of 'Feasibility and completeness of cryptographic tasks in the quantum world'. Together they form a unique fingerprint.

Cite this