Physics – Quantum Physics
Scientific paper
2006-11-20
Proc. 39th STOC, p. 516-525 (2007)
Physics
Quantum Physics
16 pages, improved version, supersedes quant-ph/0607173 and quant-ph/0607174 although some proofs are different
Scientific paper
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.) Earlier such an exponential separation was known only for a relational problem. The communication problem corresponds to a \emph{strong extractor} that fails against a small amount of \emph{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.
Gavinsky Dmitry
Kempe Julia
Kerenidis Iordanis
Raz Ran
Wolf Ronald de
No associations
LandOfFree
Exponential separations for one-way quantum communication complexity, with applications to cryptography does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exponential separations for one-way quantum communication complexity, with applications to cryptography, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exponential separations for one-way quantum communication complexity, with applications to cryptography will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-121006