# Efficient Secure Multiparty Computation Protocol for Sequencing Problem over Insecure Channel

Authors: Yi Sun; Qiaoyan Wen; Yudong Zhang; Hua Zhang; Zhengping Jin
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

As a powerful tool in solving privacy preserving cooperative problems, secure multiparty computation is more and more popular in electronic bidding, anonymous voting, and online auction. Privacy preserving sequencing problem which is an essential link is regarded as the core issue in these applications. However, due to the difficulties of solving multiparty privacy preserving sequencing problem, related secure protocol is extremely rare. In order to break this deadlock, this paper first presents an efficient secure multiparty computation protocol for the general privacy-preserving sequencing problem based on symmetric homomorphic encryption. The result is of value not only in theory, but also in practice.


---

## Body

## 1. Introduction

Sequencing problem is very common in our daily life, such as ranking according to the scores, queuing by the height. Informally speaking, it is about comparing and sequencing of some numbers. It is easy and convenient to get the result because it cares nothing about privacy in the scenes above. On the contrary, privacy-preserving sequencing problem (PPSP) is always a hard challenge since it requires to conduct secret numbers comparison without knowing the numbers. In this scenario, all participants distrust each other and would not like to leak their own secret information to anyone else. It is an urgent task to be solved for some important applications such as electronic bidding, anonymous voting, and online auction. Naturally, as a powerful tool in solving privacy-preserving cooperative problems, secure multiparty computation (SMC) [1] is the best choice for privacy-preserving sequencing. In fact, the classical Millionaire’s problem [1–3] is the earliest example of introducing secure multiparty computation into the sequencing problem. More specifically, the millionaire’s problem, with the aim to find out which one of the two Millionaires is richer without revealing their net worth, can be described as comparing two secret numbers in the perspective of sequencing, that is, the 2-party case of PPSP. In this aspect, the case of 2-party sequencing problem has already been resolved along with the advent of the solutions to Millionaire’s problem and the presence of other secure two-party computation protocols [4–12]. Due to the limitation of the 2-party case in practice, the general multiparty PPSP becomes the focus in secure multiparty computation recently.In 1962, Held and Karp [13] put forward a dynamic programming approach to multiparty sequencing problem before the advent of SMC. They concern more about some certain scenarios and aim to design schemes for the special applications such as the traveling-salesman problem. Subsequently, the research on PPSP is rare and mainly about the 2-party case. Currently, Tang et al. [14] have constructed an efficient and secure multiparty computation protocol for PPSP by making use of a secret sharing scheme based on polynomial. It is an important fruit of PPSP since it has indeed realized secure sequencing among distrusted participants. However, the cost is too high in choosing random numbers and transmitting messages. In the case of n parties with t adversaries, it needs to choose 2n·(2t+1)+n polynomials and 2n·(t+1) random numbers. What is more, the transmitted messages are up to (2t+1)·(n-1)·n+(n-1)·n+n2(2t+1) every round.This paper applies the fast symmetric homomorphic encryption to replace the cumbersome secret sharing based on polynomial. It no longer needs to choose so many polynomials and random numbers. Relevant complexities in computation and communication also have a great improvement. Our result is not only much simpler but also more efficient. In brief, our contributions can be summarized as follows.(1)
We first introduce symmetric homomorphic encryption to solve the privacy-preserving sequencing problem in secure multiparty computation, which brings less communications and random numbers than the method of secret sharing based on polynomial.(2)
Our protocol is appropriate for the insecure channel which allows external attackers to eavesdrop and can resist at mostt<n/2  adversaries’ corruption supposing that any two neighbor parties do not conspire.(3)
We propose a protocol for the general privacy-preserving sequencing problem, which is suitable for multiple parties to securely determine the order of a given set rather than just two parties such as the simplest sequencing problem-Millionaire’s problem, or a special application such as the traveling-salesman problem.Organization. The rest of this paper is organized as follows. In Section 2, we briefly give some related preliminaries. In Section 3, we present the new efficient secure multiparty computation protocol for privacy-preserving sequencing problem over insecure channel. In Section 4, we analyze the proposed protocol in detail including its correctness and privacy. Furthermore, we show the advantages of our protocol in the two aspects of transmitted messages and random numbers. Finally, we summarize our work of this paper in the last section.


