### Paper Menu >>

### Journal Menu >>

J. Software Engineering & Applications, 2010, 3, 709-717 doi:10.4236/jsea.2010.37081 Published Online July 2010 (http://www.SciRP.org/journal/jsea) Copyright © 2010 SciRes. 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. Email: ctang@gzhu.edu.cn 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 Copyright © 2010 SciRes. JSEA 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 Copyright © 2010 SciRes. JSEA 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 ffor {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 Pwith 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 xis 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 xand 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 Copyright © 2010 SciRes. JSEA 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 ,,,21used 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 mdenote 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 PPare 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 Copyright © 2010 SciRes. JSEA 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 xand 2 P has 0,1 n y. 2) Auxiliary input: A boolean circuit C such that for every ,0,1 n xyit 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 xand 2 P has {0,1}n y. Secure Multi-Party Proof and its Applications Copyright © 2010 SciRes. JSEA 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 42nstimes, 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 Copyright © 2010 SciRes. JSEA 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 sindependent 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 xxvia 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 Copyright © 2010 SciRes. JSEA 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 Copyright © 2010 SciRes. JSEA 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. |