# Efficient Solutions to Two-Party and Multiparty Millionaires’ Problem

Authors: Xin Liu; Shundong Li; XiuBo Chen; Gang Xu; Xiaolin Zhang; Yong Zhou
Journal: Security and Communication Networks
 (2017)

---

## Abstract

The millionaires’ problem is the basis of secure multiparty computation and has many applications. Using a vectorization method and the Paillier encryption scheme, we first propose a secure two-party solution to the millionaires’ problem, which can determinex=y,x<y, or x>y in one execution. Subsequently, using the vectorization and secret splitting methods, we propose an information-theoretically secure protocol to solve the multiparty millionaires’ problem (a.k.a. secure sorting problem), and this protocol can resist collusion attacks. We analyze the accuracy and security of our protocols in the semihonest model and compare the computational and communication complexities between the proposed protocols and the existing ones.


---

## Body

## 1. Introduction

The millionaires’ problem (abstracted as a greater than (GT) problem) was proposed by Yao [1] as follows: two millionaires, Alice and Bob, want to know who has more wealth, but they do not want to disclose their wealth value to each other. The GT problem can be applied to a practical situation: suppose that Alice wants to buy some commodities from Bob online, and she hopes to pay $x at most, while Bob wants to sell the commodities for $y, but neither wants to disclose this price. Therefore, they need to compare x and y privately. If x>y, they will make a bargain; otherwise, they do not waste their time trying to reach an agreement upon price. The GT problem has also been applied to secure multiparty computation (SMC), a focus in the international cryptography community [2]. Goldwasser [3] predicted that SMC will become an integral part of our computing reality in the future because of its rich theory and potential as a powerful tool.Motivated by Goldwasser’s predictions, cryptographic researchers have studied many SMC problems, including private sorting problems [4], private determination of the relationships among sets [5] and geometry [6], private voting problems [7], and private data mining [8]. Goldreich [9] studied theoretical SMC problems and established a simulation paradigm that has been extensively used to evaluate the security of SMC protocols.The GT problem is a foundational component of many SMC protocols [10–15] and should be solved efficiently for many applications. The secure two-party computation of the GT problem can be applied to securely solve the rational interval computation [16], which can further determine the inclusion problems between point and ring, point and infinite region, point and segment, and so on and even can be used to reduce the cost in real commodity transaction. Protocols for the GT problem can be used to determine graphics similarity [17]. SMC protocols of the GT problem were used to solve secure computation of skyline query in mapreduce [18], secure stable matching at scale [19], private large-scale databases [20], association rule mining [21], and so forth. In addition, Bogdanov et al. [22] proposed a tool for cryptographically secure statistical analysis based on a sorting method. Aly and Van Vyve [23] proposed a secure sorting protocol for secure single-commodity multimarket auctions. Blanton and Aguiar [24] applied a sorting protocol to compute multiset operations.Cryptographic researchers have proposed several GT protocols. Yao [1] used garbled circuits for solving the GT problem. Grigoriev and Shpilrain [30] used various laws of classical physics to offer several solutions of Yao’s millionaires’ problem. Chang et al. [31] proposed a pioneering quantum private comparison protocol for some users.Many researchers have proposed GT protocols based on homomorphic encryption schemes. Li and Wang [32] used the Paillier encryption scheme to compare two encoding numbers. Blake and Kolesnikov [25] used the additive homomorphism of the Paillier encryption scheme to construct a two-round GT protocol with the computational cost of (4b+1lg⁡N+6b) modular multiplications, where b is the bit number of the private inputs and N is the modulus of the Paillier encryption scheme. Lin and Tzeng [26] proposed a two-round protocol using the multiplicative homomorphism of the ElGamal encryption scheme, with the computational cost of (5blg⁡N+4b-6) modular multiplications. Cao and Liu [33] improved the Lin-Tzeng solution to Yao’s millionaires problem by having the two participators alternately perform the original Lin-Tzeng protocol twice.In addition, some researchers proposed SMC protocols for the GT problem based on the linear secret sharing method. Nishide and Ohta [29] constructed a simplified bit-decomposition protocol for the GT problem, whose communication cost is 15 rounds. The protocol cannot distinguish x=y from x<y. Damgard et al. [27] proposed a novel technique to convert a polynomial sharing of the secret into a sharing of the bits of inconstant rounds. Its computation complexity is O(llog⁡l) (l is the bit number of the shared value) modular multiplications.Although several protocols have been proposed, their efficiency is not very high and more efficient SMC protocols are desirable. Therefore, this paper proposes two efficient solutions to both the two-party and multiparty GT problems.Our Contributions. (1) Using the vectorization method, we encode a number into a vector and transform the GT problem into a vector-element-selection problem.(2) Protocol 1 securely solves the two-party GT problem based on the vectorization method and the Paillier encryption scheme. It determinesx=y, x<y, or x>y in one execution. The computational cost is (2s+2lg⁡N) modular multiplications (N is the modulus of the Paillier encryption scheme; s is the encoding vector dimension), and the communication cost is one round. We compare the computational and communication complexities between Protocol 1 and the existing solutions in Section 4.(3) Protocol 2 securely computes the multiparty GT problem (i.e., secure sorting problem) based on the vectorization method and the secret splitting method without any encryption scheme based on computational assumptions. The computational cost is negligible and the communication cost is2n(n-1) rounds (n is the number of parties). It can resist collusion attacks and is information-theoretically secure. We compare the computational and communication complexities between Protocol 2 and the existing solutions in Section 4.Organization. Section 2 introduces related definitions and methods, including the SMC model, the semihonest party, the simulation paradigm, the Paillier encryption scheme, and the vectorization method. Section 3 proposes the two-party and multiparty GT protocols, analyzes the protocols’ accuracy and security, and demonstrates their privacy-preserving properties using the simulation paradigm. Section 4 compares the protocols’ computational and communication complexities with the existing solutions, and Section 5 concludes this work.


## 2. Preliminary

### 2.1. Secure Multiparty Computation Model

#### 2.1.1. Secure Two-Party Computation

A two-party computation is a random computation process, denoted by(1)f:0,1∗×0,1∗⟶0,1∗×0,1∗,where(2)f:x,y⟶f1x,y,f2x,y.


#### 2.1.2. Securen-Party Computation

The above two-party computation can be extended ton-party computation. That is, (3)f:x1,…,xn⟶f1x1,…,xn,…,fnx1,…,xn.


#### 2.1.3. Ideal SMC Model

The ideal SMC model is the most secure SMC model. It needs a trusted third party (TTP), that will always tell the truth and never lies. If such a TTP exists, Alice (holdingx) and Bob (holding y) can privately compute f(x,y) as follows:(1)
Alice sendsx to TTP.(2)
Bob sendsy to TTP.(3)
TTP computesf(x,y)=(f1(x,y),f2(x,y)).(4)
TTP sendsf1(x,y) to Alice and sends f2(x,y) to Bob.Theoretically, this protocol can solve any SMC problem, but the TTP is not easily implemented in practice. Therefore, SMC protocols without needing a TTP must be developed.


### 2.2. Semihonest Party

At present, SMC protocols are investigated either in the semihonest model or in the malicious model. A semihonest party truthfully follows the protocol but may retain all intermediate computation and try to deduce other parties’ private inputs from the record. Studying SMC in the semihonest model is the basis of studying SMC in the malicious model. The semihonest model is not only an important methodology but also provides an appropriate model for many settings. In some settings, proving that a protocol is secure in the semihonest model is sufficient. Furthermore, Goldreich et el. [2] have proven that, given a protocol that privately computes a function f in the semihonest model, a protocol that privately computes the function f in the malicious model can be automatically produced by introducing a bit commitment macro that forces each party to either behave in the semihonest manner or to be detected. Therefore, this work focuses on solutions in the semihonest model.


### 2.3. Simulation Paradigm

A protocol is considered secure if what a party can obtain from the execution of the protocol can also be computed only from his input and output. This situation is formalized by a simulation paradigm [9] in which a party’s view can be simulated by the input and output of the protocol. In this case, the parties cannot learn additional information except the necessary results from the output.The simulation paradigm is a commonly used and widely accepted proof method for secure multiparty computation. The principle of the simulation paradigm is that the security of an SMC protocol is compared to the security of the ideal SMC protocol, and the protocol is secure if it discloses no more information than the ideal SMC protocol does. Therefore, the simulation paradigm is considered as the formal expression of principle to evaluate the security of SMC protocols.


#### 2.3.1. Simulation Paradigm for the Two-Party Case

Suppose thatf=(f1,f2) is a probabilistic polynomial-time function. Alice holds x, and Bob holds y. They want to privately compute f(x,y). π is a protocol that computes f.In the execution ofπ, Alice and Bob obtain message sequences view1π(x,y)=(x,r1,m11,…,mt1) and view2π(x,y)=(y,r2,m12,…,mt2), respectively, where r1(r2) is the result of her (his) internal coin toss and mi1(mi2) is her (his) received message. Their outputs are output1π(x,y) and output2π(x,y).Definition 1 (see [9]).
For a functionf, π privately computes f if there exist probabilistic polynomial-time algorithms S1 and S2 such that(4)S1x,f1x,y,f2x,y≡cview1πx,y,output2πx,y,f1x,y,S2y,f2x,y≡coutput1πx,y,view2πx,y,where ≡c denotes computational indistinguishability.
In order to prove that a multiparty computation protocol is secure, we must construct simulatorsS1 and S2 such that (4) hold.


#### 2.3.2. Simulation Paradigm for then-Party Case

A semihonest party is one that follows the protocol properly, with the exception that it keeps a record of all its intermediate computations. Loosely speaking, a multiparty protocol privately computesf if whatever a set I (or a coalition) of semihonest parties can obtain after participating in the protocol could be essentially obtained from the input and output of these parties. Thus, the only difference between the current definition and the one used in the two-party case is that we consider the gain of a coalition (rather than of a single party) from participating in the protocol [9].Letf:({0,1}∗)m→({0,1}∗)m be an m-ary function, where fi(x1,…,xm) denotes the i-th element of f(x1,…,xm). For I={i1,…,it}⊆[m]=def{1,…,m}, we let fI(x1,…,xm) denote the subsequence fi1(x1,…,xm),…,fit(x1,…,xm). Let Π be an m-party protocol for computing f. The view of the i-th party during an execution of Π on X=(x1,…,xm), denoted by viewiΠ(X), is defined as in Definition 1, and for I={i1,…,it}, we let viewIΠ(X)=def(I,viewi1Π(X),…,viewitΠ(X)).Definition 2 (see [9]).
In casef is a deterministic m-ary function, we say that Π privately computes f if there exists a probabilistic polynomial-time algorithm, denoted by S, such that for every I⊆[m], it holds that (5)SI,xi1,…,xit,fIXX∈0,1∗m≡cviewIΠXX∈0,1∗m.


### 2.4. Paillier Encryption Scheme

The Paillier public-key cryptosystem [34] is probabilistic and has the additive homomorphism. The cryptosystem contains the following three algorithms.KeyGen. This algorithm generates two large primes p,q and sets N=pq. Let λ=lcm⁡(p-1,q-1). The algorithm computes g such that gcd⁡(L(gλmod⁡N2),N)=1, where (6)Lx=x-1N.The public key is(g,N), and the private key is λ.Encryption. To encrypt a plaintext m(m<N), select a random number r(r<N) and compute (7)c=gm·rNmod⁡N2.Decryption. To decrypt the ciphertext c<N2, compute (8)m=Lcλmod⁡N2Lgλmod⁡N2mod⁡N.Additive Homomorphism.Consider the following:(9)Em1·Em2≡gm1·r1Nmod⁡N2gm2·r2Nmod⁡N2=gm1+m2·r1r2Nmod⁡N2≡Em1+m2.


