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

to the commitment values, we essentially get computational privacy for free, i.e. , with-
out having to make further assumptions.

Theorem 1. Correct deterministic mechanism execution can be guaranteed given that
trapdoor permutations exist. Privacy can be breached by the center or exhaustive com-
putation.

Proof. Agents broadcast unconditionally binding commitments to preferences. Both
the commitment scheme and the broadcasting can be based on the existence of one-way
functions (and the availability of a signature scheme infrastructure) [LSP82, Nao89]. In
order to prevent an agent from copying somebody else's commitment (and thus his pref-
erences), each agent proves in computational zero-knowledge (which can be based on
one-way functions as well [BOGG + 88]) that he knows how to open the commitment,
i.e. , he proves that he knows what he committed to. These proofs are executed sequen-
tially to avoid the copying of proofs. 4 After all agents have submitted their commit-
ments (this can be publicly verified due to the broadcasting), agents send information
on how to open their commitments to the center using public-key encryption (based
on trapdoor permutations). The center privately opens all preferences and rejects mal-
formed by publicly opening the commitment value (on the broadcast channel). The
center cannot reject preferences illegitimately as the commitment value is uniquely de-
fined. Finally, it privately computes and declares the outcome with an accompanying
proof of correctness in computational zero-knowledge.

In order to obtain privacy that does not rely on intractability, we also consider a model
that is based on somewhat stronger assumptions.

Theorem 2. Correct deterministic mechanism execution can be guaranteed given that
there are private channels from each agent to the center and one-way permutations
exist. Privacy can only be breached by the center.

Proof. Agents broadcast unconditionally hiding commitments to their preferences and
sequentially prove their correctness using perfect zero-knowledge arguments. After
that, agents send information on how to open their commitments to the center on pri-
vate channels. The center then privately opens the preferences and rejects malformed
by publicly opening the corresponding commitment. In the following, it privately com-
putes the outcome and then declares the outcome with an accompanying argument of
correctness in perfect zero-knowledge. All these operations can be based on one-way
permutations.

Zero-knowledge proofs and arguments allow the center to privately send parts of the
outcome to each agent (and prove its correctness), so that a single agent learns only the
part of the outcome that it is required to know. This can be of advantage in auctions so
that only winning bidders learn about the goods they are awarded and the prices they
have to pay while still guaranteeing correctness [Bra03a].

4

There are more efficient, yet less intuitive, ways of achieving the same functionality.