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

authenticated means of communication between two parties that are unconditionally
secure without relying on any computational assumption. Quantum channels, for ex-
ample, would meet this definition.
It has turned out that the existence of almost all cryptographic primitives can be re-
duced to the existence of certain notions of one-way functions. A one-way function
is a function that can be evaluated efficiently (in polynomial time), but there is no
polynomial-time algorithm that can invert the function more accurately than guessing
at random. A one-way permutation is a one-way function that is a bijective mapping
of a domain onto itself. A trapdoor permutation is a one-way permutation that, given
some extra information (the trapdoor), can be inverted in polynomial time. To give two
examples, it has been shown that secure digital signatures exist if (and only if) there
are one-way functions. Secure public-key encryption, on the other hand, is known to be
feasible if trapdoor permutations exist.
The actual existence of one-way functions would imply .However,the

reverse is not true: Although it might be hard to invert a function in the worst-case ,it
can be easy in many practical instances or even in the average-case . This uncertainty
plus the technological assumptions one has to rely on—even when one-way functions
exist—motivate the exploration of security that is based on alternative models such as
in unconditionally secure multiparty computation [BGW88, CCD88].
The approach of the subsequent sections is as follows. We believe correctness to be
fundamentally important and thus only consider models that guarantee correctness. On
top of that, we investigate which sets of assumptions are necessary to provide differing
degrees of privacy, e.g. , privacy that relies on a trusted center or privacy that relies
on computational intractability. The proofs in the following sections will make use of
cryptographic primitives such as commitment schemes , (computational) zero-knowledge
proofs ,and perfect zero-knowledge arguments 2 . We refer to cryptographic textbooks
( e.g. , [Gol01]) for definitions of these building blocks.

P = NP

3.1 Centralized Mechanism Execution

Let us first start by trying to obtain a provably correct single center without caring for
privacy. It might seem to be sufficient to provide private channels, e.g. , based on public-
key cryptography, from each agent to the center in order to transmit the preferences and
a signature scheme that allows agents to sign their submissions. The center would then
be able to prove the correctness of the outcome by just broadcasting all signed prefer-
ences. However, the center could collude with an agent and make him sign and send
preferences that the center chooses after having seen preferences that were submitted
earlier. 3 For this reason, publishing a so-called commitment to one's preferences prior
to submitting the preferences becomes inevitable. By applying zero-knowledge proofs

2

Perfect zero-knowledge arguments are a variant of zero-knowledge proofs in which there is no
information revelation even to computationally unbounded adversaries, but computationally
unbounded agents can produce “forged” proofs.

3

Even if communication from the center to any agent could be prohibited, a manipulated agent
would be able to send various signed messages. The center could then choose the appropriate
one after it has seen all other preferences.