### 2.5. Vectorization Method

We use a vectorization method to solve the GT problem privately. The vectorization method encodes a number into a vector. Suppose thatk∈U={u1,…,us}, k is encoded into an s-dimensional vector V=(v1,…,vs) as follows:(10)vi=α,ui<k,γ,ui=k,β,ui>k.The computational complexity of our protocol depends on|U|. Note that s=U. If U is smaller, no matter how large k is, it can be encoded into a low dimension vector. For example, suppose that k=8388608,α=2,β=3,γ=5 and U={107,1587,357862,8178261,8388608,11587243, 654395824}; then, the vector representation of k is V=(2,2,2,2,5,3,3). The vector dimension is 7, which is much less than the bit number of klog2⁡8388608=23. With this vectorization method and the additive homomorphism of the Paillier encryption scheme, we can easily solve the GT problem.Yao is the pioneer of secure multiparty computation research. In his seminal paper entitled “Protocols for Secure Computations” [1] which introduced the famous millionaire’s problem and further ignited the secure multiparty computation research, he assumed that the numbers to be compared are members of a set U={1,…,10}. Noting that the domain size U is usually small in many practical applications [35], this assumption is reasonable and it does not leak any information.In many cases,U is known to all parties in reality. For example, if some students want to know their score sorting, then U={0,…,100} is known to all parties; if two persons want to compare their ages, then U may be {1,…,120}; if two workers of a company want to compare their wages, U may be {1000,…,100000}, but the wages of a company are often sparsely rather than densely distributed on U. The wages can only be a few scales, and U is small. Therefore, U is known to them and, in all these cases, U does not leak any information about their private data. Generally speaking, all the numbers compared in secure multiparty computation are comparable. If the numbers are comparable, the parties know their range. A common worker will never compare his wages with that of Bill Gates because they are not comparable. But we have to say that though U is known, if U is large, the computational complexity of the protocol will become high, and the protocol therefore becomes impractical.


## 2.1. Secure Multiparty Computation Model

### 2.1.1. Secure Two-Party Computation

A two-party computation is a random computation process, denoted by(1)f:0,1∗×0,1∗⟶0,1∗×0,1∗,where(2)f:x,y⟶f1x,y,f2x,y.


### 2.1.2. Securen-Party Computation

The above two-party computation can be extended ton-party computation. That is, (3)f:x1,…,xn⟶f1x1,…,xn,…,fnx1,…,xn.


### 2.1.3. Ideal SMC Model

The ideal SMC model is the most secure SMC model. It needs a trusted third party (TTP), that will always tell the truth and never lies. If such a TTP exists, Alice (holdingx) and Bob (holding y) can privately compute f(x,y) as follows:(1)
Alice sendsx to TTP.(2)
Bob sendsy to TTP.(3)
TTP computesf(x,y)=(f1(x,y),f2(x,y)).(4)
TTP sendsf1(x,y) to Alice and sends f2(x,y) to Bob.Theoretically, this protocol can solve any SMC problem, but the TTP is not easily implemented in practice. Therefore, SMC protocols without needing a TTP must be developed.


## 2.1.1. Secure Two-Party Computation

A two-party computation is a random computation process, denoted by(1)f:0,1∗×0,1∗⟶0,1∗×0,1∗,where(2)f:x,y⟶f1x,y,f2x,y.


## 2.1.2. Securen-Party Computation

The above two-party computation can be extended ton-party computation. That is, (3)f:x1,…,xn⟶f1x1,…,xn,…,fnx1,…,xn.


## 2.1.3. Ideal SMC Model

The ideal SMC model is the most secure SMC model. It needs a trusted third party (TTP), that will always tell the truth and never lies. If such a TTP exists, Alice (holdingx) and Bob (holding y) can privately compute f(x,y) as follows:(1)
Alice sendsx to TTP.(2)
Bob sendsy to TTP.(3)
TTP computesf(x,y)=(f1(x,y),f2(x,y)).(4)
TTP sendsf1(x,y) to Alice and sends f2(x,y) to Bob.Theoretically, this protocol can solve any SMC problem, but the TTP is not easily implemented in practice. Therefore, SMC protocols without needing a TTP must be developed.


## 2.2. Semihonest Party

At present, SMC protocols are investigated either in the semihonest model or in the malicious model. A semihonest party truthfully follows the protocol but may retain all intermediate computation and try to deduce other parties’ private inputs from the record. Studying SMC in the semihonest model is the basis of studying SMC in the malicious model. The semihonest model is not only an important methodology but also provides an appropriate model for many settings. In some settings, proving that a protocol is secure in the semihonest model is sufficient. Furthermore, Goldreich et el. [2] have proven that, given a protocol that privately computes a function f in the semihonest model, a protocol that privately computes the function f in the malicious model can be automatically produced by introducing a bit commitment macro that forces each party to either behave in the semihonest manner or to be detected. Therefore, this work focuses on solutions in the semihonest model.


## 2.3. Simulation Paradigm

A protocol is considered secure if what a party can obtain from the execution of the protocol can also be computed only from his input and output. This situation is formalized by a simulation paradigm [9] in which a party’s view can be simulated by the input and output of the protocol. In this case, the parties cannot learn additional information except the necessary results from the output.The simulation paradigm is a commonly used and widely accepted proof method for secure multiparty computation. The principle of the simulation paradigm is that the security of an SMC protocol is compared to the security of the ideal SMC protocol, and the protocol is secure if it discloses no more information than the ideal SMC protocol does. Therefore, the simulation paradigm is considered as the formal expression of principle to evaluate the security of SMC protocols.


### 2.3.1. Simulation Paradigm for the Two-Party Case

Suppose thatf=(f1,f2) is a probabilistic polynomial-time function. Alice holds x, and Bob holds y. They want to privately compute f(x,y). π is a protocol that computes f.In the execution ofπ, Alice and Bob obtain message sequences view1π(x,y)=(x,r1,m11,…,mt1) and view2π(x,y)=(y,r2,m12,…,mt2), respectively, where r1(r2) is the result of her (his) internal coin toss and mi1(mi2) is her (his) received message. Their outputs are output1π(x,y) and output2π(x,y).Definition 1 (see [9]).
For a functionf, π privately computes f if there exist probabilistic polynomial-time algorithms S1 and S2 such that(4)S1x,f1x,y,f2x,y≡cview1πx,y,output2πx,y,f1x,y,S2y,f2x,y≡coutput1πx,y,view2πx,y,where ≡c denotes computational indistinguishability.
In order to prove that a multiparty computation protocol is secure, we must construct simulatorsS1 and S2 such that (4) hold.


### 2.3.2. Simulation Paradigm for then-Party Case

A semihonest party is one that follows the protocol properly, with the exception that it keeps a record of all its intermediate computations. Loosely speaking, a multiparty protocol privately computesf if whatever a set I (or a coalition) of semihonest parties can obtain after participating in the protocol could be essentially obtained from the input and output of these parties. Thus, the only difference between the current definition and the one used in the two-party case is that we consider the gain of a coalition (rather than of a single party) from participating in the protocol [9].Letf:({0,1}∗)m→({0,1}∗)m be an m-ary function, where fi(x1,…,xm) denotes the i-th element of f(x1,…,xm). For I={i1,…,it}⊆[m]=def{1,…,m}, we let fI(x1,…,xm) denote the subsequence fi1(x1,…,xm),…,fit(x1,…,xm). Let Π be an m-party protocol for computing f. The view of the i-th party during an execution of Π on X=(x1,…,xm), denoted by viewiΠ(X), is defined as in Definition 1, and for I={i1,…,it}, we let viewIΠ(X)=def(I,viewi1Π(X),…,viewitΠ(X)).Definition 2 (see [9]).
In casef is a deterministic m-ary function, we say that Π privately computes f if there exists a probabilistic polynomial-time algorithm, denoted by S, such that for every I⊆[m], it holds that (5)SI,xi1,…,xit,fIXX∈0,1∗m≡cviewIΠXX∈0,1∗m.


## 2.3.1. Simulation Paradigm for the Two-Party Case

Suppose thatf=(f1,f2) is a probabilistic polynomial-time function. Alice holds x, and Bob holds y. They want to privately compute f(x,y). π is a protocol that computes f.In the execution ofπ, Alice and Bob obtain message sequences view1π(x,y)=(x,r1,m11,…,mt1) and view2π(x,y)=(y,r2,m12,…,mt2), respectively, where r1(r2) is the result of her (his) internal coin toss and mi1(mi2) is her (his) received message. Their outputs are output1π(x,y) and output2π(x,y).Definition 1 (see [9]).
For a functionf, π privately computes f if there exist probabilistic polynomial-time algorithms S1 and S2 such that(4)S1x,f1x,y,f2x,y≡cview1πx,y,output2πx,y,f1x,y,S2y,f2x,y≡coutput1πx,y,view2πx,y,where ≡c denotes computational indistinguishability.
In order to prove that a multiparty computation protocol is secure, we must construct simulatorsS1 and S2 such that (4) hold.


## 2.3.2. Simulation Paradigm for then-Party Case

A semihonest party is one that follows the protocol properly, with the exception that it keeps a record of all its intermediate computations. Loosely speaking, a multiparty protocol privately computesf if whatever a set I (or a coalition) of semihonest parties can obtain after participating in the protocol could be essentially obtained from the input and output of these parties. Thus, the only difference between the current definition and the one used in the two-party case is that we consider the gain of a coalition (rather than of a single party) from participating in the protocol [9].Letf:({0,1}∗)m→({0,1}∗)m be an m-ary function, where fi(x1,…,xm) denotes the i-th element of f(x1,…,xm). For I={i1,…,it}⊆[m]=def{1,…,m}, we let fI(x1,…,xm) denote the subsequence fi1(x1,…,xm),…,fit(x1,…,xm). Let Π be an m-party protocol for computing f. The view of the i-th party during an execution of Π on X=(x1,…,xm), denoted by viewiΠ(X), is defined as in Definition 1, and for I={i1,…,it}, we let viewIΠ(X)=def(I,viewi1Π(X),…,viewitΠ(X)).Definition 2 (see [9]).
In casef is a deterministic m-ary function, we say that Π privately computes f if there exists a probabilistic polynomial-time algorithm, denoted by S, such that for every I⊆[m], it holds that (5)SI,xi1,…,xit,fIXX∈0,1∗m≡cviewIΠXX∈0,1∗m.


## 2.4. Paillier Encryption Scheme

The Paillier public-key cryptosystem [34] is probabilistic and has the additive homomorphism. The cryptosystem contains the following three algorithms.KeyGen. This algorithm generates two large primes p,q and sets N=pq. Let λ=lcm⁡(p-1,q-1). The algorithm computes g such that gcd⁡(L(gλmod⁡N2),N)=1, where (6)Lx=x-1N.The public key is(g,N), and the private key is λ.Encryption. To encrypt a plaintext m(m<N), select a random number r(r<N) and compute (7)c=gm·rNmod⁡N2.Decryption. To decrypt the ciphertext c<N2, compute (8)m=Lcλmod⁡N2Lgλmod⁡N2mod⁡N.Additive Homomorphism.Consider the following:(9)Em1·Em2≡gm1·r1Nmod⁡N2gm2·r2Nmod⁡N2=gm1+m2·r1r2Nmod⁡N2≡Em1+m2.


