Quantum and Approximate Privacy
Quantum and Approximate Privacy
复制标题
量子和近似隐私
DOI：
10.1007/s00224-003-1113-7
复制
发表时间：
2001
影响因子：
0.5
通讯作者：
H. Klauck
中科院分区：
文献类型：
--
作者：
H. Klauck
摘要
本文研究了通信复杂度下的隐私和安全功能评估问题。重点是量子版本的模型和
只有近似隐私的协议对抗诚实的玩家。我们表明，隐私损失（最小泄露信息）在计算一个
函数可以通过使用量子协议指数地减少，而私有可计算函数类（即，那些有隐私的人
损耗0）不被量子协议放大。另一方面，量子通信与小信息泄漏相结合，
（几乎）可私下计算的函数，这些函数使用无泄漏的量子通信或经典通信都不可计算
泄漏。我们还给出了一个例子，通过允许隐私损失，函数的通信复杂度呈指数级降低。
o（1）而不是隐私损失0。
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.