ECCC-Report TR03-071https://eccc.weizmann.ac.il/report/2003/071Comments and Revisions published for TR03-071en-usWed, 25 May 2005 00:00:00 +0300
Revision 1
| Privacy in Non-Private Environments |
Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey
https://eccc.weizmann.ac.il/report/2003/071#revision1We study private computations in information-theoretical settings on networks that are not 2-connected. Non-2-connected networks are "non-private" in the sense that most functions cannot privately be computed on them. We relax the notion of privacy by introducing lossy private protocols, which generalize private protocols. We measure the information each player gains during the computation. Good protocols should minimize the amount of information they lose to the players. Throughout this work, privacy always means 1-privacy, i.e. players are not allowed to share their knowledge. Furthermore, the players are honest but curious, thus they never deviate from the given protocol.
By use of randomness by the protocol the communication strings a certain player can observe on a particular input determine a probability distribution. We define the loss of a protocol to a player as the logarithm of the number of different probability distributions the player can observe. For optimal protocols, this is justified by the following result: For a particular content of any player's random tape, the distributions the player observes have pairwise fidelity zero. Thus the player can easily distinguish the distributions.
The simplest non-2-connected networks consists of two blocks that share one bridge node. We prove that on such networks, communication complexity and the loss of a private protocol are closely related: Up to constant factors, they are the same.
Then we study one-phase protocols, an analogue of one-round communication protocols. In such a protocol each bridge node may communicate with each block only once. We investigate in which order a bridge node should communicate with the blocks to minimize the loss of information. In particular, for symmetric functions it is optimal to sort the components by increasing size. Then we design a one-phase protocol that for symmetric functions simultaneously minimizes the loss at all nodes where the minimum is taken over all one-phase protocols.
Finally, we prove a phase hierarchy. For any $k$ there is a function such that every (k-1)-phase protocol for this function has an information loss that is exponentially greater than that of the best k-phase protocol.
Wed, 25 May 2005 00:00:00 +0300https://eccc.weizmann.ac.il/report/2003/071#revision1
Paper TR03-071
| Privacy in Non-Private Environments |
Markus Bläser,
Andreas Jakoby,
Maciej Liskiewicz,
Bodo Manthey
https://eccc.weizmann.ac.il/report/2003/071We study private computations in information-theoretical settings on
networks that are not 2-connected. Non-2-connected networks are
``non-private'' in the sense that most functions cannot privately be
computed on such networks. We relax the notion of privacy by
introducing lossy private protocols, which generalize private
protocols. We measure the information each player gains during the
computation. Good protocols should minimize the amount of information
it loses to the players.
The loss of a protocol to a player is the logarithm of the number of
different probability distributions on the communication strings a
player can observe. For optimal protocols, this is justified by the
following result: For a particular content of any player's random
tape, the distributions the player observes have pairwise fidelity
zero. Thus the player can easily distinguish the distributions.
The simplest non-2-connected networks consists of two blocks that
share one bridge node. We prove that on such networks, communication
complexity and the loss of a private protocol are closely related: Up
to constant factors, they are the same.
Then we study 1-phase protocols, an analogue of 1-round communication
protocols. In such a protocol each bridge node may communicate with
each block only once. We investigate in which order a bridge node
should communicate with the blocks to minimize the loss of
information. In particular, for symmetric functions it is optimal to
sort the components by increasing size. Then we design a 1-phase
protocol that for symmetric functions simultaneously minimizes the
loss at all nodes, where the minimum is taken over all 1-phase
protocols.
Finally, we prove a phase hierarchy. For any k there is a function
such that every (k-1)-phase protocol for this function has an
information loss that is exponentially greater than that of the best
k-phase protocol.
Thu, 02 Oct 2003 13:41:50 +0300https://eccc.weizmann.ac.il/report/2003/071