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 language | English (US) |
---|---|
Pages (from-to) | 1695-1708 |
Number of pages | 14 |
Journal | SIAM Journal on Computing |
Volume | 38 |
Issue number | 5 |
DOIs | |
State | Published - 2008 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Mathematics
Keywords
- Bounded-storage model
- Communication complexity
- Exponential separation
- Extractor
- Hidden matching problem
- One-way communication
- Quantum communication
- Quantum cryptography
- Streaming model