J. Software Engineering & Applications, 2010, 3, 709-717
doi:10.4236/jsea.2010.37081 Published Online July 2010 (http://www.SciRP.org/journal/jsea)
709
Secure Multi-Party Proof and its Applications
Chunming Tang1,2, Shuhong Gao3
1School of Mathematics and Information Sciences, Guangzhou University, Guangzhou, China; 2State Key Laboratory of Information
Security, Chinese Academy of Science, Beijing, China; 3Department of Mathematical Sciences, Clemson University, Clemson, USA.
Received April 30th, 2010; revised May 24th, 2010; accepted June 1st, 2010.
ABSTRACT
We define a new type cryptographical model called secure multi-party proof that allows any
t
players and a verifier
to securely compute a function ),...,( 1t
xxf : each of the players learns nothing about other players’ input and about the
value of f, and the verifier obtains the value of fand it’s validity but learns nothing about the input of any of the
players. It is implemented by a protocol using oblivious transfer and Yao’s scrambled circuit. We prove that our proto-
col is secure if the players and the verifier are semi-honest (i.e. they follow the protocol) and polynomial time bounded.
The main applications of our protocol are for electronic voting and electronic bidding.
Keywords: Multi-Party Proof, Multi-Party Computation, Electronic Voting, Electronic Bidding
1. Introduction
1.1 Secure Multi-Party Computation and its
Disadvantage
In a secure multi-party computation, a set of n par-
ties with private inputs wish to jointly and securely
compute a function that depends on the individual in-
puts of the parties. This computation should be such
that each party receives its correct output (correctness),
and none of the parties learn anything beyond their
prescribed output (privacy). For example, in an election
protocol, correctness ensures that no coalition of par-
ties can influence the outcome of the election beyond
just voting outcome for their preferred candidate, whe-
reas privacy ensures that no parties learn anything
about the individual votes of other parties. Secure mul-
ti-party computation can be viewed as the task of car-
rying out a distributed computation, while protecting
honest parties from the malicious manipulation of dis-
honest (or corrupted) parties.
In all secure multi-party computation, only partici-
pants obtain information about the value of the func-
tion
f
computed. In some applications, some party
say an arbiter, other than the participants, may want to
know the function value and needs to be sure of its
validity, yet the arbiter learns nothing about the secret
inputs of the participants. Here’s a possible scenario.
Assume a company needs to appoint a new manager for
a department. The administrators of the company hope
that the manager is elected by the staff in this depart-
ment only. The staff could elect a new manager by us-
ing an electronic voting protocol from a secure multi-
party computation. However, these administrators are
usually not in this department, hence they may not be
convinced that the election result is valid.
Another main application of secure multi-party com-
putation is the design of electronic bidding protocols.
Usually, all participants jointly run a secure multi-party
computation protocol and decide the winner; as a result,
only all participants know who the winner is. However,
the sponsor in any electronic bidding is not a partici-
pant; hence the sponsor may not be sure about the
winner. Also, in some time the participants may not be
allowed to know the winner, as the winner wants to be
kept anonymous.
1.2 Our Contributions
We define a new type cryptographical model called se-
cure multi-party proof that allows any t players and a
verifier to securely compute a function 1 ( ,...,)
t
f
xx. The
model requires the following properties: each of the
players learns nothing about other players’ input and nor
any information about the value of
f
, and the verifier
obtains the value of
f
and it’s validity but learns noth-
ing about the input of any of the players. We implement
this model by a protocol using oblivious transfer and

Secure Multi-Party Proof and its Applications 710
Yao’s scrambled circuit. We prove that our protocol is
secure if the players and the verifier are semi-honest (i.e.
they follow the protocol) and polynomial time bounded.
Based on our secure multi-party proof, our protocol can
be used for electronic voting and electronic bidding.
1.3 Related Work
A great deal of work has been done about secure mul-
ti-party computation. Secure computation for two parties
was first formulated by Yao [1] in 1982. In [2,3], Lindell
and Pinkas gave a complete and explicit proof of Yao’s
protocol for secure two-party computation. Goldreich,
Micali and Wigderson [4] showed how to securely com-
pute any multivariate function (even if malicious adver-
saries are present); see [5] for complete proof of their
results. Ben-Or, Goldwasser and Wigderson [6] (and,
independently, Chaum, Crepeau and Damgard [7]) study
secure multiparty computation in the secure channels
setting. They show that: 1) If the adversary is eavesdrop-
ping then there exist

21
n


 -secure protocols for
computing any function. 2) If the adversary is Byzantine,
then any function can be

31
n


 -securely computed.