## 2.5. Vectorization Method

We use a vectorization method to solve the GT problem privately. The vectorization method encodes a number into a vector. Suppose thatk∈U={u1,…,us}, k is encoded into an s-dimensional vector V=(v1,…,vs) as follows:(10)vi=α,ui<k,γ,ui=k,β,ui>k.The computational complexity of our protocol depends on|U|. Note that s=U. If U is smaller, no matter how large k is, it can be encoded into a low dimension vector. For example, suppose that k=8388608,α=2,β=3,γ=5 and U={107,1587,357862,8178261,8388608,11587243, 654395824}; then, the vector representation of k is V=(2,2,2,2,5,3,3). The vector dimension is 7, which is much less than the bit number of klog2⁡8388608=23. With this vectorization method and the additive homomorphism of the Paillier encryption scheme, we can easily solve the GT problem.Yao is the pioneer of secure multiparty computation research. In his seminal paper entitled “Protocols for Secure Computations” [1] which introduced the famous millionaire’s problem and further ignited the secure multiparty computation research, he assumed that the numbers to be compared are members of a set U={1,…,10}. Noting that the domain size U is usually small in many practical applications [35], this assumption is reasonable and it does not leak any information.In many cases,U is known to all parties in reality. For example, if some students want to know their score sorting, then U={0,…,100} is known to all parties; if two persons want to compare their ages, then U may be {1,…,120}; if two workers of a company want to compare their wages, U may be {1000,…,100000}, but the wages of a company are often sparsely rather than densely distributed on U. The wages can only be a few scales, and U is small. Therefore, U is known to them and, in all these cases, U does not leak any information about their private data. Generally speaking, all the numbers compared in secure multiparty computation are comparable. If the numbers are comparable, the parties know their range. A common worker will never compare his wages with that of Bill Gates because they are not comparable. But we have to say that though U is known, if U is large, the computational complexity of the protocol will become high, and the protocol therefore becomes impractical.


## 3. Our Protocols

In this section, we propose protocols to solve secure two-party and multiparty GT problems. In the two-party case, we propose Protocol 1 by using the vectorization method to encode a plaintext number into a vector and using the Paillier encryption scheme to encrypt the vector’s components. Protocol 1 can determine the relationship ofx>y,x<y or x=y in one execution.Although we can expand the two-party GT protocol ton parties, the communication complexity is high, and it will disclose more information. Therefore, we propose Protocol 2 by using the vectorization method and the secret splitting method to solve the multiparty GT problem without using any encryption scheme based on computational assumptions. Protocol 2 can resist collusion attacks and is information-theoretically secure.


### 3.1. Secure Two-Party Computation for the GT Problem

#### 3.1.1. A Protocol for the Two-Party GT Problem

Yao’s scheme [1] simply determines whether x≤y or x>y, which cannot distinguish x<y from x=y. Our protocol can compare x>y,x<y, and x=y in one execution.In our solution, Alice (holdingx) uses the vectorization method to encode x into a vector and uses the Paillier encryption scheme to encrypt the vector. Bob (holding y) receives the encrypted vector, selects the y-th element, encrypts the y-th element into another ciphertext using the additive homomorphism of the Paillier encryption scheme, and returns the ciphertext to Alice. Alice decrypts the ciphertext and tells Bob the result.The solution for two-party GT problem is as follows.Protocol 1. Secure two-party computation of the GT problem.Input. Alice’s input is x, and Bob’s input is y. So x,y∈U=u1,…,us.Output. The relationship of x and y is denoted by (11)Px,y=-1,x>y,0,x=y,1,x<y.(1)
With the Paillier encryption scheme, Alice generates the public key{g,N} and private key {λ} and sends the public key to Bob.(2)
Following the vectorization method, Alice encodesx into a vector:(12)X=m1,…,mi,…,ms,where(13)mi=α,1≤ui<xγ,ui=xβ,ui>xα≠β≠γ.(3)
Alice selectss random numbers r1,…,rs, and encrypts the vector X using the Paillier encryption scheme: (14)EX=Em1,r1,…,Emi,ri,…,Ems,rs,whereEmi,ri=gmi·riNmod⁡N2 (i=1,…,s).(4)
Alice sendsE(X) to Bob.(5)
Bob selects a random numberrb. He chooses E(mi,ri) from E(X) such that i=y and computes (15)Emi,ri×E0,rb=gmi·rinmod⁡n2×g0·rbnmod⁡n2⟶Eμ.(6)
Bob sendsE(μ) to Alice.(7)
Alice decrypts(16)DEμ=μand tells Bob the resultP(x,y):Ifμ=α, P(x,y)=-1 and x>y.Ifμ=β, P(x,y)=1 and x<y.Ifμ=γ, P(x,y)=0 and x=y.


#### 3.1.2. Accuracy and Security

(1)
Alice computesD(E(μ))=μ; that is, μ=mi such that i=y. Since mi∈{m1,…,mx-1, mx,mx+1,…,ms}={α,…,α,γ,β,…,β}, if mi=α which implies mi∈{m1,…,mx-1}, so y<x. If mi=γ which implies mi=mx, then y=x. If mi=β which implies mi∈{mx+1, …,ms}, then y>x.
(2)
When Alice receivesE(μ) from Bob, she does not know how to compute E(μ) because she does not know rb, so E(mi,ri) is private for Bob. Therefore, y is private for Bob.
When Bob obtains the resultx>y or x<y, he cannot know which mi equals α or β, so x is private for Alice.
(3)
Using Protocol 1, we can determine the relationship betweenx and y in one execution, especially x=y that Yao’s solution [1] cannot determine directly.The following theorem refers to the privacy-preserving property of this protocol.Theorem 3.
Protocol 1 for the two-party GT problem is secure in the semihonest model.Proof.
We begin by constructingS1 and S2 such that (4) are satisfied.
In the protocol,(17)view1πx,y=x,EX,Eμ,μ,Px,y,f1x,y=f2x,y=output1πx,y=output2πx,y=Px,y,where x,y are inputs, E(X) is Alice’s encryption result, μ is Alice’s decryption result, E(μ) is Bob’s computation result, and P(x,y) is the output.
S
1 proceeds as follows:(1)
Byf1(x,y), S1 randomly selects a number y′∈U such that f1(x,y)=f1(x,y′). S1 constructs the vector X=(m1,m2,…,ms).(2)
Using the Paillier encryption scheme,S1 encrypts X using different random numbers ri: (18)EX=Em1,r1,Em2,r2,…,Ems,rs.(3)
S1 selects a random number r′ and computes E(mi,ri)×(r′nmod⁡n2)→E(μ′), (i=y′).(4)
S1 decrypts DEμ′=μ′. By comparing μ′ with {α,β,γ}, S1 determines P(x,y′).
Let(19)S1x,Px,y=x,EX,Eμ′,μ′,Px,y′.
SinceEμ≡cEμ′,μ≡cμ′, and P(x,y)=P(x,y′), then (20)S1x,f1x,y,f2x,yx,y≡cview1πx,y,output2πx,yx,y.
Similarly, we can constructS2, such that (21)f1x,y,S2y,f2x,yx,y≡coutput1πx,y,view2πx,yx,y.


### 3.2. Secure Multiparty Computation Protocol for the GT Problem (Secure Sorting Problem)

In practice, more than two parties want to privately compare all of their numbers. For example, some companies want to compare their turnovers, but they do not want to disclose their data, so they prefer a secure protocol that can sort their turnovers. As another example, students desire to know their own score’s rank without publishing their scores, and thus they must privately determine the order of their own score.To solve the secure multiparty GT problem (i.e., secure sorting problem), we may use Protocol 1 to compare pairwise, but this process is of high complexity and will disclose too much information to other parties. Therefore, we propose a more efficient protocol as follows.


#### 3.2.1. Secure Sorting Problem Model

The set is defined asK={(P1,a1),(P2,a2),…,(Pz,az)}, where Pi (i=1,…,z, and z is the number of the parties) holds his own number ai, ai≠aj(i≠j).ConsiderL={ord(a1),…,ord(az)}, where ord(ai) is the order of ai. (22)F:K⟶L.A protocol is proposed to computeF privately. In the protocol, Pi only knows ord(ai) and cannot know other parties’ orders and any other information.


#### 3.2.2. A Protocol for the Multiparty GT Problem

In our protocol,ai∈U={u1,…,uk,…,us}, Pi encodes his own number ai into a vector Vi by the vectorization method as follows. (23)ai⟶Vi=vi1,…,vik,…,vis,where (24)vik=0,1≤uk<ai,α,uk≥ai.All parties’Vi form a matrix (Table 1). If Pi wants to know his order, he can add the components of aith column vector. For example, Table 1 shows the vectorization method and all parties’ orders.Table 1
Four-party vectorization method and sorting order.
P
1
:
a
1
=
4
,
V
1
→
0
0
0
α
α
α
α
α
⋯
P
2
:
a
2
=
2
,
V
2
→
0
α
α
α
α
α
α
α
⋯
P
3
:
a
3
=
6
,
V
3
→
0
0
0
0
0
α
α
α
⋯
P
4
:
a
4
=
7
,
V
4
→
0
0
0
0
0
0
α
α
⋯
Addition
α
2
α
3
α
4
α
Sorting order
o
r
d
(
a
2
)
=
1
o
r
d
(
a
1
)
=
2
o
r
d
(
a
3
)
=
3
o
r
d
(
a
4
)
=
4However, ifPi sends Vi to other parties directly, ai will be disclosed. We utilize the secret splitting method to guarantee his privacy. Pi splits Vi into z vectors Vi(1),…,Vi(z). He keeps Vi(i) secret and sends Vi(1),…,Vi(i-1),Vi(i+1),…,Vi(z) to other z-1 parties. In the end, Pi will receive (z-1) vectors Vj(i) (j≠i) that other parties send to him, as shown in Figure 1. Pi computes Vi′=Vi(i)+∑j=1zVj(i),(j≠i).Figure 1
Four-party sendingVi(k).All parties publish theirVi′. If Pi wants to know his order, he adds all vjai′ of Vj′, that is, ∑j=1zvjai′=δ, and ord(ai)=δ/α.Protocol 2. Secure multiparty computation of the GT problem.Input. The inputs of P1,P2,…,Pz are a1,a2,…,az,ai∈U={u1,u2,…,us}.Output. Consider ord(a1),ord(a2),…,ord(az).(1)
All parties encode their own numbers with the vectorization method. Takeai for example:(25)ai⟶Vi=vi1,…,vik,…,vis,where(26)vik=0,1≤ui<ai,α,k≥ai.(2)
Pi randomly splits Vi into z vectors {Vi(1),Vi(2),…,Vi(z)}, as follows:(27)Vi=vi1,vi2,vi3,…,vik,…,vis⟶Vi1=vi11,vi21,vi31,…,vik1,…,vis1,Vi2=vi12,vi22,vi32,…,vik2,…,vis2,⋮Viz=vi1z,vi2z,vi3z,…,vikz,…,visz,where allvik(j)(1≤j≤z,1≤k≤s) are random numbers that satisfy(28)vi1=∑j=1zvi1j,…,vis=∑j=1zvisj.(3)
Pi keeps his Vi(i) secret and sends Vi(j)(j≠i) to other z-1 parties separately. In the end, each party holds z vectors; that is, Pi holds V1(i),…,Vi(i),…,Vz(i) and adds the corresponding column vectors, denoted by Vi′={vi1′,vi2′,…,vis′}={(v11(i)+v21(i)+⋯+vz1(i)),(v12(i)+v22(i)+⋯+vz2(i)),…,(v1s(i)+v2s(i)+⋯+vzs(i))}.(4)
All parties publish theirVi′. According to ai, Pi adds all vjai′ (j=1,…,z) of Vj′, denoted by δi=(v1ai′+v2ai′+v3ai′+⋯+vzai′).(5)
Pi computes ord(ai)=δi/α as his order.