## 2. Preliminaries

### 2.1.  Secure Multiparty Computation

Secure multiparty computation is dedicated to dealing with the problem of privacy-preserving cooperative computation among distrusted participants. It was first introduced by Yao in 1982 [1] by putting forward the famous Millionaire’s problem. Afterwards, SMC has become a research focus in the international cryptographic community, and a mass of research results have been published one after the other [2–12].Generally speaking, SMC is a method to implement cooperative computation with all participants’ private data, ensuring the correctness of the computation as well as not disclosing additional information except the necessary results. Assume that there aren participants P1,P2,…,Pn. Each has a secret, respectively, S1,S2,…,Sn. They want to compute the value of a public function F(·) on n variables at the point (S1,S2,…,Sn), that is, F(S1,S2,…,Sn). An SMC protocol is dubbed secure if no participant can learn more from the description of the public function and the result of the global calculation than what he can learn from his own information.


### 2.2. Homomorphic Encryption

In this subsection, we introduce a basic tool to design our protocol, the symmetric homomorphic encryption scheme. Allowing for security, the participants usually would not like to directly transmit their original data over insecure channel while interacting with others. They expect that other parties can perform necessary computations on the encrypted version of the data. In this way, they can encrypt their own private information and then transmit it to others without exposing the real data and finally decrypt the information sent back by others to get the target result when completing cooperative computation. To meet this demand, Rivest et al. proposed homomorphic encryption in 1978 [15]. His work sparked the research in this field. A lot of articles have been proposed and widely used in many applications since then. However, the most common homomorphic encryption schemes are mainly asymmetric, for example, ELGamal homomorphic encryption scheme and Paillier’ homomorphic encryption scheme.Although symmetric homomorphic encryption has not been used in PPSP, it is really a promising method for secure multiparty computation while dealing with the problem of privacy-preserving sequencing. The symmetry will bring high efficiency to our solution since symmetric encryption possesses the advantage of being really fast and can be used as often as possible. As illustrated in [16], a block cipher like AES is typically 100 times faster than RSA encryption and 2000 times than RSA decryption, with about 60 MB per second on a modest platform. Stream ciphers are even faster, some of them being able to encrypt/decrypt 100 MB per second or more. Therefore, asymmetric homomorphic encryptions are bound to much slower than the symmetric ones. In this paper, we will employ the superior symmetric homomorphic encryption schemes to construct our protocol.Generally, an encryption scheme is said to be homomorphic if for any given encryption keyk, the encryption function E(·) satisfies the following condition:
(1)∀m1,m2∈P,E(m1⊙Pm2)=E(m1)⊙CE(m2),
where P(C) denotes the set of the plaintexts (ciphertexts), and ⊙P and ⊙C are the operators in P and C.We say that a scheme is additively homomorphic if we consider addition operators, and it is multiplicatively homomorphic if we consider multiplication operators. Usually, multiplicative homomorphic encryption functions are more efficient than additive homomorphic encryption functions.Herein, we will use the random symmetric homomorphic encryption functionE(·) in this paper, which satisfies the following property:
(2)∀m1,m2∈Q+,E(m1+m2)=E(m1)*E(m2),
where E(·) is a random function and Q is the set of rational numbers.It is easy to deduce that for allm∈Q+,  r∈Z+,
(3)E(r*m)=E(m)r.


### 2.3. Privacy-Preserving Sequencing Problem

#### 2.3.1. The Original Problem

Privacy-preserving sequencing problem is in fact the more universal description of the generalized secret number comparison. To be more specific, there aren distrusted participants P1,P2,…,Pn. Each of them has a private number, respectively, S1,S2,…,Sn. The problem is that they hope to rank the n-array (S1,S2,…,Sn) without leaking any information about S1,S2,…,Sn. It requires that after executing cooperative computation, P1,P2,…,Pn know the size relations of S1,S2,…,Sn but no more other information. Formally, we can represent the whole problem as shown in Algorithm 1.Algorithm 1
Input: (S1,S2,…,Sn), Si is the private number of Pi;
Output: (l1,l2,…,ln), li is the order of Si in the n-array.