Furthermore, they show that these bounds on the number
of corruptions are tight. These protocols can be shown
secure in the presence of non-adaptive adversaries.
Adaptive security (i.e., security in the presence of adap-
tive adversaries) is provable in certain variants of this
setting.
Goldwasser and Levin [8] study the case of Byzantine
adversaries where a majority of the parties may be cor-
rupted. Chor and Kushilevitz [9] deal with secure multi-
party computation with majority of the parties corrupted
in the secure channels setting. Goldreich, Goldwasser
and Linial [10] study secure multiparty computation in
the presence of insecure channels and computationally
unlimited adversaries. Ostrovsky and Yung [11] study
secure multiparty computation in the presence of secure
channels and mobile adversaries. Micali and Rogaway
[12], and also Beaver [13], propose definitions for secure
multiparty computation in the secure channels setting in
the presence of adaptive adversaries. Other types of se-
cure multi-party computation include adaptively secure
multi-party computation [14], almost-everywhere secure
computation [15], concurrent secure multi-party compu-
tation [16], and fair multi-party computation [17-19] and
so on.
1.4 Organization
The paper is organized as follows. We start with some
basic definitions and tools in Section 2. Section 3 gives a
formal model of secure multi-party proof. Section 4 con-
structs a secure multi-party proof for any polynomial-
time computable function if all participants are semi-
honest. Section 5 provides a general method to construct
a protocol that can be used for electronic voting and
electronic bidding. Finally, Section 6 outlines concluding
remarks and future directions.
2. Preliminary and Basic Tools
Let n denote a positive integer. We say that a function
()n

is negligible in n (or just negligible) if, for
every polynomial()pn , we have ()1/ ()npn

 for all
sufficiently largen. Let S be an infinite set and the
size of an element
s
S

is denoted by
s
. Suppose
{}
s
sS
XX


and {}
s
sS
YY


are two ensembles of
random distributions (or random variables). We say that
X
and Y are computationally indistinguishable if, for
every non-uniform polynomial-time distinguisherD, the
absolute difference Pr(()1) Pr( ( )1)
ss
DX DY is
negligible in
s
(for
s
S

). For a probabilistic ma-
chine
M
, we denote by ()
M
x the output of
M
when
the input is
x
. The value ()
M
x is a probabilistic dis-
tribution, as it depends on some random values from an
internal random tape used by the machine.
Semi-honest Adversaries vs. Malicious Adversaries.
Loosely speaking, the aim of a secure multi-party proto-
col is to protect honest parties against dishonest behav-
iors by some other parties. Usually, adversaries are di-
vided into semi-honest and malicious adversaries.
A semi-honest adversary controls one of the parties
and follows the protocol specification exactly. However,
it may try to learn more information than allowed by the
protocol via analyzing the transcript of messages re-
ceived.
A malicious adversary may arbitrarily deviate from the
specified protocol. When considering malicious adver-
saries, there are certain undesirable actions that cannot be
prevented. Specifically, a party may refuse to participate
in the protocol or substitute its local input (and use in-
stead a different input). The adversary may also abort the
protocol prematurely so that the adversary may obtain its
output while the honest party does not.
In this paper, we assume that all parties or adversaries
are semi-honest.
Special Symmetric Encryption. In [2], a special
symmetric encryption scheme was constructed that has
indistinguishable encryption for multiple messages. This
means that for any two messages
x
and
y
, no polyno-
mial-time adversary can distinguish an encryption of
x
from that of
y
.
Definition 1 Let (,, )GED be a symmetric encryp-
tion scheme and let the range of a key k denoted by
() {():{0,1}}
n
nk
RkEx x.

Secure Multi-Party Proof and its Applications 711
1) We say that (,, )GED has an elusive range if, for
every probabilistic polynomial-time machine
M
and
for every polynomial()pn , we have
Pr(( )( ))1/( )
n
M
kRk pn
for sufficiently large n, where k is a random binary
string of length n.
2) We say that (,, )GED has an efficiently verifiable
range if there exists a probabilistic polynomial time ma-
chine
M
such that (1 ,,)1
n
Mkc if and only if
()
n
cRk.
By convention, for every ()
n
cRk, we let
()
k
Dc .
In [2], Y. Lindell and B. Pinkas give a simple con-
struction of a special symmetric encryption scheme. Let
{}
k
F
f be a family of pseudorandom functions [11],
where 2 :(0,1} {0,1}
nn
k
ffor {0,1}n k. Then define
() (,()0)
n
kk
Exrfr x
where {0,1}n
x, {0,1}n
R
r and 0n
x
denotes the con-
catenation of
x
and 0n.
Oblivious Transfer. We will briefly describe the ob-
livious transfer protocol of [20]. This protocol is secure
in the presence of semi-honest adversaries. Our descrip-
tion will be for the case that 01
,{0,1}xx; when consid-
ering semi-honest adversaries, the general case can be
obtained by running the single-bit protocol many times in
parallel. It is assumed that there is a family of permuta-
tions with trapdoors, so the permutations are one-way
functions if the trapdoors are not given. Furthermore,
()Bx is a hardcore bit of the one-way functions, so
computing ()Bx is equivalent to inverting the one-way
functions (without using the trapdoors).
Suppose 1
P has two bits 01 ,{0,1}xx and 2 P has
{0,1}