#### 3.2.3. Accuracy and Security

(1)
In this protocol, we use the secret splitting method to split a vectorV into z vectors. Each party keeps his Vi(i) secret. Without Vi(i), others cannot conspire to compute Vi.
(2)
Protocol 2 does not require any encryption scheme based on computational assumptions, so it is information-theoretically secure.
(3)
P
i adds the ai-th column vectors of Vj′(j=1,…,z), and other parties do not know which column vector Pi selects.
(4)
In a particular case, ifPi holds the number 2 and his order is also 2, he confirms that someone holds the number 1, but he does not know who holds the number 1. This situation does not imply that the protocol is insecure because this information is what the function computed leaks. Even in the ideal SMC protocol, the TTP tells Pi that his rank is 2, the information also leaks because this is what the function to be computed leaks.
(5)
The protocol cannot be applied to the two-party situation, because, in this case,
in the execution of Protocol 2 for two parties, Alice splitsV1 to vectors {V1(1),V1(2)}, and Bob splits V2 to vectors {V2(1),V2(2)}. Alice sends V1(2) to Bob, and Bob sends V2(1) to Alice. Bob computes V2′=V2(2)+V1(2) and sends V2′ to Alice. Because Alice has the vectors V1(2) and V2(1), she can compute V2(2)=V2′-V1(2) and compute V2=V2(1)+V2(2), so she obtains Bob’s a2. Therefore, Protocol 2 is not applicable to the two-party GT problem.
(6)
In this protocol, we do not consider attacks in the transmitting process. If necessary, we can use the Paillier encryption scheme [34] to encrypt Vi(k) and Vi′, although this increases the computational and communication costs.
(7)
In fact, in many cases, limited parties take part in sorting their numbers. In cryptographic literatures, the multiparty refers 3 to 5 parties. There are few literatures that consider more than 10 parties. In addition, in our life, we sort 100 richest men of the world or compare the top 100 banks in the world or rank the top 500 companies all over the world at most. Therefore, the number of parties in the above cases does matter much.
(8)
Protocol 2 can resist collusion attacks, which is proved by the following Theorem4.The following theorem states the privacy-preserving property of the protocol.Theorem 4.
Protocol 2 for the multiparty GT problem is secure in the semihonest model.Proof.
In Protocol 2, even though some adversaries obtainPi’s z-1 vectors Vj(i)(j≠i), they cannot compute Vi. Because all vectors Vj(i)(j=1,…,z) sum to Vi, while Pi keeps Vi(i) secret, the adversaries cannot obtain Vi(i). Therefore, the security of Protocol 2 is the same as the security of a protocol with a TTP in the ideal SMC model. We prove the privacy-preserving property of Protocol 2 using the following formal proving method (Definition 2).
We consider the following cases.
Case 1. P1 does not participate in collusion, while other participants I(I⊆{P2,P3,…,Pz}) conspire to compute Pj’s Vj(Pj∉I). By executing Protocol 2, the set I can obtain {V2′,…,Vj-1′,Vj+1′,…,Vz′} and {ord(a2),…,ord(aj-1),ord(aj+1),…,ord(az)}. Since P1,Pj∉I,V1(1) and Vj(j) are private, the coconspirators I cannot obtain V1 and Vj. So they do not conspire aj. We can construct a simulator S such that (5) holds.(i)
By the result of the protocol, the coconspiratorsI choose V1(1)∗ and Vj(j)∗ such that(29)V11∗+V12+⋯+V1z+V2+⋯+Vj-1+Vjj∗+Vj1+⋯+Vjz+Vj+1+⋯+Vz=V.(ii)
The setI will execute the protocol Π, determining their viewIΠ as follows:(30)viewIΠV=I,view2ΠV,…,viewj-1ΠV,viewj+1ΠV,…,viewzΠV=V1′∗,V2′,…,Vj-1′,Vj′∗,Vj+1′,…,Vz′,V.(iii)
Let(31)SI,V2′,V3′,…,Vz′,fV=V1′,V2′,…,Vj-1′,Vj′,Vj+1′,…,Vz′,V.V1′∗≡cV1′,Vj′∗≡cVj′,SI,V2′,V3′,…,Vz′,fV≡cviewIΠV.Therefore, in this case, the protocol is secure.
Case 2. P1 and the participants I⊆{P2,P3,…,Pz} conspire to obtain the information of other participants I′={P1,P2,…,Pz}∖I.
Case 2.1. If I′=1, suppose Pi∈I′, Pi’s order ord(ai) except ai can be obtained, which is the same as the case mentioned above in part (4) and part (5) of Section 3.2.3. Even in the ideal SMC protocol, the TTP tells the orders of P1 and I, and P1 and I can conspire Pi’s order ord(ai). Therefore, the protocol does not leak more information than that the ideal SMC model leaks, and the protocol is secure.
Case 2.2. If I′={Pi,Pj}, Vi(i) and Vj(j) are private, and P1 and I cannot know Vi′ and Vj′, which is the same as Case 1. In this case, the protocol is secure. This is true for I′⩾2.
To sum up, in any case, there exists a simulatorS such that (5) holds, so Protocol 2 is secure.To help the readers understand the protocol, we give a toy example.ExampleInput. {(P1,5),(P2,3),(P3,8),(P4,7)},U={1, …,10}.Output. ord(i),i∈{5,3,8,7}.(1)
P1,…,P4 encode their number’s vectors as follows (set α=2):(32)x1=5,V1=0,0,0,0,2,2,2,2,2,2,x2=3,V2=0,0,2,2,2,2,2,2,2,2,x3=8,V3=0,0,0,0,0,0,0,2,2,2,x4=7,V4=0,0,0,0,0,0,2,2,2,2.(2)
P1,…,P4 split their own vector into four random vectors, respectively:(33)V1⟶V11=-5,-3,2,3,3,-1,-4,2,3,5V12=7,4,-5,6,2,-4,9,-2,1,3V13=2,-1,3,-2,4,5,4,1,2,-3V14=-4,0,0,-7,-7,2,-7,1,-4,-3.V2⟶V21=4,2,5,-7,-3,-5,6,1,0,1V22=-2,3,-1,6,1,2,-4,-5,-7,3V23=3,-6,2,3,2,5,-3,-2,4,-2V24=-5,1,-4,0,2,0,3,8,5,0.V3⟶V31=2,1,-3,-5,-2,2,0,0,6,-1V32=3,0,-2,0,-5,0,-4,0,-2,2V33=-3,2,5,-4,1,0,2,-1,-3,-2V34=-2,-3,0,9,6,-2,2,3,1,3.V4⟶V41=3,1,-2,-5,-3,-2,-1,0,-3,-4V42=2,3,-1,5,7,4,2,0,-3,2V43=-4,3,-2,-1,-5,2,1,2,3,1V44=-1,-7,5,1,1,-4,0,0,5,3.(3)
P1 keeps V1(1) secret and sends V1(2),V1(3),V1(4) to P2,P3,P4, respectively.P2 keeps V2(2) secret and sends V2(1),V2(3),V2(4) to P1,P3,P4, respectively.P3 keeps V3(3) secret and sends V3(1),V3(2),V3(4) to P1,P2,P4, respectively.P4 keeps V4(4) secret and sends V4(1),V4(2),V4(3) to P1,P2,P3, respectively.(4)
P1 holds V1(1),V2(1),V3(1),V4(1).P2 holds V2(2),V1(2),V3(2),V4(2).P3 holds V3(3),V1(3),V2(3),V4(3).P4 holds V4(4),V1(4),V2(4),V3(4).(5)
P1 computes V1′=V1(1)+V2(1)+V3(1)+V4(1)=(4,1,2,-14,-5,-6,1,3,6,1).P2 computes V2′=V2(2)+V1(2)+V3(2)+V4(2)=(10,10,-9,17,5,2,3,-7,-11,10).P3 computes V3′=V3(3)+V1(3)+V2(3)+V4(3)=(-2,-2,8,-4,2,12,4,0,6,-6).P4 computes V4′=V4(4)+V1(4)+V2(4)+V3(4)=(-12,-9,1,3,2,-4,-2,12,7,3).(6)
P1,P2,P3,P4 publish their V1′,V2′,V3′,V4′, respectively.(7)
Bya1=5, P1 selects V1′(5)=-5,V2′(5)=5,V3′(5)=2,V4′(5)=2.Bya2=3, P2 selects V1′(3)=2,V2′(3)=-9,V3′(3)=8,V4′(3)=1.Bya3=8, P3 selects V1′(8)=3,V2′(8)=-7,V3′(8)=0,V4′(8)=12.Bya1=3, P4 selects V1′(7)=1,V2′(7)=3,V3′(7)=4,V4′(7)=-2.(8)
P1 computes his rank ord(5)=(V1′(5)+V2′(5)+V3′(5)+V4′(5))/α=(-5+5+2+2)/2=2.P2 computes his rank ord(3)=(V1′(3)+V2′(3)+V3′(3)+V4′(3))/α=(2+(-9)+8+1)/2=1.P3 computes his rank ord(8)=(V1′(8)+V2′(8)+V3′(8)+V4′(8))/α=(3-7+0+12)/2=4.P4 computes his rank ord(7)=(V1′(7)+V2′(7)+V3′(7)+V4′(7))/α=(1+3+4+(-2))/2=3.


## 3.1. Secure Two-Party Computation for the GT Problem

### 3.1.1. A Protocol for the Two-Party GT Problem

Yao’s scheme [1] simply determines whether x≤y or x>y, which cannot distinguish x<y from x=y. Our protocol can compare x>y,x<y, and x=y in one execution.In our solution, Alice (holdingx) uses the vectorization method to encode x into a vector and uses the Paillier encryption scheme to encrypt the vector. Bob (holding y) receives the encrypted vector, selects the y-th element, encrypts the y-th element into another ciphertext using the additive homomorphism of the Paillier encryption scheme, and returns the ciphertext to Alice. Alice decrypts the ciphertext and tells Bob the result.The solution for two-party GT problem is as follows.Protocol 1. Secure two-party computation of the GT problem.Input. Alice’s input is x, and Bob’s input is y. So x,y∈U=u1,…,us.Output. The relationship of x and y is denoted by (11)Px,y=-1,x>y,0,x=y,1,x<y.(1)
With the Paillier encryption scheme, Alice generates the public key{g,N} and private key {λ} and sends the public key to Bob.(2)
Following the vectorization method, Alice encodesx into a vector:(12)X=m1,…,mi,…,ms,where(13)mi=α,1≤ui<xγ,ui=xβ,ui>xα≠β≠γ.(3)
Alice selectss random numbers r1,…,rs, and encrypts the vector X using the Paillier encryption scheme: (14)EX=Em1,r1,…,Emi,ri,…,Ems,rs,whereEmi,ri=gmi·riNmod⁡N2 (i=1,…,s).(4)
Alice sendsE(X) to Bob.(5)
Bob selects a random numberrb. He chooses E(mi,ri) from E(X) such that i=y and computes (15)Emi,ri×E0,rb=gmi·rinmod⁡n2×g0·rbnmod⁡n2⟶Eμ.(6)
Bob sendsE(μ) to Alice.(7)
Alice decrypts(16)DEμ=μand tells Bob the resultP(x,y):Ifμ=α, P(x,y)=-1 and x>y.Ifμ=β, P(x,y)=1 and x<y.Ifμ=γ, P(x,y)=0 and x=y.