#### 2.3.2. Equivalent Transformation of the Original Problem

In this paper, we make use of a useful theorem in the progressing procedure following reference [14] so that we can reduce the initial sequencing problem about the n-array (S1,S2,…,Sn) to the new n-array (S1′,S2′,…,Sn′), which has the same sequence as (S1,S2,…,Sn) and is called as the pseudoarray of (S1,S2,…,Sn). Then P1,P2,…,Pn can obtain the sequence of S1,S2,…,Sn by directly comparing the pseudoarrays (S1′,S2′,…,Sn′) in public. Along with the equivalent transformation of the problem, the aim of secure multiparty computation needs a corresponding change. It no longer has to consider how to deal with the real data S1,S2,…,Sn but only needs to securely get the pseudodata S1′,S2′,…,Sn′. And then the subsequent work is just a piece of cake.Theorem 1.
Arrays(S1,S2,…,Sn) and (S1′,S2′,…,Sn′) have the same sequence, where Si′=r1*Si+r2*Si2+⋯+rn*Sin, ri≥0, Si≥0, i=1,2,…,n.Proof.
Given for allSi′,Sj′∈(S1′,S2′,…,Sn′)(4)Si′=r1*Si+r2*Si2+⋯+rn*Sin,Sj′=r1*Sj+r2*Sj2+⋯+rn*Sjn.
Then,
(5)Si′-Sj′=(r1*Si+r2*Si2+⋯+rn*Sin)=(r1*Si+r2*Si2+⋯+rn*Sin)-(r1*Sj+r2*Sj2+⋯+rn*Sjn)=r1*(Si-Sj)+r2*(Si2-Sj2)+⋯+rn*(Sin-Sjn)=(Si-Sj)[Sjn-2r1+r2*(Si+Sj)+r3*(Si2+Si·Sj+Sj2)+⋯+rn*(Sin-1+Sin-2·Sj+⋯+Si·Sjn-2+Sjn-1)].
Let
(6)Q=r1+r2*(Si+Sj)+r3*(Si2+Si·Sj+Sj2)+⋯+rn*(Sin-1+Sin-2·Sj+⋯+Si·Sjn-2+Sjn-1).
Then, Si′-Sj′=(Si-Sj)·Q. As we know that ri≥0, Si≥0, i=1,2,…,n. Therefore, Q≥0. That means, for all Si′,Sj′∈(S1′,S2′,…,Sn′), Si′, Sj′ and Si, Sj have the same sequence. Obviously, (S1,S2,…,Sn) and (S1′,S2′,…,Sn′) have the same sequence.


## 2.1.  Secure Multiparty Computation

Secure multiparty computation is dedicated to dealing with the problem of privacy-preserving cooperative computation among distrusted participants. It was first introduced by Yao in 1982 [1] by putting forward the famous Millionaire’s problem. Afterwards, SMC has become a research focus in the international cryptographic community, and a mass of research results have been published one after the other [2–12].Generally speaking, SMC is a method to implement cooperative computation with all participants’ private data, ensuring the correctness of the computation as well as not disclosing additional information except the necessary results. Assume that there aren participants P1,P2,…,Pn. Each has a secret, respectively, S1,S2,…,Sn. They want to compute the value of a public function F(·) on n variables at the point (S1,S2,…,Sn), that is, F(S1,S2,…,Sn). An SMC protocol is dubbed secure if no participant can learn more from the description of the public function and the result of the global calculation than what he can learn from his own information.


## 2.2. Homomorphic Encryption