. The goal is for 1 P to transfer
x

to 2 P but
1
P does not know which of the two bits was transferred.
This is called a 1-out-of-2 oblivious transfer.
Oblivious Transfer Protocol
1) 1 P randomly chooses a permutation-trapdoor pair
(,)Et from a family of trapdoor permutations. 1 P
sends E (but not the trapdoor t) to 2 P.
2) 2 P chooses a random


in the domain of E
and computes

f



 . In addition, 2 Pchooses a
random 1


 in the range of E. 2
Psends


01
,


to 1
P.
3) 1
Puses the trapdoort and computes 1
0E




0

and

1
11
E



. Then computes


000
bB x  
and


111
bB x 

, whereBis a hard-core bit of E.
Finally, 1
P sends


01
,bb to2 P.
4) 2
Pcomputes


x
Bb


 , which is the bit
transferred to 2
P by 1 P.
It was proven in [21] that the above protocol is secure
if both of 1
P and 2 P are semi-honest.
3. Definition of Secure Multi-Party Proof
Suppose there aretplayers 12 ,,,
t
PP Pwith secret in-
puts 12 ,,,
t
x
xx, respectively, and a verifier V. We as-
sume that all the players and the verifier are computation-
ally bounded. In addition, assume that

12
,,,
t
f
xx xis
a polynomial-time computable function, so it has a poly-
nomial size circuit.
Definition 2. A multi-party Proof consists of two
sub-protocols:
Computation sub-protocol: It is an ordinary mul-
ti-party computation among the players12
,,,
t
PP P. The
goal is to compute a value for each player, say i m for
i
P for1it

. Each value i mdepends on i xand a
random binary stringi r, both of them are kept secret by
player i P for1it

. Each player does not gain any
information about


12
,,,
t
f
xx xand any information
on other players’ inputs. Then each playeri
Psends se-
cretly i m to V, 1it

.
Proof sub-protocol: In this sub-protocol, the verifier
Vcomputes the value


12
,,,
t
f
xx x from12 ,,,mm
t
m and verifies its validity.
When defining security of multi-party proof, we have
to consider the security of each of the two sub-protocols.
The computation sub-protocol is an ordinary multi-party
computation which allows a set of mutually distrusting
parties to compute a function in a distributed way while
guaranteeing (to the extent possible) the privacy of their
local inputs and the correctness of the outputs. To be
more exact, security is typically formulated by compar-
ing a real execution of the protocol to an ideal execution
where the parties just send their inputs to a trusted party
and receive back their outputs. A real protocol is said to
be secure if an adversary can do no more harm in a real
execution than in an ideal execution (which is secure by
definition). The main security properties that have been
identified, and are implied by this formulation, are pri-
vacy (parties learn nothing more than their own output)
and correctness (the outputs are correctly computed).
In the proof sub-protocol, the verifier Vwill learn
nothing beyond the value of

12
,, t
f
xx x and its va-

Secure Multi-Party Proof and its Applications 712
lidity, that is, Vonly obtains

12
,, t
f
xx x and its
validity. In another word, Vdoes not gain any informa-
tion about 12 ,,,
t
x
xx yet is convinced that the values
of t
x
x
x
,,,21used in computing

12
,,,
t
f
xx x are
the same as claimed, and furthermore, the verifier obtains
the correct function value12
,,,
t
x
xx. This is defined
more formally as follows.
Definition 3 (Security of Multi-Party Proof)
A multi-party proof is secure if it satisfies the follow-
ing properties:
1) Correctness: Suppose each player1
P (fori

1, 2,, t) chooses random binary string i r of length n.
Let 0 y be the final value computed by V from
12
,,,
t
mm m. Then 0 y is equal to

12
,,,
t
f
xx x
with high probability, that is, the probability Pr(0
y


12
,,,
t
f
xx x) is negligible as a function of n.
2) Privacy: For each playeri
P,1it, let i
M
be all
the message thati Pobtains from all other players in the
computation sub-protocol. The protocol is said to have
privacy for all the players if, for each1it, there ex-
ists a bounded probabilistic polynomial time simula-
tor Sisuch thati
M
is indistinguishable from the out-
put

1n
i
S of the simulatorSi.
For the verifier V, let