### 3.1.2. Accuracy and Security

(1)
Alice computesD(E(μ))=μ; that is, μ=mi such that i=y. Since mi∈{m1,…,mx-1, mx,mx+1,…,ms}={α,…,α,γ,β,…,β}, if mi=α which implies mi∈{m1,…,mx-1}, so y<x. If mi=γ which implies mi=mx, then y=x. If mi=β which implies mi∈{mx+1, …,ms}, then y>x.
(2)
When Alice receivesE(μ) from Bob, she does not know how to compute E(μ) because she does not know rb, so E(mi,ri) is private for Bob. Therefore, y is private for Bob.
When Bob obtains the resultx>y or x<y, he cannot know which mi equals α or β, so x is private for Alice.
(3)
Using Protocol 1, we can determine the relationship betweenx and y in one execution, especially x=y that Yao’s solution [1] cannot determine directly.The following theorem refers to the privacy-preserving property of this protocol.Theorem 3.
Protocol 1 for the two-party GT problem is secure in the semihonest model.Proof.
We begin by constructingS1 and S2 such that (4) are satisfied.
In the protocol,(17)view1πx,y=x,EX,Eμ,μ,Px,y,f1x,y=f2x,y=output1πx,y=output2πx,y=Px,y,where x,y are inputs, E(X) is Alice’s encryption result, μ is Alice’s decryption result, E(μ) is Bob’s computation result, and P(x,y) is the output.
S
1 proceeds as follows:(1)
Byf1(x,y), S1 randomly selects a number y′∈U such that f1(x,y)=f1(x,y′). S1 constructs the vector X=(m1,m2,…,ms).(2)
Using the Paillier encryption scheme,S1 encrypts X using different random numbers ri: (18)EX=Em1,r1,Em2,r2,…,Ems,rs.(3)
S1 selects a random number r′ and computes E(mi,ri)×(r′nmod⁡n2)→E(μ′), (i=y′).(4)
S1 decrypts DEμ′=μ′. By comparing μ′ with {α,β,γ}, S1 determines P(x,y′).
Let(19)S1x,Px,y=x,EX,Eμ′,μ′,Px,y′.
SinceEμ≡cEμ′,μ≡cμ′, and P(x,y)=P(x,y′), then (20)S1x,f1x,y,f2x,yx,y≡cview1πx,y,output2πx,yx,y.
Similarly, we can constructS2, such that (21)f1x,y,S2y,f2x,yx,y≡coutput1πx,y,view2πx,yx,y.


## 3.1.1. A Protocol for the Two-Party GT Problem

Yao’s scheme [1] simply determines whether x≤y or x>y, which cannot distinguish x<y from x=y. Our protocol can compare x>y,x<y, and x=y in one execution.In our solution, Alice (holdingx) uses the vectorization method to encode x into a vector and uses the Paillier encryption scheme to encrypt the vector. Bob (holding y) receives the encrypted vector, selects the y-th element, encrypts the y-th element into another ciphertext using the additive homomorphism of the Paillier encryption scheme, and returns the ciphertext to Alice. Alice decrypts the ciphertext and tells Bob the result.The solution for two-party GT problem is as follows.Protocol 1. Secure two-party computation of the GT problem.Input. Alice’s input is x, and Bob’s input is y. So x,y∈U=u1,…,us.Output. The relationship of x and y is denoted by (11)Px,y=-1,x>y,0,x=y,1,x<y.(1)
With the Paillier encryption scheme, Alice generates the public key{g,N} and private key {λ} and sends the public key to Bob.(2)
Following the vectorization method, Alice encodesx into a vector:(12)X=m1,…,mi,…,ms,where(13)mi=α,1≤ui<xγ,ui=xβ,ui>xα≠β≠γ.(3)
Alice selectss random numbers r1,…,rs, and encrypts the vector X using the Paillier encryption scheme: (14)EX=Em1,r1,…,Emi,ri,…,Ems,rs,whereEmi,ri=gmi·riNmod⁡N2 (i=1,…,s).(4)
Alice sendsE(X) to Bob.(5)
Bob selects a random numberrb. He chooses E(mi,ri) from E(X) such that i=y and computes (15)Emi,ri×E0,rb=gmi·rinmod⁡n2×g0·rbnmod⁡n2⟶Eμ.(6)
Bob sendsE(μ) to Alice.(7)
Alice decrypts(16)DEμ=μand tells Bob the resultP(x,y):Ifμ=α, P(x,y)=-1 and x>y.Ifμ=β, P(x,y)=1 and x<y.Ifμ=γ, P(x,y)=0 and x=y.


## 3.1.2. Accuracy and Security

(1)
Alice computesD(E(μ))=μ; that is, μ=mi such that i=y. Since mi∈{m1,…,mx-1, mx,mx+1,…,ms}={α,…,α,γ,β,…,β}, if mi=α which implies mi∈{m1,…,mx-1}, so y<x. If mi=γ which implies mi=mx, then y=x. If mi=β which implies mi∈{mx+1, …,ms}, then y>x.
(2)
When Alice receivesE(μ) from Bob, she does not know how to compute E(μ) because she does not know rb, so E(mi,ri) is private for Bob. Therefore, y is private for Bob.
When Bob obtains the resultx>y or x<y, he cannot know which mi equals α or β, so x is private for Alice.
(3)
Using Protocol 1, we can determine the relationship betweenx and y in one execution, especially x=y that Yao’s solution [1] cannot determine directly.The following theorem refers to the privacy-preserving property of this protocol.Theorem 3.
Protocol 1 for the two-party GT problem is secure in the semihonest model.Proof.
We begin by constructingS1 and S2 such that (4) are satisfied.
In the protocol,(17)view1πx,y=x,EX,Eμ,μ,Px,y,f1x,y=f2x,y=output1πx,y=output2πx,y=Px,y,where x,y are inputs, E(X) is Alice’s encryption result, μ is Alice’s decryption result, E(μ) is Bob’s computation result, and P(x,y) is the output.
S
1 proceeds as follows:(1)
Byf1(x,y), S1 randomly selects a number y′∈U such that f1(x,y)=f1(x,y′). S1 constructs the vector X=(m1,m2,…,ms).(2)
Using the Paillier encryption scheme,S1 encrypts X using different random numbers ri: (18)EX=Em1,r1,Em2,r2,…,Ems,rs.(3)
S1 selects a random number r′ and computes E(mi,ri)×(r′nmod⁡n2)→E(μ′), (i=y′).(4)
S1 decrypts DEμ′=μ′. By comparing μ′ with {α,β,γ}, S1 determines P(x,y′).
Let(19)S1x,Px,y=x,EX,Eμ′,μ′,Px,y′.
SinceEμ≡cEμ′,μ≡cμ′, and P(x,y)=P(x,y′), then (20)S1x,f1x,y,f2x,yx,y≡cview1πx,y,output2πx,yx,y.
Similarly, we can constructS2, such that (21)f1x,y,S2y,f2x,yx,y≡coutput1πx,y,view2πx,yx,y.


## 3.2. Secure Multiparty Computation Protocol for the GT Problem (Secure Sorting Problem)

In practice, more than two parties want to privately compare all of their numbers. For example, some companies want to compare their turnovers, but they do not want to disclose their data, so they prefer a secure protocol that can sort their turnovers. As another example, students desire to know their own score’s rank without publishing their scores, and thus they must privately determine the order of their own score.To solve the secure multiparty GT problem (i.e., secure sorting problem), we may use Protocol 1 to compare pairwise, but this process is of high complexity and will disclose too much information to other parties. Therefore, we propose a more efficient protocol as follows.


### 3.2.1. Secure Sorting Problem Model

The set is defined asK={(P1,a1),(P2,a2),…,(Pz,az)}, where Pi (i=1,…,z, and z is the number of the parties) holds his own number ai, ai≠aj(i≠j).ConsiderL={ord(a1),…,ord(az)}, where ord(ai) is the order of ai. (22)F:K⟶L.A protocol is proposed to computeF privately. In the protocol, Pi only knows ord(ai) and cannot know other parties’ orders and any other information.


### 3.2.2. A Protocol for the Multiparty GT Problem

In our protocol,ai∈U={u1,…,uk,…,us}, Pi encodes his own number ai into a vector Vi by the vectorization method as follows. (23)ai⟶Vi=vi1,…,vik,…,vis,where (24)vik=0,1≤uk<ai,α,uk≥ai.All parties’Vi form a matrix (Table 1). If Pi wants to know his order, he can add the components of aith column vector. For example, Table 1 shows the vectorization method and all parties’ orders.Table 1
Four-party vectorization method and sorting order.
P
1
:
a
1
=
4
,
V
1
→
0
0
0
α
α
α
α
α
⋯
P
2
:
a
2
=
2
,
V
2
→
0
α
α
α
α
α
α
α
⋯
P
3
:
a
3
=
6
,
V
3
→
0
0
0
0
0
α
α
α
⋯
P
4
:
a
4
=
7
,
V
4
→
0
0
0
0
0
0
α
α
⋯
Addition
α
2
α
3
α
4
α
Sorting order
o
r
d
(
a
2
)
=
1
o
r
d
(
a
1
)
=
2
o
r
d
(
a
3
)
=
3
o
r
d
(
a
4
)
=
4However, ifPi sends Vi to other parties directly, ai will be disclosed. We utilize the secret splitting method to guarantee his privacy. Pi splits Vi into z vectors Vi(1),…,Vi(z). He keeps Vi(i) secret and sends Vi(1),…,Vi(i-1),Vi(i+1),…,Vi(z) to other z-1 parties. In the end, Pi will receive (z-1) vectors Vj(i) (j≠i) that other parties send to him, as shown in Figure 1. Pi computes Vi′=Vi(i)+∑j=1zVj(i),(j≠i).Figure 1
Four-party sendingVi(k).All parties publish theirVi′. If Pi wants to know his order, he adds all vjai′ of Vj′, that is, ∑j=1zvjai′=δ, and ord(ai)=δ/α.Protocol 2. Secure multiparty computation of the GT problem.Input. The inputs of P1,P2,…,Pz are a1,a2,…,az,ai∈U={u1,u2,…,us}.Output. Consider ord(a1),ord(a2),…,ord(az).(1)
All parties encode their own numbers with the vectorization method. Takeai for example:(25)ai⟶Vi=vi1,…,vik,…,vis,where(26)vik=0,1≤ui<ai,α,k≥ai.(2)
Pi randomly splits Vi into z vectors {Vi(1),Vi(2),…,Vi(z)}, as follows:(27)Vi=vi1,vi2,vi3,…,vik,…,vis⟶Vi1=vi11,vi21,vi31,…,vik1,…,vis1,Vi2=vi12,vi22,vi32,…,vik2,…,vis2,⋮Viz=vi1z,vi2z,vi3z,…,vikz,…,visz,where allvik(j)(1≤j≤z,1≤k≤s) are random numbers that satisfy(28)vi1=∑j=1zvi1j,…,vis=∑j=1zvisj.(3)
Pi keeps his Vi(i) secret and sends Vi(j)(j≠i) to other z-1 parties separately. In the end, each party holds z vectors; that is, Pi holds V1(i),…,Vi(i),…,Vz(i) and adds the corresponding column vectors, denoted by Vi′={vi1′,vi2′,…,vis′}={(v11(i)+v21(i)+⋯+vz1(i)),(v12(i)+v22(i)+⋯+vz2(i)),…,(v1s(i)+v2s(i)+⋯+vzs(i))}.(4)
All parties publish theirVi′. According to ai, Pi adds all vjai′ (j=1,…,z) of Vj′, denoted by δi=(v1ai′+v2ai′+v3ai′+⋯+vzai′).(5)
Pi computes ord(ai)=δi/α as his order.


