Quantum and approximate privacy

DOI10.1007/S00224-003-1113-7zbMATH Open1107.68422arXivquant-ph/0110038OpenAlexW2002917701WikidataQ58040235 ScholiaQ58040235MaRDI QIDQ705071FDOQ705071

Authors: Hartmut Klauck 

Publication date: 25 January 2005

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

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.

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

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

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)

Cited In (13)

• Interactive Information Complexity
• Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
• Interactive Information Complexity
• Quantum privacy and quantum wiretap channels
• Duality of privacy amplification against quantum adversaries and data compression with quantum side information
• Title not available (Why is that?)
• Quantifying the leakage of quantum protocols for classical two-party cryptography
• Gentle measurement of quantum states and differential privacy
• A discrepancy lower bound for information complexity
• Certifying equality with limited interaction
• Information lower bounds via self-reducibility
• Quantum Private Queries
• Susceptible Two-Party Quantum Computations

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)