12
,,,
vt
M
mm mdenote
all the messages received from the players. We say that
the protocol has privacy for Vif there exists a bounded
probabilistic polynomial time simulator v S so that v
M
is indistinguishable with the output


n
v
S1 of the simu-
lator v S.
Also, none of the players learn anything about the
function value computed.
3) Validity: The validity includes the two following
properties:
a) Vcan verify with high probability that the value
i
m is correctly computed from the claimed value of
, 1
i
x
it, all of which are kept secret from V.
b) Vcan verify the correctness of 0 y. Assume the
function
f
is given as a boolean circuit C. Then V
can verify every gate’s computation from the input wires
to the output wires.
4. Construction of Secure Multi-Party Proof
In this section, we will construct a secure multi-party
proof for any polynomial-time computable function

12
,, t
f
xx x if all players1,,
n
PPare semi-honest.
4.1 Two-Party Computation Secure against
Semi-Honest Adversaries
We firstly describe the construction of secure two-party
computation (for semi-honest adversaries) due to Yao [1].
We follow the description by [2,3] where it is proven to
be secure against semi-honest adversaries.
Let Cbe a Boolean circuit that receives two inputs
 
,0,1
n
xy and outputs
  
,0,1
n
Cxy (for simplic-
ity, we assume that the input length, output length and
the security parameter are all n). We also assume that
C has the property that every gate with a circuit-output
wire has no other outgoing wires. We begin by describ-
ing the construction of a single garbled gate g inC.
The circuit C is Boolean, and therefore any gate is rep-
resented by a function


   
: 0,10,10,1g. Let the
two input wires to
g
be labeled 1

and2

.
g
may
have several outgoing wires, but all of them are labeled
by the same symbol3

. Furthermore, let010
112
,,,kkk
101
233
,,kkk be six random keys obtained by independently
invoking the keygeneration algorithm

1n G; for sim-
plicity, assume that these keys are also of length n. In-
tuitively, we wish to be able to compute


,
3
g
k


from
1
k

and 2
k

, without revealing any of the other three
values,

1, ,1
33
,
gg
kk

 
, and

1,1
3
g
k

 . The garbled
gate
g
is defined by the following four values




00
12
0,0
0,0 3
g
kk
cEEg




01
12
0,1
0,13
g
kk
cEEg




10
12
1,0
1,03
g
kk
cEEg




11
12
1,1
1,1 3
g
kk
cEEg
where E is from a private key encryption scheme


,,GED that has indistinguishable encryptions for mul-
tiple messages, and has an elusive efficiently verifiable
range [2,3]. The actual gate is defined by a random per-
mutation of the above values, denoted as 0123
,, ,cccc;
from here on we call them the garbled of gate
g
. Notice
that given 1
k

and 2 k

, and these values 0123 ,, ,cccc, it
is possible to compute the output of the gate
 ,
3
g
k


as
follows. For everyi, computes


1
2i
k k
DDc

. If there
are more than one decryption then returns a non-

value, then output abort. Otherwise, define 3 k

to be the

Secure Multi-Party Proof and its Applications 713
only non- value that is obtained. (Notice that if only a
single non- value is obtained, then this will be

,
3
g
k


because it is encrypted under the given keys
1
k

and 2 k

. Later we will show that except with negli-
gible probability, only one non- value is indeed ob-
tained.)
We are now ready to show how to construct the entire
garbled circuit. Let mbe the number of wires in the
circuit C, and let 1,,
m

  be labels of these wires.
These labels are all chosen uniquely with the following
exception: if i

and
j

are both output wires from the
same gate
g
, thenij

  (this occurs if the fan-out of
g
is greater than one). Likewise, if an input bit enters
more than one gate, then all circuit-input wires associated
with this bit will have the same label. Next, for every
label i

, choose two independent keys


01
,1
n
ii
kk G;
we stress that all of these keys are chosen independently
of the others. Now, given these keys, the four garbled
values of each gate are computed as described above and
the results are permuted randomly. Finally, the output or
decryption tables of the garbled circuit are computed.
These tables simply consist of the values


0
0, i k
and

1
1, i kwhere i

is a circuit-output wire. (Alterna-
tively, output gates can just compute 0 or 1 directly.
That is, in an output gate, one can define
1
,k
cE



 

2
,
k
Eg


for every
 
,0,1  ).
The entire garbled circuit of C, denoted


GC ,
consists of the garbled table for each gate and the output
tables. We note that the structure of C is given, and the
garbled version of C is simply defined by specifying
the output tables and the garbled table that belongs to
each gate. This completes the description of the garbled
circuit.
Let 1,,
n
x
xx and1,,
n
yy y be two n-bit in-
puts for C. Furthermore, let 1,,
n

  be the input
labels corresponding to
x
, and let 12 ,,
nn


