2006/11/30 by Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis +2 · 4 citations
Computer Science · Engineering · #Coding theory and cryptography #Quantum Computing Algorithms and Architecture #graph theory and CDMA systems
paper · doi:10.1145/1250790.1250866
openalex publication_date 2007/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.