Journal
SIAM JOURNAL ON COMPUTING
Volume 38, Issue 5, Pages 1695-1708Publisher
SIAM PUBLICATIONS
DOI: 10.1137/070706550
Keywords
communication complexity; exponential separation; quantum communication; one-way communication; hidden matching problem; quantum cryptography; bounded-storage model; extractor; streaming model
Funding
- Canada's NSERC
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available