Exponential separations for one-way quantum communication complexity, with applications to cryptography

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald De Wolf

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

100 Scopus citations

Abstract

We give an exponential separation between one-way quantum and classical communication protocols for twopartial Boolean functions, both of which are variants of the Boolean Hidden Matching Problem of Bar-Yossef et al. Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proofs use the Fourier coefficients inequality of Kahn, Kalai, and Linial. We give a number of applications of this separation. In particular, in the bounded-storage model of cryptography we exhibita scheme that is secure against adversaries with a certain amount of classical storage, but insecure against adversaries with a similar (or even much smaller) amount of quantum storage; in the setting of privacy amplification, we show that there are strong extractors that yield a classically secure key, but are insecure against a quantum adversary.

Original languageEnglish (US)
Title of host publicationSTOC'07
Subtitle of host publicationProceedings of the 39th Annual ACM Symposium on Theory of Computing
Pages516-525
Number of pages10
DOIs
StatePublished - 2007
Externally publishedYes
EventSTOC'07: 39th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 11 2007Jun 13 2007

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

OtherSTOC'07: 39th Annual ACM Symposium on Theory of Computing
Country/TerritoryUnited States
CitySan Diego, CA
Period6/11/076/13/07

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication complexity
  • Cryptography
  • Quantum

Fingerprint

Dive into the research topics of 'Exponential separations for one-way quantum communication complexity, with applications to cryptography'. Together they form a unique fingerprint.

Cite this