be the
input labels corresponding toy. It is shown in [2] that
given the garbled circuit

GC and the strings
11
112
,, ,,,
nn
x
y xy
nn n
kkk k

, it is possible to compute

,Cxy, except with negligible probability. The com-
plete protocol is as followed.
Protocol 1 (Yao’s two-party protocol):
1) Inputs: 1 P has


0,1 n xand 2 P has


0,1 n y.
2) Auxiliary input: A boolean circuit C such that
for every
 
,0,1
n
xyit holds that



,,Cxyf xy,
where :{0,1} {0,1}{0,1}
nn n
f. We require that C is
such that every gate with a circuit-output wire has no
other outgoing wires.
3) The protocol
a) 1
Pconstructs the garbled circuit

GC as de-
scribed in above, and sends it to 2 P.
b) Let 1,,
n

  be the circuit-input wires corre-
sponding to
x
, and let 12 ,,
nn


 be the circuit-input
wires corresponding to y. Then,
.i1 P sends 2 P the strings 1
1,,n
x
x
n
kk.
.ii For every ,i iPand 2 P execute a 1-out-of-2 obli-
vious transfer protocol in which 1
P input equals


01
,
ni ni
kk

 and 2
P’s input equals i y.
The above oblivious transfers can all be run in parallel.
c) Following the above, 2 P has obtained the garbled
circuit and 2n keys corresponding to the 2n input
wires to C. Party 2
P then computes using the garbled
circuit, as described above, obtaining

f
x. 2 P then
sends the value


f
xto 1 P, and they both output this
value.
Assume that the oblivious transfer protocol is secure in
the presence of static semi-honest adversaries, and that
the encryption scheme has indistinguishable encryptions
for multiple messages, and has an elusive and efficiently
verifiable range. Then it is proved in [2] that Protocol 1
securely computes
f
in the presence of static semi-
honest adversaries.
4.2 Secure Multi-Party Proof against
Semi-Honest Adversaries
In this section, we will construct multi-party proof secure
against semi-honest adversaries for any polynomial time
computable function. We firstly construct a secure mul-
ti-party proof between two parties, then generalize it to a
secure multi-party proof for more than two participants.
4.2.1 Secure Two-Party Proof against Semi-Honest
Adversaries
Assume


f
x is a polynomial computable function, so
there exists a polynomial size boolean circuit C such
that for every ,{0,1}
n
xy it holds that


,Cxy



,
f
xy . Both


,
f
xy and Care public. We claim
that the following protocol is a secure two-party proof for
f
.
Protocol 2:
1) Input: 1 P has {0,1}n xand 2 P has {0,1}n y.

Secure Multi-Party Proof and its Applications 714
2) Set-up:
a) Let 1,,
n

 be the circuit-input wires corre-
sponding to
x
, and let 12 ,,
nn


 be the circuit-input
wires corresponding to y. Let s be the number of gates
in C excluding its circuit-input gates and circuit-output
gates
b) By running key generating algorithmG for
42nstimes, 1 Pgenerates 42ns independent
strings
01010101
1122212122
,,,,,,,,,,
nnn nnsns
kkkkk kkk
 

then constructs a garbled computation table for every
gate by using the special symmetric encryption described
in Section 2, and obtains a garbled circuit

GC which
consists of the garbled table for each gate and the output
tables. Finally, 1
P publicizes


GC , and keeps 0
1,k
101
122
,, ,
nsns
kkk

 secret.
3) Computation Sub-protocol:
a) For every 1
1, inP and 2 Pexecute a 1-out-of-2
oblivious transfer protocol in which ,
1
Ps input equals

01
,
ni ni
kk

and ,
2
Ps
input equalsi y.
b) The above oblivious transfers can be run by using
the oblivious transfer protocol in Section 2 and can be
done in parallel.
c) 1 P sends V the strings 1
1,,n
x
x
n
kk.
d) 2
P sends V the strings 1
12
,,n
y y
nn
kk
.
4) Proof Sub-protocol:
Vhas obtained the garbled circuit


GC and 2n
keys corresponding to the 2n input wires to C. V
then computes and obtains


,
f
xy via

GC .
Proof: Correctness. It is correct by the design of the
garbled circuit.
Privacy. Assume that 1 P constructs the garbled cir-
cuit

GC for boolean circuit C. According to the obli-
vious transfer protocol in Section 2, all messages 1 P
obtains are
 


11 12212212
,,,,,,
nn
   from
n1-out-of-2 oblivious transfer protocols between 1 P
and 2
P. In the transfer protocol, every ij

is chosen at
random. The simulator
M
for 1 P is just a pseudoran-
dom generator, see for example [12,16]. Let


1n Mde-
notes the output of
M
which has length


2ij nk k

.
Then

