Information Technology Reference
In-Depth Information
curity models for centralized mechanism execution in which the center proves its cor-
rectness (in zero-knowledge) and that provide differing degrees of privacy. However,
in these models, privacy always has to rely on the trustworthiness of the mechanism
center. For this reason, we showed how participating agents can emulate a (correct)
“virtual” mechanism center by jointly computing the mechanism outcome without a
trusted third-party. The emulation of a restricted class of mechanisms, so-called simple
mechanisms, can provide unconditional privacy of preferences whereas all mechanisms
can be emulated so that privacy can only be breached by unbounded computation. In
these models, privacy builds upon the fact that it can be ruled out that all agents are
forming a coalition in order to breach privacy. Furthermore, the decentralization allows
for the provable correctness of randomized mechanisms. Table 1 summarizes the pro-
posed models for secure mechanism execution. Even though the centralized models
provide questionable privacy, there are certainly applications in which they would be
favored over the decentralized models due to practical considerations (efficiency, lack
of communication between agents, robustness, etc. ).
Ta b l e 1 . Comparison of security models with provable correctness
Center Privacy can be breached by Requirements
Th. 1
yes
center or computation
trapdoor perm., det. mech.
Th. 2
yes
center
A → C -channels, one-way perm., det. mech.
Pr. 1
no
computation
trapdoor perm.
Pr. 2
no
A → A -channels, one-way perm., simple mech.
A → C -channels: private channels from each agent to the center
A → A -channels: complete network of private channels between all agents
In addition to the revelation principle criticisms stated in [CS03b], we pointed out
that multi-step and untruthful mechanisms can drastically improve privacy in a variety
of social choice settings. In particular, we identified a class of mechanisms, so-called
privately elicitable mechanisms, for which there are fully private protocols that emulate
a preference elicitor so that a part of the preferences is never elicited and thus remains
unconditionally private and does not have to be determined by the agents.
Besides further investigation of preference protection by multi-step and untruthful
mechanisms, future directions include
- the construction of efficient zero-knowledge proofs/arguments for the outcome of
relevant mechanisms,
- the investigation of which mechanisms can be emulated by unconditionally fully
private protocols (a first step has been made in [BS04]), and
- the construction of efficient protocols that (computationally) fully privately emulate
relevant mechanisms. 11
11
We already constructed a protocol that (computationally) fully privately emulates the Vickrey
auction in just three rounds of broadcasting without any direct interaction between bidders
[Bra03a].
Search WWH ::




Custom Search