In this subsection, we introduce a basic tool to design our protocol, the symmetric homomorphic encryption scheme. Allowing for security, the participants usually would not like to directly transmit their original data over insecure channel while interacting with others. They expect that other parties can perform necessary computations on the encrypted version of the data. In this way, they can encrypt their own private information and then transmit it to others without exposing the real data and finally decrypt the information sent back by others to get the target result when completing cooperative computation. To meet this demand, Rivest et al. proposed homomorphic encryption in 1978 [15]. His work sparked the research in this field. A lot of articles have been proposed and widely used in many applications since then. However, the most common homomorphic encryption schemes are mainly asymmetric, for example, ELGamal homomorphic encryption scheme and Paillier’ homomorphic encryption scheme.Although symmetric homomorphic encryption has not been used in PPSP, it is really a promising method for secure multiparty computation while dealing with the problem of privacy-preserving sequencing. The symmetry will bring high efficiency to our solution since symmetric encryption possesses the advantage of being really fast and can be used as often as possible. As illustrated in [16], a block cipher like AES is typically 100 times faster than RSA encryption and 2000 times than RSA decryption, with about 60 MB per second on a modest platform. Stream ciphers are even faster, some of them being able to encrypt/decrypt 100 MB per second or more. Therefore, asymmetric homomorphic encryptions are bound to much slower than the symmetric ones. In this paper, we will employ the superior symmetric homomorphic encryption schemes to construct our protocol.Generally, an encryption scheme is said to be homomorphic if for any given encryption keyk, the encryption function E(·) satisfies the following condition:
(1)∀m1,m2∈P,E(m1⊙Pm2)=E(m1)⊙CE(m2),
where P(C) denotes the set of the plaintexts (ciphertexts), and ⊙P and ⊙C are the operators in P and C.We say that a scheme is additively homomorphic if we consider addition operators, and it is multiplicatively homomorphic if we consider multiplication operators. Usually, multiplicative homomorphic encryption functions are more efficient than additive homomorphic encryption functions.Herein, we will use the random symmetric homomorphic encryption functionE(·) in this paper, which satisfies the following property:
(2)∀m1,m2∈Q+,E(m1+m2)=E(m1)*E(m2),
where E(·) is a random function and Q is the set of rational numbers.It is easy to deduce that for allm∈Q+,  r∈Z+,
(3)E(r*m)=E(m)r.


## 2.3. Privacy-Preserving Sequencing Problem

### 2.3.1. The Original Problem

Privacy-preserving sequencing problem is in fact the more universal description of the generalized secret number comparison. To be more specific, there aren distrusted participants P1,P2,…,Pn. Each of them has a private number, respectively, S1,S2,…,Sn. The problem is that they hope to rank the n-array (S1,S2,…,Sn) without leaking any information about S1,S2,…,Sn. It requires that after executing cooperative computation, P1,P2,…,Pn know the size relations of S1,S2,…,Sn but no more other information. Formally, we can represent the whole problem as shown in Algorithm 1.Algorithm 1
Input: (S1,S2,…,Sn), Si is the private number of Pi;
Output: (l1,l2,…,ln), li is the order of Si in the n-array.


### 2.3.2. Equivalent Transformation of the Original Problem

In this paper, we make use of a useful theorem in the progressing procedure following reference [14] so that we can reduce the initial sequencing problem about the n-array (S1,S2,…,Sn) to the new n-array (S1′,S2′,…,Sn′), which has the same sequence as (S1,S2,…,Sn) and is called as the pseudoarray of (S1,S2,…,Sn). Then P1,P2,…,Pn can obtain the sequence of S1,S2,…,Sn by directly comparing the pseudoarrays (S1′,S2′,…,Sn′) in public. Along with the equivalent transformation of the problem, the aim of secure multiparty computation needs a corresponding change. It no longer has to consider how to deal with the real data S1,S2,…,Sn but only needs to securely get the pseudodata S1′,S2′,…,Sn′. And then the subsequent work is just a piece of cake.Theorem 1.
Arrays(S1,S2,…,Sn) and (S1′,S2′,…,Sn′) have the same sequence, where Si′=r1*Si+r2*Si2+⋯+rn*Sin, ri≥0, Si≥0, i=1,2,…,n.Proof.
Given for allSi′,Sj′∈(S1′,S2′,…,Sn′)(4)Si′=r1*Si+r2*Si2+⋯+rn*Sin,Sj′=r1*Sj+r2*Sj2+⋯+rn*Sjn.
Then,
(5)Si′-Sj′=(r1*Si+r2*Si2+⋯+rn*Sin)=(r1*Si+r2*Si2+⋯+rn*Sin)-(r1*Sj+r2*Sj2+⋯+rn*Sjn)=r1*(Si-Sj)+r2*(Si2-Sj2)+⋯+rn*(Sin-Sjn)=(Si-Sj)[Sjn-2r1+r2*(Si+Sj)+r3*(Si2+Si·Sj+Sj2)+⋯+rn*(Sin-1+Sin-2·Sj+⋯+Si·Sjn-2+Sjn-1)].
Let
(6)Q=r1+r2*(Si+Sj)+r3*(Si2+Si·Sj+Sj2)+⋯+rn*(Sin-1+Sin-2·Sj+⋯+Si·Sjn-2+Sjn-1).
Then, Si′-Sj′=(Si-Sj)·Q. As we know that ri≥0, Si≥0, i=1,2,…,n. Therefore, Q≥0. That means, for all Si′,Sj′∈(S1′,S2′,…,Sn′), Si′, Sj′ and Si, Sj have the same sequence. Obviously, (S1,S2,…,Sn) and (S1′,S2′,…,Sn′) have the same sequence.