### 3.2.3. Accuracy and Security

(1)
In this protocol, we use the secret splitting method to split a vectorV into z vectors. Each party keeps his Vi(i) secret. Without Vi(i), others cannot conspire to compute Vi.
(2)
Protocol 2 does not require any encryption scheme based on computational assumptions, so it is information-theoretically secure.
(3)
P
i adds the ai-th column vectors of Vj′(j=1,…,z), and other parties do not know which column vector Pi selects.
(4)
In a particular case, ifPi holds the number 2 and his order is also 2, he confirms that someone holds the number 1, but he does not know who holds the number 1. This situation does not imply that the protocol is insecure because this information is what the function computed leaks. Even in the ideal SMC protocol, the TTP tells Pi that his rank is 2, the information also leaks because this is what the function to be computed leaks.
(5)
The protocol cannot be applied to the two-party situation, because, in this case,
in the execution of Protocol 2 for two parties, Alice splitsV1 to vectors {V1(1),V1(2)}, and Bob splits V2 to vectors {V2(1),V2(2)}. Alice sends V1(2) to Bob, and Bob sends V2(1) to Alice. Bob computes V2′=V2(2)+V1(2) and sends V2′ to Alice. Because Alice has the vectors V1(2) and V2(1), she can compute V2(2)=V2′-V1(2) and compute V2=V2(1)+V2(2), so she obtains Bob’s a2. Therefore, Protocol 2 is not applicable to the two-party GT problem.
(6)
In this protocol, we do not consider attacks in the transmitting process. If necessary, we can use the Paillier encryption scheme [34] to encrypt Vi(k) and Vi′, although this increases the computational and communication costs.
(7)
In fact, in many cases, limited parties take part in sorting their numbers. In cryptographic literatures, the multiparty refers 3 to 5 parties. There are few literatures that consider more than 10 parties. In addition, in our life, we sort 100 richest men of the world or compare the top 100 banks in the world or rank the top 500 companies all over the world at most. Therefore, the number of parties in the above cases does matter much.
(8)
Protocol 2 can resist collusion attacks, which is proved by the following Theorem4.The following theorem states the privacy-preserving property of the protocol.Theorem 4.
Protocol 2 for the multiparty GT problem is secure in the semihonest model.Proof.
In Protocol 2, even though some adversaries obtainPi’s z-1 vectors Vj(i)(j≠i), they cannot compute Vi. Because all vectors Vj(i)(j=1,…,z) sum to Vi, while Pi keeps Vi(i) secret, the adversaries cannot obtain Vi(i). Therefore, the security of Protocol 2 is the same as the security of a protocol with a TTP in the ideal SMC model. We prove the privacy-preserving property of Protocol 2 using the following formal proving method (Definition 2).
We consider the following cases.
Case 1. P1 does not participate in collusion, while other participants I(I⊆{P2,P3,…,Pz}) conspire to compute Pj’s Vj(Pj∉I). By executing Protocol 2, the set I can obtain {V2′,…,Vj-1′,Vj+1′,…,Vz′} and {ord(a2),…,ord(aj-1),ord(aj+1),…,ord(az)}. Since P1,Pj∉I,V1(1) and Vj(j) are private, the coconspirators I cannot obtain V1 and Vj. So they do not conspire aj. We can construct a simulator S such that (5) holds.(i)
By the result of the protocol, the coconspiratorsI choose V1(1)∗ and Vj(j)∗ such that(29)V11∗+V12+⋯+V1z+V2+⋯+Vj-1+Vjj∗+Vj1+⋯+Vjz+Vj+1+⋯+Vz=V.(ii)
The setI will execute the protocol Π, determining their viewIΠ as follows:(30)viewIΠV=I,view2ΠV,…,viewj-1ΠV,viewj+1ΠV,…,viewzΠV=V1′∗,V2′,…,Vj-1′,Vj′∗,Vj+1′,…,Vz′,V.(iii)
Let(31)SI,V2′,V3′,…,Vz′,fV=V1′,V2′,…,Vj-1′,Vj′,Vj+1′,…,Vz′,V.V1′∗≡cV1′,Vj′∗≡cVj′,SI,V2′,V3′,…,Vz′,fV≡cviewIΠV.Therefore, in this case, the protocol is secure.
Case 2. P1 and the participants I⊆{P2,P3,…,Pz} conspire to obtain the information of other participants I′={P1,P2,…,Pz}∖I.
Case 2.1. If I′=1, suppose Pi∈I′, Pi’s order ord(ai) except ai can be obtained, which is the same as the case mentioned above in part (4) and part (5) of Section 3.2.3. Even in the ideal SMC protocol, the TTP tells the orders of P1 and I, and P1 and I can conspire Pi’s order ord(ai). Therefore, the protocol does not leak more information than that the ideal SMC model leaks, and the protocol is secure.
Case 2.2. If I′={Pi,Pj}, Vi(i) and Vj(j) are private, and P1 and I cannot know Vi′ and Vj′, which is the same as Case 1. In this case, the protocol is secure. This is true for I′⩾2.
To sum up, in any case, there exists a simulatorS such that (5) holds, so Protocol 2 is secure.To help the readers understand the protocol, we give a toy example.ExampleInput. {(P1,5),(P2,3),(P3,8),(P4,7)},U={1, …,10}.Output. ord(i),i∈{5,3,8,7}.(1)
P1,…,P4 encode their number’s vectors as follows (set α=2):(32)x1=5,V1=0,0,0,0,2,2,2,2,2,2,x2=3,V2=0,0,2,2,2,2,2,2,2,2,x3=8,V3=0,0,0,0,0,0,0,2,2,2,x4=7,V4=0,0,0,0,0,0,2,2,2,2.(2)
P1,…,P4 split their own vector into four random vectors, respectively:(33)V1⟶V11=-5,-3,2,3,3,-1,-4,2,3,5V12=7,4,-5,6,2,-4,9,-2,1,3V13=2,-1,3,-2,4,5,4,1,2,-3V14=-4,0,0,-7,-7,2,-7,1,-4,-3.V2⟶V21=4,2,5,-7,-3,-5,6,1,0,1V22=-2,3,-1,6,1,2,-4,-5,-7,3V23=3,-6,2,3,2,5,-3,-2,4,-2V24=-5,1,-4,0,2,0,3,8,5,0.V3⟶V31=2,1,-3,-5,-2,2,0,0,6,-1V32=3,0,-2,0,-5,0,-4,0,-2,2V33=-3,2,5,-4,1,0,2,-1,-3,-2V34=-2,-3,0,9,6,-2,2,3,1,3.V4⟶V41=3,1,-2,-5,-3,-2,-1,0,-3,-4V42=2,3,-1,5,7,4,2,0,-3,2V43=-4,3,-2,-1,-5,2,1,2,3,1V44=-1,-7,5,1,1,-4,0,0,5,3.(3)
P1 keeps V1(1) secret and sends V1(2),V1(3),V1(4) to P2,P3,P4, respectively.P2 keeps V2(2) secret and sends V2(1),V2(3),V2(4) to P1,P3,P4, respectively.P3 keeps V3(3) secret and sends V3(1),V3(2),V3(4) to P1,P2,P4, respectively.P4 keeps V4(4) secret and sends V4(1),V4(2),V4(3) to P1,P2,P3, respectively.(4)
P1 holds V1(1),V2(1),V3(1),V4(1).P2 holds V2(2),V1(2),V3(2),V4(2).P3 holds V3(3),V1(3),V2(3),V4(3).P4 holds V4(4),V1(4),V2(4),V3(4).(5)
P1 computes V1′=V1(1)+V2(1)+V3(1)+V4(1)=(4,1,2,-14,-5,-6,1,3,6,1).P2 computes V2′=V2(2)+V1(2)+V3(2)+V4(2)=(10,10,-9,17,5,2,3,-7,-11,10).P3 computes V3′=V3(3)+V1(3)+V2(3)+V4(3)=(-2,-2,8,-4,2,12,4,0,6,-6).P4 computes V4′=V4(4)+V1(4)+V2(4)+V3(4)=(-12,-9,1,3,2,-4,-2,12,7,3).(6)
P1,P2,P3,P4 publish their V1′,V2′,V3′,V4′, respectively.(7)
Bya1=5, P1 selects V1′(5)=-5,V2′(5)=5,V3′(5)=2,V4′(5)=2.Bya2=3, P2 selects V1′(3)=2,V2′(3)=-9,V3′(3)=8,V4′(3)=1.Bya3=8, P3 selects V1′(8)=3,V2′(8)=-7,V3′(8)=0,V4′(8)=12.Bya1=3, P4 selects V1′(7)=1,V2′(7)=3,V3′(7)=4,V4′(7)=-2.(8)
P1 computes his rank ord(5)=(V1′(5)+V2′(5)+V3′(5)+V4′(5))/α=(-5+5+2+2)/2=2.P2 computes his rank ord(3)=(V1′(3)+V2′(3)+V3′(3)+V4′(3))/α=(2+(-9)+8+1)/2=1.P3 computes his rank ord(8)=(V1′(8)+V2′(8)+V3′(8)+V4′(8))/α=(3-7+0+12)/2=4.P4 computes his rank ord(7)=(V1′(7)+V2′(7)+V3′(7)+V4′(7))/α=(1+3+4+(-2))/2=3.


## 3.2.1. Secure Sorting Problem Model

The set is defined asK={(P1,a1),(P2,a2),…,(Pz,az)}, where Pi (i=1,…,z, and z is the number of the parties) holds his own number ai, ai≠aj(i≠j).ConsiderL={ord(a1),…,ord(az)}, where ord(ai) is the order of ai. (22)F:K⟶L.A protocol is proposed to computeF privately. In the protocol, Pi only knows ord(ai) and cannot know other parties’ orders and any other information.


## 3.2.2. A Protocol for the Multiparty GT Problem

