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

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

Research output: Contribution to journalArticle

Abstract

We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean hidden matching problem of Bar-Yossef et al.). Previously, such an exponential separation was known only for a relational problem. The communication problem corresponds to a strong extractor that fails against a small amount of quantum information about its random source. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones.

Original languageEnglish (US)
Pages (from-to)1695-1708
Number of pages14
JournalSIAM Journal on Computing
Volume38
Issue number5
DOIs
StatePublished - 2008

Keywords

  • Bounded-storage model
  • Communication complexity
  • Exponential separation
  • Extractor
  • Hidden matching problem
  • One-way communication
  • Quantum communication
  • Quantum cryptography
  • Streaming model

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this