We give an exponential separation between one-way quantum and classical communication protocols for two partial 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 exhibit a 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 \emph{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.

ACM
D.S. Johnson , U. Feige
Quantum Computing: algorithms, proofs and tradeoffs , Qubit Applications
Annual ACM Symposium on Theory of Computing
Quantum Computing and Advanced System Research

Gavinsky, D, Kempe, J, Kerenidis, I, Raz, R, & de Wolf, R.M. (2007). Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography. In D.S Johnson & U Feige (Eds.), Proceedings of 39th STOC (pp. 516–525). ACM.