Exponential separations for one-way quantum communication complexity, with applications to cryptography
Authors:
- Dmitry GavinskyDGDmitry Gavinsky
- Julia KempeJKJulia Kempe
- Iordanis KerenidisIKIordanis Kerenidis
- Ran RazRRRan Raz
- Ronald de WolfRWRonald de Wolf
Preprint
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.) 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.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- The Bounded-Storage Model in the Presence of a Quantum AdversaryIEEE Transactions on Information Theory, 2008
- On the Power of Quantum MemoryIEEE Transactions on Information Theory, 2005
- Optimal Randomizer Efficiency in the Bounded-Storage ModelJournal of Cryptology, 2003
- Constructing Locally Computable Extractors and Cryptosystems in the Bounded-Storage ModelJournal of Cryptology, 2003
- Encryption against Storage-Bounded Adversaries from On-Line Strong ExtractorsJournal of Cryptology, 2003
- Everlasting security in the bounded storage modelIEEE Transactions on Information Theory, 2002
- Fourier analysis for probabilistic communication complexitycomputational complexity, 1995
- Conditionally-perfect secrecy and a provably-secure randomized cipherJournal of Cryptology, 1992
- Private vs. common random bits in communication complexityInformation Processing Letters, 1991
- Privacy Amplification by Public DiscussionSIAM Journal on Computing, 1988