Back to Search
Start Over
EXPONENTIAL SEPARATION FOR ONE-WAY QUANTUM COMMUNICATION COMPLEXITY, WITH APPLICATIONS TO CRYPTOGRAPHY.
- Source :
- SIAM Journal on Computing; 2009, Vol. 38 Issue 5, p1695-1708, 14p
- Publication Year :
- 2009
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 38
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 36850724
- Full Text :
- https://doi.org/10.1137/070706550