On Correctness and Privacy in Distributed Mechanisms - Agent-Mediated Electronic Commerce - page 217

3.2 Decentralized Mechanism Execution

In order to decentralize the trust that agents need to have in a single center, the computation
of the outcome can be distributed across several distinct centers. This is just a straight-
forward application of secure multiparty computation [GMW87, BGW88, CCD88]. It
is possible to generate shares of a secret piece of information so that a single share is
“worthless”, i.e. , it reveals no information at all, but all shares put together uniquely de-
termine the original piece of information. 5 Assume that agents distribute shares of their
preferences so that each center receives one share from each agent. Multiparty computa-
tion protocols allow the centers to jointly compute the mechanism outcome using these
shares. Depending on the protocol and the underlying security model, privacy may rely
on computational intractability. In any case, privacy also relies on the assumption that a
coalition of all centers is ruled out. When all centers collude and share their information,
they can reconstruct each agent's private preferences. Nevertheless, this model is used in
almost all existing cryptographic auction protocols. Especially the special case for two
centers, as introduced by [Yao82], has been widely used.
In this section, we aim to obtain a more satisfying level of privacy by omitting the
center(s) completely and letting agents resolve the mechanism by themselves. In other
words, the mechanism's participants engage in a multiparty computation protocol. The
key observation underlying this model is that if there is a coalition of all agents, there
are no preferences left to be private. Thus, if the protocol is designed so that a coalition
of up to n 1 agents does not gain any information, collusion becomes pointless (in

order to breach privacy). This will be called “full privacy” in the following.

−

Definition 1 (Full privacy). Aprotocolis fully private 6 if no information about any
agent's preferences can be uncovered, other than what can be inferred from the outcome
and all remaining preferences.

By introducing full privacy, we shift the focus from mechanisms to protocols .These
protocols enable agents to jointly determine the outcome of the mechanism by exchang-
ing messages according to some predefined rules without revealing any information be-
sides the outcome. We say that a protocol fully privately emulates a mechanism. When
relying on computational intractability, any mechanism can be emulated by fully private
protocols.

Proposition 1. Correct mechanism execution can be guaranteed without a center given
that trapdoor permutations exist. Privacy can only be breached by exhaustive compu-
tation. 7

5

As an easy example, consider a single secret bit that is shared by choosing n bits at random so
that the exclusive-or of these n bits yields the original bit. A single share, and even up to n − 1
shares, reveal no information at all about the secret bit.

6

In cryptographic terms, a fully private protocol is ( n− 1)-private, which means that a coalition
of up to n − 1 agents is incapable of breaching privacy.

7

Propositions 1 and 2 are based on modifying the classic results of multiparty computation
[GMW87, BGW88, CCD88] for a setting of full privacy by introducing “weak robustness”.
Due to a very strict security model, the original results rely on a fraction, e.g. , a majority, of
the agents being trusted (see [Bra03b] for more details).