Quantum and approximate privacy

DOI10.1007/S00224-003-1113-7MaRDI QIDQ705071zbMATH OpenOpenAlexWikidataFDO

Authors Hartmut Klauck

Publication date 25 January 2005

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0110038

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Authentication, digital signatures and secret sharing (94A62)

Abstract: This paper studies privacy and secure function evaluation in communication complexity. The focus is on quantum versions of the model and on protocols with only approximate privacy against honest players. We show that the privacy loss (the minimum divulged information) in computing a function can be decreased exponentially by using quantum protocols, while the class of privately computable functions (i.e., those with privacy loss 0) is not enlarged by quantum protocols. Quantum communication combined with small information leakage on the other hand makes certain functions computable (almost) privately which are not computable using either quantum communication without leakage or classical communication with leakage. We also give an example of an exponential reduction of the communication complexity of a function by allowing a privacy loss of $o(1)$ instead of privacy loss 0.

Recommendations

• scientific article; zbMATH DE number 2086397
• New Lower Bounds for Privacy in Communication Protocols
• Quantifying the leakage of quantum protocols for classical two-party cryptography
• On communication protocols that compute almost privately
• Privacy and Communication Complexity

Cited in

(15)

• Quantifying the leakage of quantum protocols for classical two-party cryptography
• scientific article; zbMATH DE number 2086397 (Why is no real title available?)
• Duality of privacy amplification against quantum adversaries and data compression with quantum side information
• Certifying equality with limited interaction
• Lower bounds on information complexity via zero-communication protocols and applications
• Susceptible Two-Party Quantum Computations
• Information lower bounds via self-reducibility
• Gentle measurement of quantum states and differential privacy
• Quantifying the leakage of quantum protocols for classical two-party cryptography
• Quantum privacy and quantum wiretap channels
• A property of quantum relative entropy with an application to privacy in quantum communication
• Quantum Private Queries
• Communication complexity of private simultaneous quantum messages protocols
• Interactive information complexity
• Interactive Information Complexity

This page was built for publication: Quantum and approximate privacy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705071)