Exponential separations for one-way quantum communication complexity, with applications to cryptography
Authors:
Open Access
- 11 June 2007
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 38 (5) , 516-525
Abstract
We give an exponential separation between one-way quantum and classical communication protocols for twopartial Boolean functions, both of which are variants of the Boolean Hidden Matching Problem of Bar-Yossef et al. Earlier such an exponential separation was known only for a relational version of the Hidden Matching Problem. Our proofs use the Fourier coefficients inequality of Kahn, Kalai, and Linial. We give a number of applications of this separation. In particular, in the bounded-storage model of cryptography we exhibita scheme that is secure against adversaries with a certain amount of classical storage, but insecure against adversaries with a similar (or even much smaller) amount of quantum storage; in the setting of privacy amplification, we show that there are strong extractors that yield a classically secure key, but are insecure against a quantum adversary.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Quantum communication and complexityTheoretical Computer Science, 2002
- Everlasting security in the bounded storage modelIEEE Transactions on Information Theory, 2002
- Quantum FingerprintingPhysical Review Letters, 2001
- The Space Complexity of Approximating the Frequency MomentsJournal of Computer and System Sciences, 1999
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- How much are increasing sets positively correlated?Combinatorica, 1996
- Fourier analysis for probabilistic communication complexitycomputational complexity, 1995
- Private vs. common random bits in communication complexityInformation Processing Letters, 1991
- Inequalities in Fourier AnalysisAnnals of Mathematics, 1975
- Étude des coefficients de Fourier des fonctions deAnnales de l'institut Fourier, 1970