Information Technology Reference
In-Depth Information
in the context of correctness and privacy. The paper concludes with a summary of the
obtained results and a brief outlook on future research in Section 5.
2
Related Work
In [MPS03], a connection between mechanism design and multiparty computation has
been established for a purpose that is slightly different from the one we pursue in this
paper. The authors integrate “cryptographic objectives” such as the wish to keep other
agents from learning one's preferences, the wish to learn other agents' preferences, the
wish to know the correct mechanism outcome, and the wish to prevent others from
knowing it into the utility functions of agents and then investigate the possibility of
incentive-compatible mechanism design in this novel framework. A similar approach
without a mechanism center was recently analyzed in [HT04]. [MT99] consider a model
where agents are not directly connected to the center, but are rather nodes in a more
general communication network.
To our knowledge, the first paper to explicitly present a security model and generic
protocol for arbitrary mechanisms was [NPS99]. This model basically consists of two
centers that are assumed not to collude. The decentralized model presented in Sec-
tion 3.2 is based on preliminary results lately proposed in [Bra03b]. The importance of
considering the privacy of agents in distributed mechanisms has been stated in
[FNR
+
02, FS02].
In recent years, there has been a large body of research on cryptographic auction pro-
tocols,
i.e.
, protocols that privately compute the outcome of sealed-bid auction mecha-
nisms (
e.g.
, [Bra03a, Kik01, NPS99]). These special-purpose protocols implicitly con-
tain security models (of which almost all are based on using more than one center).
3
Security Models
In this section, we investigate which sets of assumptions (general model, communi-
cation channels, existence of one-way functions,
etc.
) allow the provably correct ex-
ecution of deterministic single-step mechanisms. In particular, we examine whether
unconditional
privacy,
i.e.
, privacy that can never be breached, even when unbounded
computational power becomes available, can be achieved in a given model.
In order to enable the notion of unconditional privacy in the first place, we have
to make the following distinction. While we (in some models) allow unbounded com-
putational power to breach privacy
after
the protocol/mechanism terminated, super-
polynomial computational power is
not
available
during
the protocol. The deep rela-
tion between correctness and privacy makes this assumption necessary.
1
Nevertheless,
this assumption seems reasonable since the time needed to perform super-polynomial
computation is presumably longer than the typically short execution time of a mecha-
nism. Furthermore, we generally assume the availability of a public key infrastructure.
In some cases, we will assume “private channels” between certain parties. These are
1
Otherwise, privacy could be breached by violating correctness (
e.g.
, by forging perfect zero-
knowledge arguments).