## 2.3.1. The Original Problem

Privacy-preserving sequencing problem is in fact the more universal description of the generalized secret number comparison. To be more specific, there aren distrusted participants P1,P2,…,Pn. Each of them has a private number, respectively, S1,S2,…,Sn. The problem is that they hope to rank the n-array (S1,S2,…,Sn) without leaking any information about S1,S2,…,Sn. It requires that after executing cooperative computation, P1,P2,…,Pn know the size relations of S1,S2,…,Sn but no more other information. Formally, we can represent the whole problem as shown in Algorithm 1.Algorithm 1
Input: (S1,S2,…,Sn), Si is the private number of Pi;
Output: (l1,l2,…,ln), li is the order of Si in the n-array.


## 2.3.2. Equivalent Transformation of the Original Problem

In this paper, we make use of a useful theorem in the progressing procedure following reference [14] so that we can reduce the initial sequencing problem about the n-array (S1,S2,…,Sn) to the new n-array (S1′,S2′,…,Sn′), which has the same sequence as (S1,S2,…,Sn) and is called as the pseudoarray of (S1,S2,…,Sn). Then P1,P2,…,Pn can obtain the sequence of S1,S2,…,Sn by directly comparing the pseudoarrays (S1′,S2′,…,Sn′) in public. Along with the equivalent transformation of the problem, the aim of secure multiparty computation needs a corresponding change. It no longer has to consider how to deal with the real data S1,S2,…,Sn but only needs to securely get the pseudodata S1′,S2′,…,Sn′. And then the subsequent work is just a piece of cake.Theorem 1.
Arrays(S1,S2,…,Sn) and (S1′,S2′,…,Sn′) have the same sequence, where Si′=r1*Si+r2*Si2+⋯+rn*Sin, ri≥0, Si≥0, i=1,2,…,n.Proof.
Given for allSi′,Sj′∈(S1′,S2′,…,Sn′)(4)Si′=r1*Si+r2*Si2+⋯+rn*Sin,Sj′=r1*Sj+r2*Sj2+⋯+rn*Sjn.
Then,
(5)Si′-Sj′=(r1*Si+r2*Si2+⋯+rn*Sin)=(r1*Si+r2*Si2+⋯+rn*Sin)-(r1*Sj+r2*Sj2+⋯+rn*Sjn)=r1*(Si-Sj)+r2*(Si2-Sj2)+⋯+rn*(Sin-Sjn)=(Si-Sj)[Sjn-2r1+r2*(Si+Sj)+r3*(Si2+Si·Sj+Sj2)+⋯+rn*(Sin-1+Sin-2·Sj+⋯+Si·Sjn-2+Sjn-1)].
Let
(6)Q=r1+r2*(Si+Sj)+r3*(Si2+Si·Sj+Sj2)+⋯+rn*(Sin-1+Sin-2·Sj+⋯+Si·Sjn-2+Sjn-1).
Then, Si′-Sj′=(Si-Sj)·Q. As we know that ri≥0, Si≥0, i=1,2,…,n. Therefore, Q≥0. That means, for all Si′,Sj′∈(S1′,S2′,…,Sn′), Si′, Sj′ and Si, Sj have the same sequence. Obviously, (S1,S2,…,Sn) and (S1′,S2′,…,Sn′) have the same sequence.


