TY - GEN
T1 - Exponential separations for one-way quantum communication complexity, with applications to cryptography
AU - Gavinsky, Dmitry
AU - Kempe, Julia
AU - Kerenidis, Iordanis
AU - Raz, Ran
AU - De Wolf, Ronald
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - Communication complexity
KW - Cryptography
KW - Quantum
UR - http://www.scopus.com/inward/record.url?scp=35448991662&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35448991662&partnerID=8YFLogxK
U2 - 10.1145/1250790.1250866
DO - 10.1145/1250790.1250866
M3 - Conference contribution
AN - SCOPUS:35448991662
SN - 1595936319
SN - 9781595936318
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 516
EP - 525
BT - STOC'07
T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing
Y2 - 11 June 2007 through 13 June 2007
ER -