11 122122
(,, ,,,   

12
,)
nn
 and


1n M
is computational indistinguishable. That is, privacy for
1
P is satisfied.
Now we consider privacy for 2
P. All messages2 P
obtains are




111122 2122
(,,,,,,,EbbE bb

12
,, ),
nn n
Eb b
where i E is a permutation-trapdoor and pair


12
,
ii
bb
is random for 1, 2,,in

. Hence, privacy for 2 P is
satisfied by using a pseudorandom generator as a simu-
lator.
The privacy for both 1 P and 2 P implies that 1 P
and 2
P do not obtain any information on the other
player’s input.
Next we consider privacy forV in computation
sub-protocol. All messages V obtains are garbled cir-
cuit


12
12
,,,,
n
x
xx
n
GC kkk from1 P, and2
1
2
1,,,
n
y
y
n
kk


2
n
y
n
k from 2 P. The symmetric encryption algorithm used
in


GC is the special symmetric encryption scheme in
Section 2. Because the output of the symmetric encryp-
tion algorithm is random and both 12
12
,,,
n
x
xx
n
kk k and
12
12 2
,,,
n
y yy
nn n
kkk

 are random, privacy for V is satisfied
by using a pseudorandom generator as a simulator.
Finally, each player learns nothing about the function
value computed by V, since the player know nothing
about what other players send to the verifier.
Validity. Because all participants are semi-honest, the
validity of all the value i m computed by i P from i
x
holds automatically. To see the correctness of the value


,
f
xy , note that Vobtains

GC and12
12
,,,
xx
kk
n
x
n
k from 1 P, and 12
12 2
,,,
n
y yy
nn n
kkk

 from 2 P. Hence,
according to properties of special symmetric encryption,
he can compute


,
f
xy and verifies its validity by veri-
fying every gate’s computation from the circuit-input
wires to circuit-output wires.
4.2.2 Secure Multi-Party Proof against Semi-Honest
Adversaries
In this section, we will generalize two-party proof to
multi-party proof. Assume

1,, t
f
xx is a polynomial
time computable function so there exists a boolean cir-
cuit C of polynomial size such that, for every 1,,x
{0,1}n
t
x, it holds that



11
,, ,,
tt
Cx xfxx.
Both


1,, t
f
xx and C are made public.
Protocol 3:
1) Inputs: i P has {0,1}n
i
x for 1,2,,.it
2) Set-up:
a) Let 12 ,,,
ii in

  be the circuit-input wires cor-
responding toi
x
for 1, 2,,.it

 Let s denote the

Secure Multi-Party Proof and its Applications 715
number of gates in the circuitC excluding its circuit-
input gates and circuit-output gates.
b) By running key generating algorithm G for
22tn s times, 1 P generates 22tn sindependent
strings 010 101
11
,,,,,,,
tntntn stn s
kkkkk k


 constructs a garbled
computation table for every gate by using special sym-
metric encryption in Section 2, and obtains a garbled
circuit

GC which consists of the garbled table for
each gate and the output tables. Finally, 1 P publicizes

GC , and keeps 010 1
11
,,,,,
tn tn
kk kk 01 ,,
tn stn s
kk

 se-
cret.
3) Computation Sub-protocol：
a) For every

2,, ,it 1 P and i P execute a
1-out-of-2 oblivious transfer protocol in which,
1
Ps input
equals

01
,
ij ij
kk and ,
i
Ps input equalsij
x
, forj

1, 2,,.n
b) The above oblivious transfers can be run by using
the oblivious transfer protocol in Section 2 and can be
done in parallel.
c) i P sends V the strings 1
1,,
iin
x
x
iin
kk fori

1, 2,, t.
4) Proof Sub-protocol:
Vhas obtained the garbled circuit

GC and tn
keys corresponding to the tn input wires to C. V
computes and obtains

1., t
f
xxvia

GC .
Proof: Correctness. It follows from the design of the
protocol.
Privacy. Assume that 1 P constructs the garbled cir-
cuit

GC for boolean circuit C. Then, according to the
oblivious transfer protocol in Section 2, all the messages
1
P sees are

11 122122
(,, ,,
ii ii
 

12
,)
ii
nn
 from
n 1-out-of-2 oblivious transfer protocols between 1 P
and

2, ,
i
Pi t. By the design of the oblivious
transfer protocol, every


2,,,1, 2,,
i
jk itj n
  is
random. The simulator
M
for 1 P is just a pseudoran-
dom generator, say the one constructed in [12,16]. Let

1n M denote the output of
M
, whose output length
is



21 i
ij
tnkk

.
Then
 

 
22 2222
11 12212212
,,,,,, ,
nn
  ,


11,
t

 


1221 2212
,, ,,,
ttt tt
nn
  and