In our protocol,ai∈U={u1,…,uk,…,us}, Pi encodes his own number ai into a vector Vi by the vectorization method as follows. (23)ai⟶Vi=vi1,…,vik,…,vis,where (24)vik=0,1≤uk<ai,α,uk≥ai.All parties’Vi form a matrix (Table 1). If Pi wants to know his order, he can add the components of aith column vector. For example, Table 1 shows the vectorization method and all parties’ orders.Table 1
Four-party vectorization method and sorting order.
P
1
:
a
1
=
4
,
V
1
→
0
0
0
α
α
α
α
α
⋯
P
2
:
a
2
=
2
,
V
2
→
0
α
α
α
α
α
α
α
⋯
P
3
:
a
3
=
6
,
V
3
→
0
0
0
0
0
α
α
α
⋯
P
4
:
a
4
=
7
,
V
4
→
0
0
0
0
0
0
α
α
⋯
Addition
α
2
α
3
α
4
α
Sorting order
o
r
d
(
a
2
)
=
1
o
r
d
(
a
1
)
=
2
o
r
d
(
a
3
)
=
3
o
r
d
(
a
4
)
=
4However, ifPi sends Vi to other parties directly, ai will be disclosed. We utilize the secret splitting method to guarantee his privacy. Pi splits Vi into z vectors Vi(1),…,Vi(z). He keeps Vi(i) secret and sends Vi(1),…,Vi(i-1),Vi(i+1),…,Vi(z) to other z-1 parties. In the end, Pi will receive (z-1) vectors Vj(i) (j≠i) that other parties send to him, as shown in Figure 1. Pi computes Vi′=Vi(i)+∑j=1zVj(i),(j≠i).Figure 1
Four-party sendingVi(k).All parties publish theirVi′. If Pi wants to know his order, he adds all vjai′ of Vj′, that is, ∑j=1zvjai′=δ, and ord(ai)=δ/α.Protocol 2. Secure multiparty computation of the GT problem.Input. The inputs of P1,P2,…,Pz are a1,a2,…,az,ai∈U={u1,u2,…,us}.Output. Consider ord(a1),ord(a2),…,ord(az).(1)
All parties encode their own numbers with the vectorization method. Takeai for example:(25)ai⟶Vi=vi1,…,vik,…,vis,where(26)vik=0,1≤ui<ai,α,k≥ai.(2)
Pi randomly splits Vi into z vectors {Vi(1),Vi(2),…,Vi(z)}, as follows:(27)Vi=vi1,vi2,vi3,…,vik,…,vis⟶Vi1=vi11,vi21,vi31,…,vik1,…,vis1,Vi2=vi12,vi22,vi32,…,vik2,…,vis2,⋮Viz=vi1z,vi2z,vi3z,…,vikz,…,visz,where allvik(j)(1≤j≤z,1≤k≤s) are random numbers that satisfy(28)vi1=∑j=1zvi1j,…,vis=∑j=1zvisj.(3)
Pi keeps his Vi(i) secret and sends Vi(j)(j≠i) to other z-1 parties separately. In the end, each party holds z vectors; that is, Pi holds V1(i),…,Vi(i),…,Vz(i) and adds the corresponding column vectors, denoted by Vi′={vi1′,vi2′,…,vis′}={(v11(i)+v21(i)+⋯+vz1(i)),(v12(i)+v22(i)+⋯+vz2(i)),…,(v1s(i)+v2s(i)+⋯+vzs(i))}.(4)
All parties publish theirVi′. According to ai, Pi adds all vjai′ (j=1,…,z) of Vj′, denoted by δi=(v1ai′+v2ai′+v3ai′+⋯+vzai′).(5)
Pi computes ord(ai)=δi/α as his order.


## 3.2.3. Accuracy and Security

(1)
In this protocol, we use the secret splitting method to split a vectorV into z vectors. Each party keeps his Vi(i) secret. Without Vi(i), others cannot conspire to compute Vi.
(2)
Protocol 2 does not require any encryption scheme based on computational assumptions, so it is information-theoretically secure.
(3)
P
i adds the ai-th column vectors of Vj′(j=1,…,z), and other parties do not know which column vector Pi selects.
(4)
In a particular case, ifPi holds the number 2 and his order is also 2, he confirms that someone holds the number 1, but he does not know who holds the number 1. This situation does not imply that the protocol is insecure because this information is what the function computed leaks. Even in the ideal SMC protocol, the TTP tells Pi that his rank is 2, the information also leaks because this is what the function to be computed leaks.
(5)
The protocol cannot be applied to the two-party situation, because, in this case,
in the execution of Protocol 2 for two parties, Alice splitsV1 to vectors {V1(1),V1(2)}, and Bob splits V2 to vectors {V2(1),V2(2)}. Alice sends V1(2) to Bob, and Bob sends V2(1) to Alice. Bob computes V2′=V2(2)+V1(2) and sends V2′ to Alice. Because Alice has the vectors V1(2) and V2(1), she can compute V2(2)=V2′-V1(2) and compute V2=V2(1)+V2(2), so she obtains Bob’s a2. Therefore, Protocol 2 is not applicable to the two-party GT problem.
(6)
In this protocol, we do not consider attacks in the transmitting process. If necessary, we can use the Paillier encryption scheme [34] to encrypt Vi(k) and Vi′, although this increases the computational and communication costs.
(7)
In fact, in many cases, limited parties take part in sorting their numbers. In cryptographic literatures, the multiparty refers 3 to 5 parties. There are few literatures that consider more than 10 parties. In addition, in our life, we sort 100 richest men of the world or compare the top 100 banks in the world or rank the top 500 companies all over the world at most. Therefore, the number of parties in the above cases does matter much.
(8)
Protocol 2 can resist collusion attacks, which is proved by the following Theorem4.The following theorem states the privacy-preserving property of the protocol.Theorem 4.
Protocol 2 for the multiparty GT problem is secure in the semihonest model.Proof.
In Protocol 2, even though some adversaries obtainPi’s z-1 vectors Vj(i)(j≠i), they cannot compute Vi. Because all vectors Vj(i)(j=1,…,z) sum to Vi, while Pi keeps Vi(i) secret, the adversaries cannot obtain Vi(i). Therefore, the security of Protocol 2 is the same as the security of a protocol with a TTP in the ideal SMC model. We prove the privacy-preserving property of Protocol 2 using the following formal proving method (Definition 2).
We consider the following cases.
Case 1. P1 does not participate in collusion, while other participants I(I⊆{P2,P3,…,Pz}) conspire to compute Pj’s Vj(Pj∉I). By executing Protocol 2, the set I can obtain {V2′,…,Vj-1′,Vj+1′,…,Vz′} and {ord(a2),…,ord(aj-1),ord(aj+1),…,ord(az)}. Since P1,Pj∉I,V1(1) and Vj(j) are private, the coconspirators I cannot obtain V1 and Vj. So they do not conspire aj. We can construct a simulator S such that (5) holds.(i)
By the result of the protocol, the coconspiratorsI choose V1(1)∗ and Vj(j)∗ such that(29)V11∗+V12+⋯+V1z+V2+⋯+Vj-1+Vjj∗+Vj1+⋯+Vjz+Vj+1+⋯+Vz=V.(ii)
The setI will execute the protocol Π, determining their viewIΠ as follows:(30)viewIΠV=I,view2ΠV,…,viewj-1ΠV,viewj+1ΠV,…,viewzΠV=V1′∗,V2′,…,Vj-1′,Vj′∗,Vj+1′,…,Vz′,V.(iii)
Let(31)SI,V2′,V3′,…,Vz′,fV=V1′,V2′,…,Vj-1′,Vj′,Vj+1′,…,Vz′,V.V1′∗≡cV1′,Vj′∗≡cVj′,SI,V2′,V3′,…,Vz′,fV≡cviewIΠV.Therefore, in this case, the protocol is secure.
Case 2. P1 and the participants I⊆{P2,P3,…,Pz} conspire to obtain the information of other participants I′={P1,P2,…,Pz}∖I.
Case 2.1. If I′=1, suppose Pi∈I′, Pi’s order ord(ai) except ai can be obtained, which is the same as the case mentioned above in part (4) and part (5) of Section 3.2.3. Even in the ideal SMC protocol, the TTP tells the orders of P1 and I, and P1 and I can conspire Pi’s order ord(ai). Therefore, the protocol does not leak more information than that the ideal SMC model leaks, and the protocol is secure.
Case 2.2. If I′={Pi,Pj}, Vi(i) and Vj(j) are private, and P1 and I cannot know Vi′ and Vj′, which is the same as Case 1. In this case, the protocol is secure. This is true for I′⩾2.
To sum up, in any case, there exists a simulatorS such that (5) holds, so Protocol 2 is secure.To help the readers understand the protocol, we give a toy example.ExampleInput. {(P1,5),(P2,3),(P3,8),(P4,7)},U={1, …,10}.Output. ord(i),i∈{5,3,8,7}.(1)
P1,…,P4 encode their number’s vectors as follows (set α=2):(32)x1=5,V1=0,0,0,0,2,2,2,2,2,2,x2=3,V2=0,0,2,2,2,2,2,2,2,2,x3=8,V3=0,0,0,0,0,0,0,2,2,2,x4=7,V4=0,0,0,0,0,0,2,2,2,2.(2)
P1,…,P4 split their own vector into four random vectors, respectively:(33)V1⟶V11=-5,-3,2,3,3,-1,-4,2,3,5V12=7,4,-5,6,2,-4,9,-2,1,3V13=2,-1,3,-2,4,5,4,1,2,-3V14=-4,0,0,-7,-7,2,-7,1,-4,-3.V2⟶V21=4,2,5,-7,-3,-5,6,1,0,1V22=-2,3,-1,6,1,2,-4,-5,-7,3V23=3,-6,2,3,2,5,-3,-2,4,-2V24=-5,1,-4,0,2,0,3,8,5,0.V3⟶V31=2,1,-3,-5,-2,2,0,0,6,-1V32=3,0,-2,0,-5,0,-4,0,-2,2V33=-3,2,5,-4,1,0,2,-1,-3,-2V34=-2,-3,0,9,6,-2,2,3,1,3.V4⟶V41=3,1,-2,-5,-3,-2,-1,0,-3,-4V42=2,3,-1,5,7,4,2,0,-3,2V43=-4,3,-2,-1,-5,2,1,2,3,1V44=-1,-7,5,1,1,-4,0,0,5,3.(3)
P1 keeps V1(1) secret and sends V1(2),V1(3),V1(4) to P2,P3,P4, respectively.P2 keeps V2(2) secret and sends V2(1),V2(3),V2(4) to P1,P3,P4, respectively.P3 keeps V3(3) secret and sends V3(1),V3(2),V3(4) to P1,P2,P4, respectively.P4 keeps V4(4) secret and sends V4(1),V4(2),V4(3) to P1,P2,P3, respectively.(4)
P1 holds V1(1),V2(1),V3(1),V4(1).P2 holds V2(2),V1(2),V3(2),V4(2).P3 holds V3(3),V1(3),V2(3),V4(3).P4 holds V4(4),V1(4),V2(4),V3(4).(5)
P1 computes V1′=V1(1)+V2(1)+V3(1)+V4(1)=(4,1,2,-14,-5,-6,1,3,6,1).P2 computes V2′=V2(2)+V1(2)+V3(2)+V4(2)=(10,10,-9,17,5,2,3,-7,-11,10).P3 computes V3′=V3(3)+V1(3)+V2(3)+V4(3)=(-2,-2,8,-4,2,12,4,0,6,-6).P4 computes V4′=V4(4)+V1(4)+V2(4)+V3(4)=(-12,-9,1,3,2,-4,-2,12,7,3).(6)
P1,P2,P3,P4 publish their V1′,V2′,V3′,V4′, respectively.(7)
Bya1=5, P1 selects V1′(5)=-5,V2′(5)=5,V3′(5)=2,V4′(5)=2.Bya2=3, P2 selects V1′(3)=2,V2′(3)=-9,V3′(3)=8,V4′(3)=1.Bya3=8, P3 selects V1′(8)=3,V2′(8)=-7,V3′(8)=0,V4′(8)=12.Bya1=3, P4 selects V1′(7)=1,V2′(7)=3,V3′(7)=4,V4′(7)=-2.(8)
P1 computes his rank ord(5)=(V1′(5)+V2′(5)+V3′(5)+V4′(5))/α=(-5+5+2+2)/2=2.P2 computes his rank ord(3)=(V1′(3)+V2′(3)+V3′(3)+V4′(3))/α=(2+(-9)+8+1)/2=1.P3 computes his rank ord(8)=(V1′(8)+V2′(8)+V3′(8)+V4′(8))/α=(3-7+0+12)/2=4.P4 computes his rank ord(7)=(V1′(7)+V2′(7)+V3′(7)+V4′(7))/α=(1+3+4+(-2))/2=3.


