|
related topics |
{key, protocol, security} |
{algorithm, log, probability} |
{let, theorem, proof} |
{information, entropy, channel} |
{states, state, optimal} |
{error, code, errors} |
{alice, bob, state} |
|
On quantum and approximate privacy
Hartmut Klauck
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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0110038
- categories:
- quant-ph
- comments:
- 30 pages, appeared at 19th Symposium on Theoretical Aspects of
Computer Science, STACS '02, to appear in Theory of Computing Systems
- doi:
- 10.1007/s00224-003-1113-7
- arxiv_id:
- quant-ph/0110038
- journal_ref:
- Theory of Computing Systems vol.37(1), pp.221-246, 2004.
- created:
- 2001-10-05
- updated:
- 2003-06-05
Full article ▸
|
|
related documents |
0105032v2 |
0609094v1 |
0608199v3 |
0402170v1 |
9803006v5 |
0601130v2 |
0012078v1 |
0405016v2 |
0504078v2 |
0410031v1 |
0504161v2 |
0505061v3 |
0201030v1 |
0608030v3 |
0403133v2 |
0307104v3 |
0503157v1 |
0503192v4 |
0505108v1 |
0603135v1 |
0310168v2 |
0503002v1 |
0410215v2 |
0111073v2 |
0409052v1 |
|