Paper 2015/687

Classical Cryptographic Protocols in a Quantum World

Sean Hallgren, Adam Smith, and Fang Song

Abstract

Cryptographic protocols, such as protocols for secure function evaluation (SFE), have played a crucial role in the development of modern cryptography. The extensive theory of these protocols, however, deals almost exclusively with classical attackers. If we accept that quantum information processing is the most realistic model of physically feasible computation, then we must ask: what classical protocols remain secure against quantum attackers? Our main contribution is showing the existence of classical two-party protocols for the secure evaluation of any polynomial-time function under reasonable computational assumptions (for example, it suffices that the learning with errors problem be hard for quantum polynomial time). Our result shows that the basic two-party feasibility picture from classical cryptography remains unchanged in a quantum world.

Note: Full version of an old paper in Crypto'11. Invited to International Journal of Quantum Information Vol. 13, No. 4 (2015) DOI: 10.1142/S0219749915500288

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2011
Keywords
quantum attackscomposition
Contact author(s)
fang song @ uwaterloo ca
History
2015-07-13: received
Short URL
https://ia.cr/2015/687
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/687,
      author = {Sean Hallgren and Adam Smith and Fang Song},
      title = {Classical Cryptographic Protocols in a Quantum World},
      howpublished = {Cryptology ePrint Archive, Paper 2015/687},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/687}},
      url = {https://eprint.iacr.org/2015/687}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.