1n M is compu-
tational indistinguishable. That is, privacy for1
Pis satis-
fied.
We consider privacy for every

2, ,
i
Pi t. All
messages i P obtains are



11112
,,,
ii i
Eb b

22122
,, ,,
ii i
Eb b

 
12
,,
iii
nn n
Eb b, where each i
j
Eis a permutation-trapdoor
and the pair


12
,
ii
jj
bb is random for 1, 2,,jn.
Hence, privacy for i P is satisfied by using a pseudo-
random generator as a simulator.
The privacy for all12 ,,,
t
PP P implies that every i P
obtains no information on other players input during the
computation sub-protocol.
Now we consider privacy forVin computation
sub-protocol. All messages V obtains are garbled cir-
cuit


GC and 1
11 12
11 121
,,,
n
x
xx
n
kk k from1 P, and
12
12
,,,
ii in
x
xx
ii in
kk k from , 2,,
i
Pi t. The symmetric
encryption algorithm used in

GC is the special sym-
metric encryption scheme in Section 2. Because output of
the symmetric encryption algorithm is random and every

1, 2,,,1, 2,,
ij
x
ij
ki tjn is random, privacy for
V is satisfied by using a pseudorandom generator as a
simulator.
Finally, each player learns nothing about the function
value computed by V, since the player know nothing
about what other players send to the verifier.
Validity. Because all participants are semi-honest, part
(a) of the validity holds automatically. For part (b) of the
validity, Vobtains


GC and 1
11 12
11 121
,,,
n
x
xx
n
kk k from
1
P, and gains 12
12
,,,
ii in
x
xx
ii in
kk k from , 2,,
i
Pi t

.
Hence, according to the properties of the special sym-
metric encryption, V can compute

12
,,,
t
f
xx x and
verifies its validity by verifying every gate’s computation
from the circuit-input wires to circuit-output wires.
5. Electronic Protocols Based on Secure
Multi-Party Proof
Protocol 3 can be used in many applications where the
verifier has no influence on the functions to be computed,
yet he/she wants to learn the function values, however,
Protocols 1 and 2 cannot be used because there are only
two participants. The arbitrator is assured of the correct-
ness and validity of the function value computed. Two
important applications we have in mind are electronic
voting and electronic bidding.
Assume


1,, t
f
xx is a polynomial time comput-
able function used in an application.
For electronic voting, the function is a sum:


121 2
,,,
tt
f
xxxx xx

 the total count for
votes of a candidate. For electronic bidding, we may

Secure Multi-Party Proof and its Applications 716
have

12 12
,,, max{,,,}
tt
f
xx xxx x where i x is
the bid from , 1
i
Pit. For these functions there is
polynomial sized circuit C for computing them. Both
the function

1,, t
f
xx and its circuit C are public
information. Then our Protocol 3 above can be applied to
both of these cases, and it is secure if the participants and
the verifier are semi-honest.
6. Conclusions
We defined a new type cryptographical model called
secure multi-party proof that allows any t players and a
verifier to securely compute a function with t variables.
We presented a protocol that is secure when all the par-
ticipants and the verifier are semi-honest. Our protocol
can be used for electronic voting and electronic bidding.
The main difference between multi-party computation
and multi-party proof is that, in the former case only par-
ticipants know the output or partial output, while in the
later case only a designated verifier learns the final out-
put. The latter is more practicable in some important sit-
uations, for example, in an electronic bidding, where an
arbiter is only a verifier but not a participant.
It should be noted, however, that our protocol is not
secure against malicious adversaries.
Based on non-interactive zero-knowledge proof, it is
possible to construct secure multi-party proof against
malicious adversaries. However, these protocols are inef-
ficient because of complexity of zero-knowledge proof.
In future work, we intend to construct secure multi-party
proof for any polynomial-time computable function

