  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.