## 3. Proposed Protocol

In this section, we present our protocol. The simplified version of the protocol is briefly illustrated in Figure1, and the details can be described as follows.Figure 1
Simplified version of the proposed protocol.Initialization. Assume that there are n participants P1,P2,…,Pn, each Pi owning a secret number Si and a random symmetric homomorphic encryption function Ei(·).Computation
(1)
P
i chooses a random number ri>0, i=1,2,…,n, and computes Ei(Si),Ei(Si2),…,Ei(Sii-1),Ei(Sii+1),…,Ei(Sin) and Ei(ri*Sii) locally. For i=1,2,…,n, j=1,2,…,n, i≠j, Pi sends Ei(Sij) to Pj.
(2)
After receivingEi(Sij), Pj computes Ei(Sij)rj, i=1,2,…,n, j=1,2,…,n, i≠j. And then, Pj transmits Ei(Sij)rj to Pi+1, i=1,2,…,n-1, j=1,2,…,n,  j≠i+1. For i=n, Pj transfers En(Snj)rj to P1, j=2,…,n.
(3)
P
1 computes Sn′′=En(r1*Sn+r2*Sn2+⋯+rn*Snn) and sends Sn′′ to Pn; For i=1,2,…,n-1, Pi+1 computes Si′′=Ei(r1*Si+r2*Si2+⋯+rn*Sin) and sends Si′′ to Pi.
(4)
P
i computes Si′=Di(Si′′), i=1,2,…,n and broadcasts Si′ to obtain the sequence of the n-array (S1,S2,…,Sn) by comparing the size of the pseudoarray (S1′,S2′,…,Sn′).


## 4. Analysis

In this section, we have an analysis of the proposed protocol in the aspects of security and efficiency. To guarantee that it is a secure multiparty computation protocol, we have to prove that it satisfies correctness and privacy requirements at first.


### 4.1. Correctness

Assume that the attacker is passive. Then, all participants (including all attackers and honest participants) correctly follow the protocol. Therefore, we only need to examine whether the protocol will give the correct sequence for the array(S1,S2,…,Sn). From the proof of Theorem 1, we know that the array  (S1,S2,…,Sn) have the same sequence with the pseudoarray (S1′,S2′,…,Sn′). Thus, the proposed protocol can correctly achieve the aim of sequencing the array (S1,S2,…,Sn) by comparing the pseudoarrays (S1′,S2′,…,Sn′) secretly. Hence, the protocol satisfies correctness.


### 4.2. Privacy

According to the definition of privacy in multiparty computation protocols in [17], the protocol is private if the protocol satisfies the following conditions.(a)
The information string viewed by each participantPi and a random string with the same length have the same probability distribution. That is, the information string and the random string are indistinguishable.(b)
Arbitraryt<n/2 participants cannot jointly obtain any information about the input of any other participant.In fact, in the proposed protocol, the viewed information strings ofPi are Ei(Si),Ei(Si2),…,Ei(Sii-1),Ei(Sii+1),…,Ei(Sin), and Ei(ri*Sii) in the first step; Ei(ri*Sii), Ej(Sji), Ej(Sji)ri, i=1,2,…,n, j=1,2,…,n, i≠j in the second step; Si-1′′,  i=2,…,n, specially, for i=1, the viewed information string in this step is Sn′′ for P1; finally, in the last step, the viewed string is Si′ for Pi. All the strings are generated by the random symmetric homomorphic encryption function Ei(·). Therefore, the strings viewed by Pi and a random string with the same length have the same probability distribution, and (a) is satisfied.Moreover, our protocol also satisfies that arbitraryt<n/2 participants cannot jointly obtain any information about the input of any other participant under the assumption that any two neighbor parties never conspire. Since we have Pi+1 to compute Si′′ for Pi by collecting Ei(Sij)rj,  j=1,…,n, it is obvious that it is insecure if Pi and Pi+1 collude. It is reasonable to suppose that no neighbors collude because the two adversaries are not exactly adjacent since they cannot control the order of the parties when executing the protocol. In addition, if an adversary wants to get more information from Si′′=Ei(r1*Si+r2*Si2+⋯+rn*Sin), he must corrupt with at least n-1 parties since there are n-1 unknown coefficients as well as breaking the encryption scheme E(·).What is more, in our protocol, all information strings are transmitted in the encrypted forms. The private informationSi and ri are secret as long as the encryption function Ei(·) is robust. In other words, it is secure even over the insecure channel, which is better than the previous protocol based on polynomial for the sequencing problem.In short, our protocol is correct and private.