## 4. Computational and Communication Complexity

### 4.1. Computational Complexity

The computational complexity is an important measure for evaluating the efficiency of an SMC protocol.For secure two-party computation of the GT problem, we compare the computational complexity of Protocol 1 with that of the following typical solutions. The computational cost of [1] is exponential, which is impractical if the two numbers are very large. Furthermore, the protocol only compares x>y or x≤y. In [25], which also computes only x>y or x≤y, the computational cost is (4b+1lg⁡N+6b) modular multiplications, where b is the bit number of inputs and N is the modulus of the Paillier encryption scheme. In [26], Lin and Tzeng used the multiplicative homomorphism of the ElGamal encryption scheme to solve the GT problem for x>y or x≤y, the computational cost of which is (5blg⁡N+4b-6) modular multiplications. In addition, some researchers proposed SMC protocols for the GT problem based on linear secret sharing. Nishide and Ohta [29] constructed a simplified bit-decomposition protocol for the GT problem, which cannot determine x=y.In the proposed Protocol 1, Alice encodes her numberx into an s-dimensional vector. She encrypts s components of the encoding vector and computes s-time Paillier encryption and one-time Paillier decryption. Bob computes one-time Paillier encryption. The computational cost of each Paillier encryption or decryption is 2lg⁡N modular multiplications. Therefore, the computational overhead of Protocol 1 is (2s+2lg⁡N) modular multiplications, where s is the dimension of the encoding vector and N is the modulus of the Paillier encryption scheme. Table 2 compares the computational complexities of the proposed protocol and the existing protocols for the two-party GT problem.Table 2
Computational complexities for the two-party GT problem.
Schemes
Result
Modular multiplications
Yao [1]
>
,
≤
Exponential
Blake and Kolesnikov [25]
>
,
≤
4
b
+
1
lg
⁡
N
+
6
b
Lin and Tzeng [26]
>
,
≤
5
b
lg
⁡
N
+
4
b
-
6
Protocol 1
>
,
<
,
=
2
s
+
2
lg
⁡
N
b: bit number of inputs, N: modulus of the public-key encryption scheme, and s: encoding vector dimension.Table2 shows that Protocol 1 can determine whether x>y,x<y or x=y in one execution, whereas the other three solutions can only determine whether x>y or x≤y. In addition, s is much smaller than b, because s is the dimension of the encoding vector, whereas b is the bit number of inputs. For example, x=8388608 and U={107, 1587, 357862, 8178261, 8388608, 11587243, 654395824},α=2,β=3,γ=5; thus, its encoding vector is v=(2,2,2,2,5,3,3), so s=7. But the bit number of x=8388608 is b=log28388608=23. Therefore, Protocol 1 is more efficient than these three existing solutions.For secure multiparty computation of the GT problem (secure sorting problem), the solution of [1] is not suitable for the multiparty GT problem, and we compare the computational cost of Protocol 2 with that of [27, 28] which are typical protocols for the secure sorting problem. Paper [27] proposed an SMC protocol for the sorting problem based on the secret sharing scheme. The computational cost of [27] is llog⁡l (l is the length of the shared values) modular multiplications. Paper [28] proposed a sorting protocol based on the secret sharing method, with a computational cost of n2t(4t+3) modular multiplications, where n is the number of parties and t is the threshold value.In Protocol 2, we simply use the vectorization and the secret splitting methods, which requires(2ns+1)(n-1) additions, where s is the encoding vector dimension and n is the number of parties. For example, when n=4,s=10, the computational cost is 243 additions, which is much smaller than that using any public-key encryption scheme. Therefore, the computational cost of Protocol 2 is negligible. Table 3 summarizes these computational complexities for the multiparty GT problem.Table 3
Computational complexities for then-party GT problem.
Schemes
Modular multiplications
Damgard et al. [27]
l
log
⁡
l
Tang et al. [28]
n
2
t
(
4
t
+
3
)
Protocol 2
Negligible
n: the number of parties, t: the threshold value, and l: the length of the shared values.


### 4.2. Communication Complexity

The communication complexity, measured by the number of communicating rounds, is another important measure for evaluating the efficiency of an interactive protocol. For secure two-party computation of the GT problem, [1] requires two rounds, and [25] requires four rounds. Nishide and Ohta [29] constructed a simplified bit-decomposition protocol for the GT problem, whose communication cost is 15 rounds, whereas Protocol 1 requires only one round.For securen-party computation of the GT problem, [25] requires 2n(n-1) rounds, and [28] requires n(n+1) rounds. Protocol 2 also requires 2n(n-1) rounds.Table4 summarizes the communication complexities of these schemes for both types of the GT problem.Table 4
The communication complexities for the GT problem.
Schemes
Two-party
n
-
p
a
r
t
y
Yao [1]
2
—
Blake and Kolesnikov [25]
4
2
n
(
n
-
1
)
Nishide and Ohta [29]
15
—
Tang et al. [28]
—
n
(
n
+
1
)
Protocol 1
1
—
Protocol 2
—
2
n
(
n
-
1
)
n: the number of parties.


## 4.1. Computational Complexity

The computational complexity is an important measure for evaluating the efficiency of an SMC protocol.For secure two-party computation of the GT problem, we compare the computational complexity of Protocol 1 with that of the following typical solutions. The computational cost of [1] is exponential, which is impractical if the two numbers are very large. Furthermore, the protocol only compares x>y or x≤y. In [25], which also computes only x>y or x≤y, the computational cost is (4b+1lg⁡N+6b) modular multiplications, where b is the bit number of inputs and N is the modulus of the Paillier encryption scheme. In [26], Lin and Tzeng used the multiplicative homomorphism of the ElGamal encryption scheme to solve the GT problem for x>y or x≤y, the computational cost of which is (5blg⁡N+4b-6) modular multiplications. In addition, some researchers proposed SMC protocols for the GT problem based on linear secret sharing. Nishide and Ohta [29] constructed a simplified bit-decomposition protocol for the GT problem, which cannot determine x=y.In the proposed Protocol 1, Alice encodes her numberx into an s-dimensional vector. She encrypts s components of the encoding vector and computes s-time Paillier encryption and one-time Paillier decryption. Bob computes one-time Paillier encryption. The computational cost of each Paillier encryption or decryption is 2lg⁡N modular multiplications. Therefore, the computational overhead of Protocol 1 is (2s+2lg⁡N) modular multiplications, where s is the dimension of the encoding vector and N is the modulus of the Paillier encryption scheme. Table 2 compares the computational complexities of the proposed protocol and the existing protocols for the two-party GT problem.Table 2
Computational complexities for the two-party GT problem.
Schemes
Result
Modular multiplications
Yao [1]
>
,
≤
Exponential
Blake and Kolesnikov [25]
>
,
≤
4
b
+
1
lg
⁡
N
+
6
b
Lin and Tzeng [26]
>
,
≤
5
b
lg
⁡
N
+
4
b
-
6
Protocol 1
>
,
<
,
=
2
s
+
2
lg
⁡
N
b: bit number of inputs, N: modulus of the public-key encryption scheme, and s: encoding vector dimension.Table2 shows that Protocol 1 can determine whether x>y,x<y or x=y in one execution, whereas the other three solutions can only determine whether x>y or x≤y. In addition, s is much smaller than b, because s is the dimension of the encoding vector, whereas b is the bit number of inputs. For example, x=8388608 and U={107, 1587, 357862, 8178261, 8388608, 11587243, 654395824},α=2,β=3,γ=5; thus, its encoding vector is v=(2,2,2,2,5,3,3), so s=7. But the bit number of x=8388608 is b=log28388608=23. Therefore, Protocol 1 is more efficient than these three existing solutions.For secure multiparty computation of the GT problem (secure sorting problem), the solution of [1] is not suitable for the multiparty GT problem, and we compare the computational cost of Protocol 2 with that of [27, 28] which are typical protocols for the secure sorting problem. Paper [27] proposed an SMC protocol for the sorting problem based on the secret sharing scheme. The computational cost of [27] is llog⁡l (l is the length of the shared values) modular multiplications. Paper [28] proposed a sorting protocol based on the secret sharing method, with a computational cost of n2t(4t+3) modular multiplications, where n is the number of parties and t is the threshold value.In Protocol 2, we simply use the vectorization and the secret splitting methods, which requires(2ns+1)(n-1) additions, where s is the encoding vector dimension and n is the number of parties. For example, when n=4,s=10, the computational cost is 243 additions, which is much smaller than that using any public-key encryption scheme. Therefore, the computational cost of Protocol 2 is negligible. Table 3 summarizes these computational complexities for the multiparty GT problem.Table 3
Computational complexities for then-party GT problem.
Schemes
Modular multiplications
Damgard et al. [27]
l
log
⁡
l
Tang et al. [28]
n
2
t
(
4
t
+
3
)
Protocol 2
Negligible
n: the number of parties, t: the threshold value, and l: the length of the shared values.


## 4.2. Communication Complexity

The communication complexity, measured by the number of communicating rounds, is another important measure for evaluating the efficiency of an interactive protocol. For secure two-party computation of the GT problem, [1] requires two rounds, and [25] requires four rounds. Nishide and Ohta [29] constructed a simplified bit-decomposition protocol for the GT problem, whose communication cost is 15 rounds, whereas Protocol 1 requires only one round.For securen-party computation of the GT problem, [25] requires 2n(n-1) rounds, and [28] requires n(n+1) rounds. Protocol 2 also requires 2n(n-1) rounds.Table4 summarizes the communication complexities of these schemes for both types of the GT problem.Table 4
The communication complexities for the GT problem.
Schemes
Two-party
n
-
p
a
r
t
y
Yao [1]
2
—
Blake and Kolesnikov [25]
4
2
n
(
n
-
1
)
Nishide and Ohta [29]
15
—
Tang et al. [28]
—
n
(
n
+
1
)
Protocol 1
1
—
Protocol 2
—
2
n
(
n
-
1
)
n: the number of parties.


## 5. Conclusion

In this work, we propose the SMC protocols to solve the two-party and multiparty GT problem. Using the Paillier encryption scheme and the vectorization method, we construct an SMC protocol for solving the two-party GT problem which can determinex>y,x<y,x=y in one execution. To efficiently solve the multiparty GT problem (secure sorting problem), we use the vectorization method to transform private numbers into vectors and use the secret splitting method to resist collusion attacks without any encryption scheme based on computational assumptions. This protocol is information-theoretically secure. The simulation paradigm proves the privacy-preserving property of the protocols in the semihonest model. Comparing the computational and communication complexities of our protocols with that of the existing solutions, our protocols are efficient for practical applications and easily implemented.



---

*Source: 5207386-2017-05-25.xml*