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

65 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
CountryUnited 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

    Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., & De Wolf, R. (2007). Exponential separations for one-way quantum communication complexity, with applications to cryptography. In STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (pp. 516-525). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/1250790.1250866