### 4.3. Efficiency

Our protocol is efficient as well as secure. It operates better than the previous one because it is independent of the secret sharing scheme based on complex polynomial. We can make a concrete comparison between the proposed protocol and the previous one on the numbers of random numbers and transmitted messages as in Table1.Table 1
Efficiency comparison.
Item
Our protocol
Tang’s protocol
Random numbers
n
2
n
(
t
+
1
)
Transmitted messages
n
(
2
n
-
1
)
(
2
t
+
1
)
(
n
-
1
)
n
+
(
n
-
1
)
n
+
n
2
(
2
t
+
1
)From Table1, we can easily find that in Tang’ protocol [14], it needs to choose n·(2t+1) polynomials for f(·), n polynomials for r(·), and n·(2t+1) polynomials for h(·), that is, totally 2n·(t+1) random numbers as well as 2n·(2t+1)+n polynomials; it also needs to transmit fik(xj) from Pi to Pj, i,j=1,2,…,n, k=1,2,…,2t+1, ri(xj), hik(xj) from Pi to Pj, i=1,2,…,2t+1, j,k=1,2,…,n; thus, (2t+1)·(n-1)·n+(n-1)·n+n2(2t+1) messages are needed to be transmitted totally.In our protocol, it only needs to choosen random numbers in the whole procedure. And the messages that need to be transmitted are, respectively, Ei(Sij),  i=1,2,…,n,  j=1,2,…,n, i≠j, Ei(Sij)rj, i=1,2,…,n-1,  j=1,2,…,n, j≠i+1, and En(Snj)rj,  j=2,…,n, and Si′′, i=1,2,…,n, totally n·(2n-1) messages. It is much simpler and more appropriate for the clients who expect easier products in practice.If there aret=(n-1)/2 adversaries (the upper bound of the adversaries in Tang’ protocol [14]), the advantages of our protocol are more obvious as shown in Table 2.Table 2
Efficiency comparison.
Item
Our protocol
Tang’ protocol
Random numbers
n
n
(
n
+
1
)
Transmitted messages
n
(
2
n
-
1
)
2
n
3
-
n


## 4.1. Correctness

Assume that the attacker is passive. Then, all participants (including all attackers and honest participants) correctly follow the protocol. Therefore, we only need to examine whether the protocol will give the correct sequence for the array(S1,S2,…,Sn). From the proof of Theorem 1, we know that the array  (S1,S2,…,Sn) have the same sequence with the pseudoarray (S1′,S2′,…,Sn′). Thus, the proposed protocol can correctly achieve the aim of sequencing the array (S1,S2,…,Sn) by comparing the pseudoarrays (S1′,S2′,…,Sn′) secretly. Hence, the protocol satisfies correctness.


## 4.2. Privacy