12
,,,
t
f
xx x from tools other than zero-knowledge
proof.
7. Acknowledgements
This work was supported by Foundation of National
Natural Science (China) (10871222) and Opening Foun-
dation of Key Lab of Cryptological Technology and In-
formation Security Ministry of Education in Shandong
University.
REFERENCES
[1] A. Yao, “Protocols for Secure Computation,” Proceed-
ings of the 23rd Annual Symposium on Foundations of
Computer Science, Chicago, November 1982, pp. 160-
164.
[2] Y. Lindell and B. Pinkas, “A Proof of Yao’s Protocol for
Secure Two-Party Computation,” Journal of Cryptology,
Vol. 22, No. 2, April 2009, pp. 161-188.
[3] Y. Lindell and B. Pinkas, “An Efficient Protocol for Se-
cure Two-Party Computation in the Presence of Mali-
cious Adversaries,” Advances in Cryptology-Eurocrypt
2007, LNCS 4515, Barcelona, May 2007, pp. 52-78.
[4] O. Goldreich, S. Micali and A. Wigderson, “How to Play
Any Mental Game—A Completeness Theorem for Pro-
tocols with Honest Majority,” Proceedings of the 19th
Annual ACM Symposium on Theory of Computing, New
York, 1987, pp. 218-229.
[5] O. Goldreich, “Foundations of Cryptography: Volumne
2—Basic Applications,” Cambridge University Press,
2004.
[6] M. Ben-Or, S. Goldwasser and A. Wigderson, “Com-
pleteness Theorems for Non-Cryptographic Fault-Toler-
ant Distributed Computation,” Proceedings of the 20th
Annual ACM Symposium on Theory of Computing, Chi-
cago, 1988, pp. 1-10.
[7] D. Chaum, C. Crepeau and I. Damgard, “Multiparty Un-
conditionally Secure Protocols,” Proceedings of the 20th
Annual ACM Symposium on Theory of Computing, Chi-
cago, 1988, pp. 11-19.
[8] S. Goldwasser and L. Levin, “Fair Computation of Gen-
eral Functions in Presence of Immoral Majority,” Ad-
vances of Cryptology-Crypto’90, LNCS 537, Santa Bar-
bara, California, August 1990, pp. 77-93.
[9] B. Chor and E. Kushilevitz, “A Zero-One Law for Boo-
lean Privacy,” SIAM Journal on Discrete Mathematics,
Vol. 4, No. 1, February 1991, pp. 36-47.
[10] O. Goldreich, S. Goldwasser and N. Linial, “Fault-Tol-
erant Computation in the Full Information Model,” SIAM
Journal on Computing, Vol. 27, No. 2, 1991, pp. 506-
544.
[11] R. Ostrovsky and M. Yung, “How to Withstand Mobile
Virus Attacks,” Proceedings of the 10th Annual ACM
Symposium on Principles of Distributed Computing,
Montreal, August 1991, pp. 51-59.
[12] S. Micali and P. Rogaway, “Secure Computation,” Ad-
vances of Cryptology-Crypto’91, LNCS 576, Santa Bar-
bara, California, August 1991, pp. 392-404.
[13] D. Beaver, “Foundations of Secure Interactive Comput-
ing,” Advances of Cryptology-Crypto’91, LNCS 576,
Santa Barbara, California, August 1991, pp. 377-391.
[14] R. Canetti, U. Feige, O. Goldreich and M. Naor, “Adap-
tively Secure Multi-Party Computation,” Proceedings of
the 28th Annual ACM Symposium on Theory of Comput-
ing, Philadelphia, 1996, pp. 639-648.
[15] J. A. Garay and R. Ostrovsky, “Almost-Everywhere Se-
cure Computation,” Advances of Cryptology-Eurocrypt
2008, LNCS 4965, Istanbul, April 2008, pp. 307-323.
[16] R. Pass, “Bounded-Concurrent Secure Multi-Party Com-
putation with a Dishonest Majority,” Proceedings of the
36th Annual ACM Symposium on Theory of Computing,
Chicago, 2004, pp. 232-241.
[17] C. Cachin and J. Camenisch, “Optimistic Fair Secure
Computation,” Advances of Cryptology-Crypto’00, LNCS
1880, Santa Barbara, California, August 2000, pp. 93-
111.
[18] S. D. Gordon, C. Hazay, J. Katz and Y. Lindell, “Com-
plete Fairness in Secure Two-Party Computation,” Pro-
ceedings of the 40th Annual ACM Symposium on Theory

Secure Multi-Party Proof and its Applications 717
of Computing, Victoria, 2008, pp. 413-422.
[19] B. Pinkas, “Fair Secure Two-Party Computation,” Ad-
vance in Cryptology-Eurocrypt 2003, LNCS 2656, War-
saw, May 2003, pp. 87-106.
[20] S. Even, O. Goldreich and A. Lempel, “A Randomized
Protocol for Signing Contracts,” Communications of the
ACM, Vol. 28, No. 6, 1985, pp. 637-647.
[21] O. Goldreich, S. Goldwasser and S. Micali, “How to
Construct Random Functions,” Journal of the ACM, Vol.
33, No. 4, 1986, pp. 792-807.
[22] O. Goldreich, H. Krawcyzk and M. Luby, “On the Exis-
tence of Pseudorandom Generators,” SIAM Journal on
Computing, Vol. 22, No. 6, 1993, pp. 1163-1175.
[23] J. Hastad, R. Impagliazzo, L. A. Levin and M. Luby,
“Construction of a Psedorandom Generator from Any
One-Way Function,” SIAM Journal on Computing, Vol.
28, No. 4, 1999, pp. 1364-1396.