According to the definition of privacy in multiparty computation protocols in [17], the protocol is private if the protocol satisfies the following conditions.(a)
The information string viewed by each participantPi and a random string with the same length have the same probability distribution. That is, the information string and the random string are indistinguishable.(b)
Arbitraryt<n/2 participants cannot jointly obtain any information about the input of any other participant.In fact, in the proposed protocol, the viewed information strings ofPi are Ei(Si),Ei(Si2),…,Ei(Sii-1),Ei(Sii+1),…,Ei(Sin), and Ei(ri*Sii) in the first step; Ei(ri*Sii), Ej(Sji), Ej(Sji)ri, i=1,2,…,n, j=1,2,…,n, i≠j in the second step; Si-1′′,  i=2,…,n, specially, for i=1, the viewed information string in this step is Sn′′ for P1; finally, in the last step, the viewed string is Si′ for Pi. All the strings are generated by the random symmetric homomorphic encryption function Ei(·). Therefore, the strings viewed by Pi and a random string with the same length have the same probability distribution, and (a) is satisfied.Moreover, our protocol also satisfies that arbitraryt<n/2 participants cannot jointly obtain any information about the input of any other participant under the assumption that any two neighbor parties never conspire. Since we have Pi+1 to compute Si′′ for Pi by collecting Ei(Sij)rj,  j=1,…,n, it is obvious that it is insecure if Pi and Pi+1 collude. It is reasonable to suppose that no neighbors collude because the two adversaries are not exactly adjacent since they cannot control the order of the parties when executing the protocol. In addition, if an adversary wants to get more information from Si′′=Ei(r1*Si+r2*Si2+⋯+rn*Sin), he must corrupt with at least n-1 parties since there are n-1 unknown coefficients as well as breaking the encryption scheme E(·).What is more, in our protocol, all information strings are transmitted in the encrypted forms. The private informationSi and ri are secret as long as the encryption function Ei(·) is robust. In other words, it is secure even over the insecure channel, which is better than the previous protocol based on polynomial for the sequencing problem.In short, our protocol is correct and private.


## 4.3. Efficiency

Our protocol is efficient as well as secure. It operates better than the previous one because it is independent of the secret sharing scheme based on complex polynomial. We can make a concrete comparison between the proposed protocol and the previous one on the numbers of random numbers and transmitted messages as in Table1.Table 1
Efficiency comparison.
Item
Our protocol
Tang’s protocol
Random numbers
n
2
n
(
t
+
1
)
Transmitted messages
n
(
2
n
-
1
)
(
2
t
+
1
)
(
n
-
1
)
n
+
(
n
-
1
)
n
+
n
2
(
2
t
+
1
)From Table1, we can easily find that in Tang’ protocol [14], it needs to choose n·(2t+1) polynomials for f(·), n polynomials for r(·), and n·(2t+1) polynomials for h(·), that is, totally 2n·(t+1) random numbers as well as 2n·(2t+1)+n polynomials; it also needs to transmit fik(xj) from Pi to Pj, i,j=1,2,…,n, k=1,2,…,2t+1, ri(xj), hik(xj) from Pi to Pj, i=1,2,…,2t+1, j,k=1,2,…,n; thus, (2t+1)·(n-1)·n+(n-1)·n+n2(2t+1) messages are needed to be transmitted totally.In our protocol, it only needs to choosen random numbers in the whole procedure. And the messages that need to be transmitted are, respectively, Ei(Sij),  i=1,2,…,n,  j=1,2,…,n, i≠j, Ei(Sij)rj, i=1,2,…,n-1,  j=1,2,…,n, j≠i+1, and En(Snj)rj,  j=2,…,n, and Si′′, i=1,2,…,n, totally n·(2n-1) messages. It is much simpler and more appropriate for the clients who expect easier products in practice.If there aret=(n-1)/2 adversaries (the upper bound of the adversaries in Tang’ protocol [14]), the advantages of our protocol are more obvious as shown in Table 2.Table 2
Efficiency comparison.
Item
Our protocol
Tang’ protocol
Random numbers
n
n
(
n
+
1
)
Transmitted messages
n
(
2
n
-
1
)
2
n
3
-
n


## 5. Conclusion

It is always a difficult problem in the cryptographic field to construct a secure multiparty computation protocol for the privacy-preserving sequencing problem. In the present study, we have successfully designed an efficient secure multiparty computation protocol for sequencing problem over insecure channel based on symmetric homomorphic encryption, which is of great importance to the theory on this topic and of significant value in practice for its high efficiency.



---

*Source: 172718-2013-09-04.xml*