# Research on the Millionaires’ Problem under the Malicious Model Based on the Elliptic Curve Cryptography

Authors: Xin Liu; Yang Xu; Gang Xu; Baoshan Li
Journal: Security and Communication Networks
 (2022)

---

## Abstract

With the rapid development of blockchain, big data, cloud computing, and artificial intelligence, the security of multisource data collaborative computing has become increasingly prominent. Secure multiparty computing has become the core technology of privacy collaborative computing. Millionaires’ problem is the cornerstone of secure multiparty computation. Firstly, this paper proposes a 0-1 coding rule, which is used to solve the millionaires’ problem under the semihonest model. Aiming at the possible malicious behaviors of the protocol under the semihonest model, the millionaires’ problem protocol under the malicious model based on the elliptic curve cryptography is designed by using cryptographic tools such as the zero-knowledge proof and the cut-choose method. This protocol not only can effectively solve the millionaires’ problem but also can safely and effectively prevent malicious behaviors. Meanwhile, the security ordering designed by the protocol can be effectively applied to a quality evaluation in the blockchain.


---

## Body

## 1. Introduction

Secure multiparty computation (SMC) is the core technology to achieve collaborative computing for the privacy of multisource data in recent years. The idea of SMC is proposed by Professor Yao Qizhi in 1982 [1], and then Goldreich [2, 3] began to do more in-depth research on SMC. SMC has been widely used in the blockchain [4–6], data mining [7–9], privacy computing [10, 11], medical [12, 13].The millionaires’ problem is one of the most classic problems in SMC. Many cryptographers have been working on it. Reference [14] presents a protocol for solving the millionaires’ problem based on the exchange cryptosystem, oblivious transfer method. Based on the Goldwasser–Micali (GM) cryptography, reference [15] proposed a protocol to solve the problem of socialist millionaires. Reference [16] proposed a protocol to solve the problem of the millionaires’ problem by using the shift registers and the property of probability encryption. Reference [17] presents a protocol based on the Paillier cryptosystem. The existing schemes have the disadvantage of inefficiency, and most of them are only suitable for the semihonest model and cannot resist malicious attacks. To solve the above problems, this paper studies the millionaires’ problem under the malicious model in depth and presents the millionaires’ problem protocol based on the elliptic curve cryptography.Elliptic curve cryptography (ECC) is a traditional encryption method that has the advantage of high computational efficiency and is based on the elliptic curve discrete logarithm problem, and it has been widely used because of its short key [18–20]. Using ECC, the protocol designed in this paper has more efficient operation efficiency and security. The main contributions are as follows:(1)
First, a 0-1 encoding rule for ECC is proposed, and then a millionaires’ problem protocol under the semihonest model is designed(2)
With the help of some cryptographic tools such as the zero-knowledge proof and cut-choose method, a protocol is designed to resist the attacks of malicious opponents(3)
Finally, an ideal-practical example method is used to prove the security of the protocol under the malicious model


## 2. Preliminary Knowledge

### 2.1. Elliptic Curve Cryptography

Elliptic curve cryptography (ECC) is a public-key cryptosystem based on discrete logarithmic problems of point groups of elliptic curves. For example, an elliptic curve is defined asy2=x3−x, two points P and Q on the curve, a straight line through P and Q, an intersecting elliptic curve at R′ point, and a line perpendicular to X axis through R′ point. An intersecting elliptic curve at another point R is defined as P+Q=R, as shown in Figure 1.Figure 1
Elliptic curve operation, definedP+Q=R.WhenP=Q, the tangent of the point P intersects R′, and then the point R′ makes a straight line perpendicular to the X-axis, intersecting the elliptic curve at another point R. When k identical P are added, they are counted as kP, such as P+P+P+P=P+3P=4P. Elliptic curves make use of the mathematical problem of discrete logarithm in the above operations, that is, when K=kP, P and K are known, and K is easily obtained. But it is very difficult to find P and K when K is known.In cryptography systems, if there is an elliptic curveEpa,b and a base point G, a random number k is generated as the private key, and the datum is computed k times to get the public key K=kG. In ECC, the private key k is easy to get the public key K; the public key K cannot get the private key k.Compared with the traditional public key algorithms, elliptic curve cryptography has the following advantages [19, 20]:(1)
higher security performance. For example, 160 bit ECC has the same security strength as 1024 bit RSA and DSA algorithms.(2)
small amount of computation and fast processing speed. ECC is much faster than RSA and DSA in the processing speed of private key (decryption and signature).(3)
The storage space occupation is small. Compared with RSA and DSA, the key size and system parameters of ECC are much smaller, so the storage space occupation is much smaller.(4)
ECC has a wide application prospect because of its low bandwidth requirements.


#### 2.1.1. ECC Encryption

(1)
Elliptic curveEpa,b, a base point G, private key k, and public key K=kG(2)
Encode a plaintexta to a point M on the elliptic curve Epa,b and select a random number r<n (where n is the order of base point G)(3)
Encryption:C1=M+rK, C2=rG(4)
Decryption:C1−kC2=M+rK−krG=M+rK−kG=M


#### 2.1.2. Additive Homomorphism of ECC

(1)
Encryption: encode a plaintextai0<i≤m onto a point Mi of the elliptic curve Epa,b, use the private key k to generate the public key K=kG, select a random number ri<n, and calculate C1i=Mi+rK and C2i=rG(2)
Addition operation: all ciphertexts are added to obtain ciphertexts∑i=1mC1i∑i=1mC2i, where ∑i=1mC1i=C11+C12+⋯C1m and ∑i=1mC2i=C21+C22+⋯C2m(3)
Decryption: compute∑i=1mC1i−k∑i=1mC2i=∑i=1mMi+K∑i=1mri−kG∑i=1mri=∑i=1mMi and finally decode ∑i=1mMi to obtain the plaintext ∑i=1mai


### 2.2. Zero-Knowledge Proof

Zero-knowledge proof [21] means that the prover can make the verifier believe that a conclusion is correct without providing any useful information to the verifier. The prover proves to the verifier and makes him believe that he knows or owns a certain message, but the certification process cannot disclose any information about the proved message to the verifier. A large number of facts have proved that the zero-knowledge proof is very useful in cryptography. If the zero-knowledge proof can be used for verification, many problems can be effectively solved.


### 2.3. Cut-Choose Method

In cryptography, we encrypt the information that can be sent inton messages using n different random numbers. The receiver selects n/2 of them to verify their correctness and then selects one of the remaining n/2 for the remaining protocol steps. The cut-choose method can minimize the malicious input probability of the protocol and make the transmission of information more secure [22].


### 2.4. Security Definition of a Protocol under the Malicious Model

To prove that a protocol is secure under the malicious model, it must satisfy the security definition under the malicious model. If the actual protocol achieves the same security as the ideal protocol, then the protocol is secure [3].Alice ownsx, and Bob owns y. They compare by calculating function fx,y=f1x,y,f2x,y with a trusted third party (TTP). At the end of the protocol, both parties get f1x,y and f2x,y without leaking x and y. The ideal model is as follows:(1)
The honest participant always providesx or y to the TTP, while the malicious participant may decide not to execute the protocol based on x or y or provide a false input x′ or y′ to the TTP when the protocol is executed.(2)
TTP sends the result to Alice. After TTP gets input pairx,y, fx,y is calculated, and f1x,y is sent to Alice; otherwise, the special symbols ⊥ are sent to Alice.(3)
TTP sends the result to Bob, and if Alice is a malicious participant, it may no longer contact with TTP after receivingf1x,y. In this case, TTP sends Bob a special symbol ⊥; otherwise, TTP sends f2x,y to Bob.The ideal protocol is the safest protocol because participants cannot get any information except theirfix,y from TTP. If an actual protocol achieves the same security as the ideal protocol, we say that the actual protocol is secure.If the participant in the ideal model has an auxiliary informationz and the process of calculating Fx,y in combination with policy B¯ is IDEALF,B¯zx,y, it is defined as the adversary evenly choosing a random number r and to make IDEALF,B¯zx,y=γx,y,z,r, where γx,y,z,r is defined as follows (note: if both parties under the malicious model are malicious, it is impossible to design an SMC protocol; we do not consider this case):(1)
If Alice is honest, there isγx,y,z,r=f1x,y′,B2y,z,r,f2x,y′, where y′=B2y,z,r.(2)
If Bob is honest:(1)γx,y,z,r=B1x,z,r,f1x′,y,⊥,⊥,if:B1x,z,r,f1x′,y=⊥,B1x,z,r,f1x′,y,f2x′,y,otherwise.In both cases,x′=B1x,z,r.Definition 1.
Security for the malicious model.
If, in the ideal model, an acceptable policy pairA¯=A1,A2 in the actual protocol can be found, there is an acceptable policy pair B¯=B1,B2, such that(2)IDEALF,B¯zx,yx,y,z≡cREALA¯zx,yx,y,z.
So this protocol can calculateF securely.


## 2.1. Elliptic Curve Cryptography

Elliptic curve cryptography (ECC) is a public-key cryptosystem based on discrete logarithmic problems of point groups of elliptic curves. For example, an elliptic curve is defined asy2=x3−x, two points P and Q on the curve, a straight line through P and Q, an intersecting elliptic curve at R′ point, and a line perpendicular to X axis through R′ point. An intersecting elliptic curve at another point R is defined as P+Q=R, as shown in Figure 1.Figure 1
Elliptic curve operation, definedP+Q=R.WhenP=Q, the tangent of the point P intersects R′, and then the point R′ makes a straight line perpendicular to the X-axis, intersecting the elliptic curve at another point R. When k identical P are added, they are counted as kP, such as P+P+P+P=P+3P=4P. Elliptic curves make use of the mathematical problem of discrete logarithm in the above operations, that is, when K=kP, P and K are known, and K is easily obtained. But it is very difficult to find P and K when K is known.In cryptography systems, if there is an elliptic curveEpa,b and a base point G, a random number k is generated as the private key, and the datum is computed k times to get the public key K=kG. In ECC, the private key k is easy to get the public key K; the public key K cannot get the private key k.Compared with the traditional public key algorithms, elliptic curve cryptography has the following advantages [19, 20]:(1)
higher security performance. For example, 160 bit ECC has the same security strength as 1024 bit RSA and DSA algorithms.(2)
small amount of computation and fast processing speed. ECC is much faster than RSA and DSA in the processing speed of private key (decryption and signature).(3)
The storage space occupation is small. Compared with RSA and DSA, the key size and system parameters of ECC are much smaller, so the storage space occupation is much smaller.(4)
ECC has a wide application prospect because of its low bandwidth requirements.


### 2.1.1. ECC Encryption

(1)
Elliptic curveEpa,b, a base point G, private key k, and public key K=kG(2)
Encode a plaintexta to a point M on the elliptic curve Epa,b and select a random number r<n (where n is the order of base point G)(3)
Encryption:C1=M+rK, C2=rG(4)
Decryption:C1−kC2=M+rK−krG=M+rK−kG=M


### 2.1.2. Additive Homomorphism of ECC

(1)
Encryption: encode a plaintextai0<i≤m onto a point Mi of the elliptic curve Epa,b, use the private key k to generate the public key K=kG, select a random number ri<n, and calculate C1i=Mi+rK and C2i=rG(2)
Addition operation: all ciphertexts are added to obtain ciphertexts∑i=1mC1i∑i=1mC2i, where ∑i=1mC1i=C11+C12+⋯C1m and ∑i=1mC2i=C21+C22+⋯C2m(3)
Decryption: compute∑i=1mC1i−k∑i=1mC2i=∑i=1mMi+K∑i=1mri−kG∑i=1mri=∑i=1mMi and finally decode ∑i=1mMi to obtain the plaintext ∑i=1mai


## 2.1.1. ECC Encryption

(1)
Elliptic curveEpa,b, a base point G, private key k, and public key K=kG(2)
Encode a plaintexta to a point M on the elliptic curve Epa,b and select a random number r<n (where n is the order of base point G)(3)
Encryption:C1=M+rK, C2=rG(4)
Decryption:C1−kC2=M+rK−krG=M+rK−kG=M


## 2.1.2. Additive Homomorphism of ECC

(1)
Encryption: encode a plaintextai0<i≤m onto a point Mi of the elliptic curve Epa,b, use the private key k to generate the public key K=kG, select a random number ri<n, and calculate C1i=Mi+rK and C2i=rG(2)
Addition operation: all ciphertexts are added to obtain ciphertexts∑i=1mC1i∑i=1mC2i, where ∑i=1mC1i=C11+C12+⋯C1m and ∑i=1mC2i=C21+C22+⋯C2m(3)
Decryption: compute∑i=1mC1i−k∑i=1mC2i=∑i=1mMi+K∑i=1mri−kG∑i=1mri=∑i=1mMi and finally decode ∑i=1mMi to obtain the plaintext ∑i=1mai


## 2.2. Zero-Knowledge Proof

Zero-knowledge proof [21] means that the prover can make the verifier believe that a conclusion is correct without providing any useful information to the verifier. The prover proves to the verifier and makes him believe that he knows or owns a certain message, but the certification process cannot disclose any information about the proved message to the verifier. A large number of facts have proved that the zero-knowledge proof is very useful in cryptography. If the zero-knowledge proof can be used for verification, many problems can be effectively solved.


## 2.3. Cut-Choose Method

In cryptography, we encrypt the information that can be sent inton messages using n different random numbers. The receiver selects n/2 of them to verify their correctness and then selects one of the remaining n/2 for the remaining protocol steps. The cut-choose method can minimize the malicious input probability of the protocol and make the transmission of information more secure [22].


## 2.4. Security Definition of a Protocol under the Malicious Model

To prove that a protocol is secure under the malicious model, it must satisfy the security definition under the malicious model. If the actual protocol achieves the same security as the ideal protocol, then the protocol is secure [3].Alice ownsx, and Bob owns y. They compare by calculating function fx,y=f1x,y,f2x,y with a trusted third party (TTP). At the end of the protocol, both parties get f1x,y and f2x,y without leaking x and y. The ideal model is as follows:(1)
The honest participant always providesx or y to the TTP, while the malicious participant may decide not to execute the protocol based on x or y or provide a false input x′ or y′ to the TTP when the protocol is executed.(2)
TTP sends the result to Alice. After TTP gets input pairx,y, fx,y is calculated, and f1x,y is sent to Alice; otherwise, the special symbols ⊥ are sent to Alice.(3)
TTP sends the result to Bob, and if Alice is a malicious participant, it may no longer contact with TTP after receivingf1x,y. In this case, TTP sends Bob a special symbol ⊥; otherwise, TTP sends f2x,y to Bob.The ideal protocol is the safest protocol because participants cannot get any information except theirfix,y from TTP. If an actual protocol achieves the same security as the ideal protocol, we say that the actual protocol is secure.If the participant in the ideal model has an auxiliary informationz and the process of calculating Fx,y in combination with policy B¯ is IDEALF,B¯zx,y, it is defined as the adversary evenly choosing a random number r and to make IDEALF,B¯zx,y=γx,y,z,r, where γx,y,z,r is defined as follows (note: if both parties under the malicious model are malicious, it is impossible to design an SMC protocol; we do not consider this case):(1)
If Alice is honest, there isγx,y,z,r=f1x,y′,B2y,z,r,f2x,y′, where y′=B2y,z,r.(2)
If Bob is honest:(1)γx,y,z,r=B1x,z,r,f1x′,y,⊥,⊥,if:B1x,z,r,f1x′,y=⊥,B1x,z,r,f1x′,y,f2x′,y,otherwise.In both cases,x′=B1x,z,r.Definition 1.
Security for the malicious model.
If, in the ideal model, an acceptable policy pairA¯=A1,A2 in the actual protocol can be found, there is an acceptable policy pair B¯=B1,B2, such that(2)IDEALF,B¯zx,yx,y,z≡cREALA¯zx,yx,y,z.
So this protocol can calculateF securely.


## 3. The Protocol under the Semihonest Model

### 3.1. Solution Ideas

Alice ownsx, and Bob owns y. Alice and Bob want to compare the relationship: x>y, x=y, x<y, while they do not want to leak their x and y, respectively. The solution is to code x and y as a set consisting of 1 and 0 and use ECC to design an efficient protocol.The 0-1 encoding rule: encodex into a set X=a1,a2,…,am, where a1<a2<⋯<am and(3)ai=1,i=x;0,i≠x.The comparison rule: based on the position ofy in X: if x>y, then ∑i=1y−1ai+∑i=1yai=0; if x=y, then ∑i=1y−1ai+∑i=1yai=1; and if x<y, then ∑i=1y−1ai+∑i=1yai=2. Define the following formula to judge the relationship between x and y:(4)Px,y=0,x>y;1x=y;2,x<y.For example: Alice’s data is 5, which is encoded into a new setX=0,0,0,0,1,0,0, and Bob calculates with three different data y=2,5,7. This is shown in Table 1.Table 1
The 0-1 encoding. Data comparison results of Alice and Bob.
Alice’s dataNew set for encodingBob’s dataCalculatew=∑i=1y−1ai+∑i=1yaiComparison results5X=0,0,0,0,1,0,02w=0+0=0x>y5w=0+1=1x=y7w=1+1=2x<y


### 3.2. Specific Protocol

Alice owns datax, and Bob owns data y, and both parties compute Px,y securely to determine the relationship. Using the above 0-1 encoding rule, Algorithm 1 under the semihonest model is designed based on ECC homologous encryption.Algorithm 1: Judgement under the semihonest model.
Input: Alice owns datax, and Bob owns data y.Output:Px,y.(1)
Alice encodesx into a set X=a1,a2,…,am, where a1<a2<⋯<am and ai=1,i=k;0,i≠k..(2)
Alice chooses an elliptic curveEp, the base point G, and the private key k; then calculates kG=K as the public key K; and publishes the public key K and the base point G.(3)
Alice encodes the plaintextX=a1,a2,…,am one by one onto point Mi1≤i≤m on the elliptic curve Ep (the encoding method is not unique [18], which is not discussed here). She chooses m random numbers ri and encrypts each element Mi one by one using the public key K of ECC, that is, EMi=C1i,C2i, C1i=Mi+riK+C2i=riG. She gets EX=EM1,EM2,…,EMm, which is sent to Bob.(4)
Bob calculatesEW=C1,C2 based on the y position of data in EX, where C1=∑i=1y−1C1i+∑i=1y−1C1i and C2=∑i=1y−1C2i+∑i=1yC2i. He sends EW=C1,C2 to Alice.(5)
Alice decryptsW with the private key k to get W, where C1−kC2=∑i=1y−1Mi+∑i=1yMi=W, and decodes the point W to get w=∑i=0y−1ai+∑i=0yai. If w=0, x>y; if w=1, x=y; and if w=2, x<y. Alice tells Bob the result.The protocol ends.Algorithm 1 is secure under the semihonest model, but if one of Alice and Bob is a malicious participant, the protocol is no longer secure. The following section will improve the protocol to make it safe and feasible under the malicious model.


## 3.1. Solution Ideas

Alice ownsx, and Bob owns y. Alice and Bob want to compare the relationship: x>y, x=y, x<y, while they do not want to leak their x and y, respectively. The solution is to code x and y as a set consisting of 1 and 0 and use ECC to design an efficient protocol.The 0-1 encoding rule: encodex into a set X=a1,a2,…,am, where a1<a2<⋯<am and(3)ai=1,i=x;0,i≠x.The comparison rule: based on the position ofy in X: if x>y, then ∑i=1y−1ai+∑i=1yai=0; if x=y, then ∑i=1y−1ai+∑i=1yai=1; and if x<y, then ∑i=1y−1ai+∑i=1yai=2. Define the following formula to judge the relationship between x and y:(4)Px,y=0,x>y;1x=y;2,x<y.For example: Alice’s data is 5, which is encoded into a new setX=0,0,0,0,1,0,0, and Bob calculates with three different data y=2,5,7. This is shown in Table 1.Table 1
The 0-1 encoding. Data comparison results of Alice and Bob.
Alice’s dataNew set for encodingBob’s dataCalculatew=∑i=1y−1ai+∑i=1yaiComparison results5X=0,0,0,0,1,0,02w=0+0=0x>y5w=0+1=1x=y7w=1+1=2x<y


## 3.2. Specific Protocol

Alice owns datax, and Bob owns data y, and both parties compute Px,y securely to determine the relationship. Using the above 0-1 encoding rule, Algorithm 1 under the semihonest model is designed based on ECC homologous encryption.Algorithm 1: Judgement under the semihonest model.
Input: Alice owns datax, and Bob owns data y.Output:Px,y.(1)
Alice encodesx into a set X=a1,a2,…,am, where a1<a2<⋯<am and ai=1,i=k;0,i≠k..(2)
Alice chooses an elliptic curveEp, the base point G, and the private key k; then calculates kG=K as the public key K; and publishes the public key K and the base point G.(3)
Alice encodes the plaintextX=a1,a2,…,am one by one onto point Mi1≤i≤m on the elliptic curve Ep (the encoding method is not unique [18], which is not discussed here). She chooses m random numbers ri and encrypts each element Mi one by one using the public key K of ECC, that is, EMi=C1i,C2i, C1i=Mi+riK+C2i=riG. She gets EX=EM1,EM2,…,EMm, which is sent to Bob.(4)
Bob calculatesEW=C1,C2 based on the y position of data in EX, where C1=∑i=1y−1C1i+∑i=1y−1C1i and C2=∑i=1y−1C2i+∑i=1yC2i. He sends EW=C1,C2 to Alice.(5)
Alice decryptsW with the private key k to get W, where C1−kC2=∑i=1y−1Mi+∑i=1yMi=W, and decodes the point W to get w=∑i=0y−1ai+∑i=0yai. If w=0, x>y; if w=1, x=y; and if w=2, x<y. Alice tells Bob the result.The protocol ends.Algorithm 1 is secure under the semihonest model, but if one of Alice and Bob is a malicious participant, the protocol is no longer secure. The following section will improve the protocol to make it safe and feasible under the malicious model.


## 4. The Protocol under the Malicious Model

### 4.1. Solution Ideas

Firstly, we analyze the possible malicious attacks in Algorithm 1. Then the solutions to these malicious attacks are proposed. Finally, the possible malicious attacks cannot be implemented or found when they are committed. The following malicious attacks may exist in Algorithm 1 as follows:(1)
In Algorithm 1, Alice has both the public keyK and the private key k, but Bob only has the public key K, so the final result can only be calculated unilaterally by Alice, which is unfair to Bob. (2) In steps 3 and 4, if the ciphertext sent by Alice and Bob to each other is wrong so that neither party can get the correct result. (3) In step 5, Alice tells Bob the wrong result after decrypting, which leads to a wrong conclusion for Bob. For the above malicious attacks, a new protocol must be designed to find or render them impossible to implement. (Note: Before designing the protocol under the malicious model, we need to be clear that some malicious behaviors cannot be prevented in the ideal protocol. For example, if you enter wrong inputs in the ideal model, no matter how you detect and verify, you cannot get the correct results; similarly, if you refuse to carry out the protocol, we cannot get the results, either. Therefore, we will not consider the following behaviors when designing the protocol under the malicious model: (1) refusing to carry out the protocol, (2) inputting false data, and (3) one party terminating the protocol after obtaining the information he wants to prevent other participants from carrying out the protocol.)To design a secure, fair, and correct protocol under the malicious model, the solution is to use cryptographic tools such as the zero-knowledge proof and cut-choose method to prevent malicious attacks that may exist in Algorithm 1. The final results are calculated by both parties at the same time.


### 4.2. Specific Protocol

Based on the malicious attacks that may occur in Algorithm 1 under the semihonest model, we use the above 0-1 encoding rule to design the millionaires’ problem algorithm under the malicious model using the zero-knowledge proof and cut-choose method. The framework of Algorithm 2 under the malicious model is outlined in Algorithm 3.Algorithm 2: Judgement under the malicious model.
Input: Alice ownsx, and Bob owns y.Output:Px,y.Prepare:(1)
Alice and Bob jointly select an elliptic curveEp and a base point G. Alice and Bob separately select their own private key k1,k2k1,k2>0. Then Alice and Bob calculate their public keys K1=k1G and K2=k2G and u=aK1 and v=bK2, respectively. Finally, Alice and Bob exchange K1,u and K2,v.Alice and Bob construct their own new setsX=a1,a2,…,am and Y=b1,b2,…,bm through x and y, where: ai=1,i=x;0,i≠x.bi=1,i=y;0,i≠y..Start:(1)
Alice encodes the plaintextX=a1,a2,…,am onto the point Mia1≤i≤m of the elliptic curve Epa,b; selects m random numbers ria; encrypts each element Mia one by one with the public key K1, that is, calculates the EMia=C1ia,C2ia, where: C1ia=Mia+riaK1 and C2ia=riaG; obtains EX=EM1a,EM2a,…,EMma; and finally, sends EX to Bob.(2)
Bob encodes the plaintextY=b1,b2,…,bm onto the point Mib1≤i≤m of the elliptic curve Epa,b; selects m random numbers rib; encrypts each element Mib one by one by using the public key K2, that is, calculates the EMib=C1ib,C2ib, where: C1ib=Mib+ribK2 and C2ib=ribG; obtains EY=EM1b,EM2b,…,EM3b; and finally, sends EY to Alice.(3)
Alice calculatesEQ=C1,C2 according to the position of data x in EY, where C1=∑i=1x−1C1ib+∑i=1xC1ib and C2=∑i=1x−1C2ib+∑i=1xC2ib, and sends EQ to Bob.Bob calculatesEW=C1′,C2′ according to the position of data y in EX, where C1′=∑i=1y−1C1ia+∑i=1yC1ia and C2′=∑i=1y−1C2ia+∑i=1yC2ia, and sends EW to Alice.(4)
Alice decryptsEW using the private key k1, that is, calculates C1−k1C2=∑i=0x−1Mib+∑i=0xMib=W to obtain W point. Bob decrypts EQ using the private key k2, that is, calculates C1′−k2C2′=∑i=0y−1Mia+∑i=0yMia=Q to obtain point Q.(5)
Alice selectsm random numbers di (0≤i≤m) to calculate c1ai,c2ai=diW+K1,W+diW+aG. Bob selects m random numbers fi (0≤i≤m) to calculate c1bi,c2bi=fiQ+K2,Q+fiQ+bG. Finally, Alice and Bob exchange c1ai,c2ai and c1bi,c2bi.(6)
With the help of the cut-choose method, Alice randomly selects them/2 groups from the m groups c1bi,c2bi sent by Bob and publishes it and requires Bob to publish the corresponding fiQ. Alice verifies: fiQ+K2=c1bi. If the verification is passed, they continue the protocol or else terminate.Bob randomly selects them/2 groups from the m group c1ai,c2ai sent by Alice and publishes it and requires Alice to publish the corresponding diW. Bob verifies: diQ+K1=c1ai. If the verification is passed, they continue the protocol or else terminate.(7)
Alice and Bob randomly select onec1bi,c2bi and c1ai,c2ai from the remaining c1bi,c2bi and c1ai,c2ai, respectively. Meanwhile, Alice selects two random numbers h and p1, and Bob selects two random numbers l and p2. Alice calculates cb=hc2bj−c1bj−W+K2=hQ−W+hlG, P1=p1G, λb=p1K2; Bob calculates ca=lc2ai−c1ai−Q+K1=lW−Q+hlG, P2=p2G, and λa=p2K1. Then Alice and Bob send cb+P1 and ca+P2 to each other.(8)
After both parties receive information from each other, Alice calculatesωa=k1ca+P2 and ma=k1ca and sends them to Bob. Bob calculates ωb=k2cb+P1 and mb=k2cb and sends them to Alice.(9)
Alice uses the zero-knowledge proof to verify that themb sent by Bob is correct, that is, to prove that Bob does get the mb by multiplying his private key k2 with his cb, that is, to judge whether mb=ωb−λb is true. Bob uses the zero-knowledge proof to verify that the ma sent by Alice is correct, that is, to prove that Alice does get the ma by multiplying her private key k1 with her ca, that is, to judge whether ma=ωa−λa is true. The party who fails is malicious.(10)
Alice can getk2hQ−W by calculating mb−hv. If k2hQ−W=0, then Q=W; Bob can get k1lW−Q by calculating ma−lu. If k1lW−Q=0, then Q=W. If Q=W, it proves that the results required by both parties are correct and identical; otherwise, the protocol shall be terminated.(11)
Finally, Alice and Bob get∑i=0x−1bi+∑i=0xbi=w and ∑i=0y−1ai+∑i=0yai=q by decoding points W and Q, respectively. If q,w=0, then x>y; if q,w=1, then x=y; and if q,w=2, then x<y.The protocol ends.A specific protocol is as follows:Algorithm 3: Judgement under the malicious model.
Input:x: Alice’s input; y: Bob’s input; G: the base point of the elliptic curve Ep; Code: encode inputs into a m degree 0-1 codes; k1: Alice’s private key; k2: Bob’s private key; E: encrypt. h,p1: Alice’s random number; and l,p2: Bob’s random number(1)
K1=k1GK2=k2G(2)
u=aK1v=bK2(3)
P1=p1GP2=p2G(4)
λb=p1K2λa=p2K1(5)
Codex=X=a1,a2,…,am(6)
C1ia=Mia+riaK1C2ia=riaG(7)
EMia=C1ia,C2ia(8)
EX=EM1a,EM2a,…,EMma(9)
Codey=Y=b1,b2,⋯,bm(10)
C1ib=Mib+ribK2C2ib=ribG(11)
EMib=C1ib,C2ib(12)
EY=EM1b,EM2b,…,EM3b(13)
ExchangeK1,EX,u, K2,EY,v.(14)
C1=∑i=1x−1C1ib+∑i=1xC1ibC2=∑i=1x−1C2ib+∑i=1xC2ib(15)
EQ=C1,C2(16)
C2′=∑i=1y−1C2ia+∑i=1yC2ia(17)
EW=C1′,C2′(18)
ExchangeEQ, EW(19)
DEW=WDEQ=Q(20)
c1ai,c2ai=diW+K1,W+diW+aGand c1bi,c2bi=fiQ+K2,Q+fiQ+bG(21)
(c1ai,c2ai,c1bi,c2bi)(22)
Alice verifies iffiQ+K2=c1bi and then continues or else terminates(23)
Bob verifies ifdiW+K1=c1ai and then continues or else terminates(24)
cb=hc2bj−c1bj−W+K2=hQ−W+hlG(25)
ca=lc2ai−c1ai−Q+K1=lW−Q+hlG(26)
ma=k1camb=k2cb(27)
Exchangecb+P1,ma, ca+P2,mb(28)
ωa=k1ca+P2ωb=k2cb+P1(29)
Exchangeωa, ωb(30)
mb=ωb−λbma=ωa−λa(31)
mb−hv⟹k2hQ−Wma−lu⟹k1lW−Q(32)
ifQ=W, thenDW=∑i=0x−1bi+∑i=0xbi=w and DQ=∑i=0xbi+∑i=0yai=qifq,w=0, then x>yelse ifq,w=1, then x=yelsex<yelse terminateOutput:Px,y


### 4.3. Correctness Analysis

(1)
The steps and positions for both Alice and Bob to execute the protocol in Algorithm 2 are identical, so we only demonstrate the possible malicious behaviors of Alice. The security analysis of the protocol is as follows:In step (5), if Alice selectsai that is the wrong random number, Bob happens not to choose the wrong random number ai out of m/2 selected, that is, no wrong random number is detected, but in the following step (7), it happens to be selected by Bob, and Bob calculates the wrong result. The probability of success is analyzed as follows:①
If Alice uses the above method to commit a malicious attack, the most likely scenario for successful execution of such malicious attacks is that Alice mixes one wrongai in m random ai, which maximizes the likelihood that the malicious attack will succeed. The probability of deception success in this case is 1/m.②
Ifm=20, Alice mixes one wrong ai in m random ai. The probability of deception success in this case is C1910/C2010×1/10=1/200, but if Alice mixes 10 wrong ai in m random ai, the probability of deception success in this case is C1910/C2010×1/2=2.7×10−7, in which case the probability of success is even smaller or negligible.③
If Alice mixesm random ai with more than m/2 wrong random numbers, it will be discovered in the subsequent verification phase.(2)
In step (4), both Alice and Bob decrypt pointW and point Q using their respective private keys k1 and k2 as follows:(5)C1−k1C2=∑i=0x−1Mib+∑i=0xMib+K1∑i=1x−1ri−k1G∑i=1x−1ri+K1∑i=1xri−k1G∑i=1xri=∑i=0x−1Mib+∑i=0xMib=W,C1′−k2C2′=∑i=0y−1Mia+∑i=0yMia+K2∑i=1y−1ri−k2G∑i=1y−1ri+K2∑i=1yri−k2G∑i=1yri=∑i=0y−1Mia+∑i=0yMia=Q.(3)
Thec1ai,c2ai and c1di,c2di published in step (5) do not leak any information because their own random numbers are added.(4)
In step (7), Alice and Bob calculate as follows:(6)cb=hc2bj−c1bj−W+K2=hQ+fjQ+bG−fjQ−K2−W+K2=hQ−W+hlG,ca=lc2ai−c1ai−Q+K1=lW+diW+aG−diW−K1−Q+K1=lW−Q+hlG.Alice and Bob then sendcb+P1 and ca+P2 to each other.(5)
In step (10), Alice and Bob get the right results.Alice uses the zero-knowledge to prove that themb sent by Bob is correct; the result obtained by calculating mb−hv is correct, that is,(7)mb−hv=mb−hlK2=k2cb−hlk2G=k2hQ−W+k2hlG−hlk2G=k2hQ−W.After Bob uses zero-knowledge to prove that thema sent by Alice is correct; the result obtained by calculating ma−bu is correct, that is:(8)ma−lu=ma−hlK1=k1ca−hlk1G=k1lW−Q+k1hlG−hlk1G=k1lW−Q.(6)
In step (11), Alice and Bob decode pointW=∑i=0x−1Mib+∑i=0xMib and point Q=∑i=0y−1Mia+∑i=0yMia to get ∑i=0x−1bi+∑i=0xbi=w and ∑i=0y−1ai+∑i=0yai=q, respectively.(7)
The encoding of plaintexts on pointsW and Q in steps (1) and (2) and the decoding of points W and Q in step (11) can be referred to reference [23].(8)
The whole process does not leak any confidential information, and both parties can obtain results independently, avoiding unfairness caused by one party telling the other party the result.(9)
In many cases, the data range is known to all parties in reality. For example, if two students want to compare their grades, then the data range isa1,a2,…a100, that is known to all parties; if two companies at the same level want to compare their assets, the data range may be a1M,a2M,…,a100M, but a company’ assets are often sparsely rather than densely distributed on the data range. Assets can only be a few scales, and the data range is very small. Therefore, they know the data range. The data range does not leak any information about its private data. Generally speaking, all the numbers compared in SMC are comparable. If these figures are comparable, both parties will know their scope. Ordinary companies will never compare their assets with Microsoft because they are not comparable. However, we have to say that although the data range is known, if the data range is large, the computational complexity of the protocol will be very high, so the protocol becomes impractical.


### 4.4. Security Proof

Algorithm 2 under the malicious model is proved as follows.Definition 2.
Algorithm 2 is secure under the malicious model.Proof.
This proving process borrows a trusted third party (TTP). We set the actual policy pair asA¯=A1,A2, the ideal policy pair as B¯=B1,B2, F as the output, and S as the message sequence received by A2 in the zero-knowledge proof process. We want to prove that the security of the protocol under the malicious model is to prove that when Algorithm 2 is executed, the implementation of malicious behaviors in the actual protocol calculation will not affect the correct output, that is:(9)REAL,A¯W,Q=IDEALB¯W,Q.
In Algorithm 2, the malicious behaviors are not allowed for both Alice and Bob at the same time, so there are two scenarios: Alice or Bob is honest. Here,A1,B1 and A2,B2 represent Alice and Bob, respectively.(1)
IfA1 is honest and A2 is dishonest, then:(10)REALA¯W,Q=FW,A2Q,A2c1ai,c2ai,ma,S.①
SinceA1 is honest, B1 sends a correct W to TTP, and the protocol will be executed correctly.②
WhatB2 sends to TTP depends on the actual selection of A2. B2 sends Q to A2 under the ideal model. A2 sends A2Q to B2 in the practical cases, and B2 sends A2Q to TTP. Finally, TTP outputs FW,A2Q.③
Ideally,B2 uses the FW,A2Q sent by TTP to try to get viewB2FW,A2Q that is indistinguishable from the viewA2FW,A2Q calculated by A2 in practice and make it the output of A2 in the practical cases.That is,B2 selects W′ to make FA1W,Q′=FA1W,Q, performs all the calculations in Algorithm 2, obtains ma′ and c1ai′,c2ai′, and records the received sequence S′ in the zero-knowledge proof. Thus, the protocol proceeds, and we get(11)IDEALB¯W,Q=FW,A2Q,A2c1ai′,c2ai′,ma′,S′.Because ciphertexts are encrypted ideally and practically using the same probability algorithm, there arec1ai′≡cc1ai and c2ai′≡cc2ai. The random number ai is indistinguishable from ai′, so REALA¯W,Q=IDEALB¯W,Q.(2)
IfA1 is dishonest and A2 is honest, there are two situations:Actually,A1 completes the zero-knowledge proof and publishes the results:(12)REALA¯W,Q=A1c1bi,c2bi,mb,S,FW,Q.Actually,A1 does not publish the results or execute the zero-knowledge proof:(13)REALA¯W,Q=A1c1bi,c2bi,mb,S,⊥.
①
BecauseA2 is honest, B2 will send correct Q to TTP, and the protocol will be carried out correctly.②
WhatB1 will send to TTP depends on the choice of A1 in the practical situation. Ideally, B1 sends W to A1; practically, A1 sends A1W to B1, and B1 sends A1W to TTP. Finally, TTP outputs FA1W,Q.③
IfA1 does not publish the results or do not conduct the zero-knowledge proof in practice, B2 in the ideal model will get ⊥ from TTP.④
Ideally,B1 uses the FA1W,Q sent by TTP to try to obtain viewB1A1W,Q that is indistinguishable from viewA1A1W,Q calculated by A1 in the practical situation and to make it to be the output of A1 in the practical situation.
That is,B1 selects Q′ to make FA1W,Q′=FA1W,Q. And Algorithm 2 is carried out. Finally, under the ideal model, B1 obtains mb′ and c1bi′,c2bi′ and records the sequence S′ received through the zero-knowledge proof. In this way, we get the following.
Ideally, whenB1 does not publish results to B2 via TTP:(14)IDEALB¯W,Q=A1c1bi′,c2bi′,mb′,S′,⊥.
Ideally, whenB1 announces results to B2 via TTP:(15)IDEAL,B¯W,Q=A1c1bi′,c2bi′,mb′,S′,FA1W,Q,
wherec1bi′,c2bi′, and c1bi,c2bi are encrypted by the same ECC encryption algorithm. mb′ and mb are computed by both random numbers and constant operations. The zero-knowledge proof guarantees S′≡cS. Therefore, for any algorithm in the practical protocol A¯=A1,A2, there exists B¯=B1,B2 in the ideal protocol, which makes(16)IDEALB¯W,Q≡cREALA¯W,Q.
Thus, the protocol’s security is proven.


## 4.1. Solution Ideas

Firstly, we analyze the possible malicious attacks in Algorithm 1. Then the solutions to these malicious attacks are proposed. Finally, the possible malicious attacks cannot be implemented or found when they are committed. The following malicious attacks may exist in Algorithm 1 as follows:(1)
In Algorithm 1, Alice has both the public keyK and the private key k, but Bob only has the public key K, so the final result can only be calculated unilaterally by Alice, which is unfair to Bob. (2) In steps 3 and 4, if the ciphertext sent by Alice and Bob to each other is wrong so that neither party can get the correct result. (3) In step 5, Alice tells Bob the wrong result after decrypting, which leads to a wrong conclusion for Bob. For the above malicious attacks, a new protocol must be designed to find or render them impossible to implement. (Note: Before designing the protocol under the malicious model, we need to be clear that some malicious behaviors cannot be prevented in the ideal protocol. For example, if you enter wrong inputs in the ideal model, no matter how you detect and verify, you cannot get the correct results; similarly, if you refuse to carry out the protocol, we cannot get the results, either. Therefore, we will not consider the following behaviors when designing the protocol under the malicious model: (1) refusing to carry out the protocol, (2) inputting false data, and (3) one party terminating the protocol after obtaining the information he wants to prevent other participants from carrying out the protocol.)To design a secure, fair, and correct protocol under the malicious model, the solution is to use cryptographic tools such as the zero-knowledge proof and cut-choose method to prevent malicious attacks that may exist in Algorithm 1. The final results are calculated by both parties at the same time.


## 4.2. Specific Protocol

Based on the malicious attacks that may occur in Algorithm 1 under the semihonest model, we use the above 0-1 encoding rule to design the millionaires’ problem algorithm under the malicious model using the zero-knowledge proof and cut-choose method. The framework of Algorithm 2 under the malicious model is outlined in Algorithm 3.Algorithm 2: Judgement under the malicious model.
Input: Alice ownsx, and Bob owns y.Output:Px,y.Prepare:(1)
Alice and Bob jointly select an elliptic curveEp and a base point G. Alice and Bob separately select their own private key k1,k2k1,k2>0. Then Alice and Bob calculate their public keys K1=k1G and K2=k2G and u=aK1 and v=bK2, respectively. Finally, Alice and Bob exchange K1,u and K2,v.Alice and Bob construct their own new setsX=a1,a2,…,am and Y=b1,b2,…,bm through x and y, where: ai=1,i=x;0,i≠x.bi=1,i=y;0,i≠y..Start:(1)
Alice encodes the plaintextX=a1,a2,…,am onto the point Mia1≤i≤m of the elliptic curve Epa,b; selects m random numbers ria; encrypts each element Mia one by one with the public key K1, that is, calculates the EMia=C1ia,C2ia, where: C1ia=Mia+riaK1 and C2ia=riaG; obtains EX=EM1a,EM2a,…,EMma; and finally, sends EX to Bob.(2)
Bob encodes the plaintextY=b1,b2,…,bm onto the point Mib1≤i≤m of the elliptic curve Epa,b; selects m random numbers rib; encrypts each element Mib one by one by using the public key K2, that is, calculates the EMib=C1ib,C2ib, where: C1ib=Mib+ribK2 and C2ib=ribG; obtains EY=EM1b,EM2b,…,EM3b; and finally, sends EY to Alice.(3)
Alice calculatesEQ=C1,C2 according to the position of data x in EY, where C1=∑i=1x−1C1ib+∑i=1xC1ib and C2=∑i=1x−1C2ib+∑i=1xC2ib, and sends EQ to Bob.Bob calculatesEW=C1′,C2′ according to the position of data y in EX, where C1′=∑i=1y−1C1ia+∑i=1yC1ia and C2′=∑i=1y−1C2ia+∑i=1yC2ia, and sends EW to Alice.(4)
Alice decryptsEW using the private key k1, that is, calculates C1−k1C2=∑i=0x−1Mib+∑i=0xMib=W to obtain W point. Bob decrypts EQ using the private key k2, that is, calculates C1′−k2C2′=∑i=0y−1Mia+∑i=0yMia=Q to obtain point Q.(5)
Alice selectsm random numbers di (0≤i≤m) to calculate c1ai,c2ai=diW+K1,W+diW+aG. Bob selects m random numbers fi (0≤i≤m) to calculate c1bi,c2bi=fiQ+K2,Q+fiQ+bG. Finally, Alice and Bob exchange c1ai,c2ai and c1bi,c2bi.(6)
With the help of the cut-choose method, Alice randomly selects them/2 groups from the m groups c1bi,c2bi sent by Bob and publishes it and requires Bob to publish the corresponding fiQ. Alice verifies: fiQ+K2=c1bi. If the verification is passed, they continue the protocol or else terminate.Bob randomly selects them/2 groups from the m group c1ai,c2ai sent by Alice and publishes it and requires Alice to publish the corresponding diW. Bob verifies: diQ+K1=c1ai. If the verification is passed, they continue the protocol or else terminate.(7)
Alice and Bob randomly select onec1bi,c2bi and c1ai,c2ai from the remaining c1bi,c2bi and c1ai,c2ai, respectively. Meanwhile, Alice selects two random numbers h and p1, and Bob selects two random numbers l and p2. Alice calculates cb=hc2bj−c1bj−W+K2=hQ−W+hlG, P1=p1G, λb=p1K2; Bob calculates ca=lc2ai−c1ai−Q+K1=lW−Q+hlG, P2=p2G, and λa=p2K1. Then Alice and Bob send cb+P1 and ca+P2 to each other.(8)
After both parties receive information from each other, Alice calculatesωa=k1ca+P2 and ma=k1ca and sends them to Bob. Bob calculates ωb=k2cb+P1 and mb=k2cb and sends them to Alice.(9)
Alice uses the zero-knowledge proof to verify that themb sent by Bob is correct, that is, to prove that Bob does get the mb by multiplying his private key k2 with his cb, that is, to judge whether mb=ωb−λb is true. Bob uses the zero-knowledge proof to verify that the ma sent by Alice is correct, that is, to prove that Alice does get the ma by multiplying her private key k1 with her ca, that is, to judge whether ma=ωa−λa is true. The party who fails is malicious.(10)
Alice can getk2hQ−W by calculating mb−hv. If k2hQ−W=0, then Q=W; Bob can get k1lW−Q by calculating ma−lu. If k1lW−Q=0, then Q=W. If Q=W, it proves that the results required by both parties are correct and identical; otherwise, the protocol shall be terminated.(11)
Finally, Alice and Bob get∑i=0x−1bi+∑i=0xbi=w and ∑i=0y−1ai+∑i=0yai=q by decoding points W and Q, respectively. If q,w=0, then x>y; if q,w=1, then x=y; and if q,w=2, then x<y.The protocol ends.A specific protocol is as follows:Algorithm 3: Judgement under the malicious model.
Input:x: Alice’s input; y: Bob’s input; G: the base point of the elliptic curve Ep; Code: encode inputs into a m degree 0-1 codes; k1: Alice’s private key; k2: Bob’s private key; E: encrypt. h,p1: Alice’s random number; and l,p2: Bob’s random number(1)
K1=k1GK2=k2G(2)
u=aK1v=bK2(3)
P1=p1GP2=p2G(4)
λb=p1K2λa=p2K1(5)
Codex=X=a1,a2,…,am(6)
C1ia=Mia+riaK1C2ia=riaG(7)
EMia=C1ia,C2ia(8)
EX=EM1a,EM2a,…,EMma(9)
Codey=Y=b1,b2,⋯,bm(10)
C1ib=Mib+ribK2C2ib=ribG(11)
EMib=C1ib,C2ib(12)
EY=EM1b,EM2b,…,EM3b(13)
ExchangeK1,EX,u, K2,EY,v.(14)
C1=∑i=1x−1C1ib+∑i=1xC1ibC2=∑i=1x−1C2ib+∑i=1xC2ib(15)
EQ=C1,C2(16)
C2′=∑i=1y−1C2ia+∑i=1yC2ia(17)
EW=C1′,C2′(18)
ExchangeEQ, EW(19)
DEW=WDEQ=Q(20)
c1ai,c2ai=diW+K1,W+diW+aGand c1bi,c2bi=fiQ+K2,Q+fiQ+bG(21)
(c1ai,c2ai,c1bi,c2bi)(22)
Alice verifies iffiQ+K2=c1bi and then continues or else terminates(23)
Bob verifies ifdiW+K1=c1ai and then continues or else terminates(24)
cb=hc2bj−c1bj−W+K2=hQ−W+hlG(25)
ca=lc2ai−c1ai−Q+K1=lW−Q+hlG(26)
ma=k1camb=k2cb(27)
Exchangecb+P1,ma, ca+P2,mb(28)
ωa=k1ca+P2ωb=k2cb+P1(29)
Exchangeωa, ωb(30)
mb=ωb−λbma=ωa−λa(31)
mb−hv⟹k2hQ−Wma−lu⟹k1lW−Q(32)
ifQ=W, thenDW=∑i=0x−1bi+∑i=0xbi=w and DQ=∑i=0xbi+∑i=0yai=qifq,w=0, then x>yelse ifq,w=1, then x=yelsex<yelse terminateOutput:Px,y


## 4.3. Correctness Analysis

(1)
The steps and positions for both Alice and Bob to execute the protocol in Algorithm 2 are identical, so we only demonstrate the possible malicious behaviors of Alice. The security analysis of the protocol is as follows:In step (5), if Alice selectsai that is the wrong random number, Bob happens not to choose the wrong random number ai out of m/2 selected, that is, no wrong random number is detected, but in the following step (7), it happens to be selected by Bob, and Bob calculates the wrong result. The probability of success is analyzed as follows:①
If Alice uses the above method to commit a malicious attack, the most likely scenario for successful execution of such malicious attacks is that Alice mixes one wrongai in m random ai, which maximizes the likelihood that the malicious attack will succeed. The probability of deception success in this case is 1/m.②
Ifm=20, Alice mixes one wrong ai in m random ai. The probability of deception success in this case is C1910/C2010×1/10=1/200, but if Alice mixes 10 wrong ai in m random ai, the probability of deception success in this case is C1910/C2010×1/2=2.7×10−7, in which case the probability of success is even smaller or negligible.③
If Alice mixesm random ai with more than m/2 wrong random numbers, it will be discovered in the subsequent verification phase.(2)
In step (4), both Alice and Bob decrypt pointW and point Q using their respective private keys k1 and k2 as follows:(5)C1−k1C2=∑i=0x−1Mib+∑i=0xMib+K1∑i=1x−1ri−k1G∑i=1x−1ri+K1∑i=1xri−k1G∑i=1xri=∑i=0x−1Mib+∑i=0xMib=W,C1′−k2C2′=∑i=0y−1Mia+∑i=0yMia+K2∑i=1y−1ri−k2G∑i=1y−1ri+K2∑i=1yri−k2G∑i=1yri=∑i=0y−1Mia+∑i=0yMia=Q.(3)
Thec1ai,c2ai and c1di,c2di published in step (5) do not leak any information because their own random numbers are added.(4)
In step (7), Alice and Bob calculate as follows:(6)cb=hc2bj−c1bj−W+K2=hQ+fjQ+bG−fjQ−K2−W+K2=hQ−W+hlG,ca=lc2ai−c1ai−Q+K1=lW+diW+aG−diW−K1−Q+K1=lW−Q+hlG.Alice and Bob then sendcb+P1 and ca+P2 to each other.(5)
In step (10), Alice and Bob get the right results.Alice uses the zero-knowledge to prove that themb sent by Bob is correct; the result obtained by calculating mb−hv is correct, that is,(7)mb−hv=mb−hlK2=k2cb−hlk2G=k2hQ−W+k2hlG−hlk2G=k2hQ−W.After Bob uses zero-knowledge to prove that thema sent by Alice is correct; the result obtained by calculating ma−bu is correct, that is:(8)ma−lu=ma−hlK1=k1ca−hlk1G=k1lW−Q+k1hlG−hlk1G=k1lW−Q.(6)
In step (11), Alice and Bob decode pointW=∑i=0x−1Mib+∑i=0xMib and point Q=∑i=0y−1Mia+∑i=0yMia to get ∑i=0x−1bi+∑i=0xbi=w and ∑i=0y−1ai+∑i=0yai=q, respectively.(7)
The encoding of plaintexts on pointsW and Q in steps (1) and (2) and the decoding of points W and Q in step (11) can be referred to reference [23].(8)
The whole process does not leak any confidential information, and both parties can obtain results independently, avoiding unfairness caused by one party telling the other party the result.(9)
In many cases, the data range is known to all parties in reality. For example, if two students want to compare their grades, then the data range isa1,a2,…a100, that is known to all parties; if two companies at the same level want to compare their assets, the data range may be a1M,a2M,…,a100M, but a company’ assets are often sparsely rather than densely distributed on the data range. Assets can only be a few scales, and the data range is very small. Therefore, they know the data range. The data range does not leak any information about its private data. Generally speaking, all the numbers compared in SMC are comparable. If these figures are comparable, both parties will know their scope. Ordinary companies will never compare their assets with Microsoft because they are not comparable. However, we have to say that although the data range is known, if the data range is large, the computational complexity of the protocol will be very high, so the protocol becomes impractical.


## 4.4. Security Proof

Algorithm 2 under the malicious model is proved as follows.Definition 2.
Algorithm 2 is secure under the malicious model.Proof.
This proving process borrows a trusted third party (TTP). We set the actual policy pair asA¯=A1,A2, the ideal policy pair as B¯=B1,B2, F as the output, and S as the message sequence received by A2 in the zero-knowledge proof process. We want to prove that the security of the protocol under the malicious model is to prove that when Algorithm 2 is executed, the implementation of malicious behaviors in the actual protocol calculation will not affect the correct output, that is:(9)REAL,A¯W,Q=IDEALB¯W,Q.
In Algorithm 2, the malicious behaviors are not allowed for both Alice and Bob at the same time, so there are two scenarios: Alice or Bob is honest. Here,A1,B1 and A2,B2 represent Alice and Bob, respectively.(1)
IfA1 is honest and A2 is dishonest, then:(10)REALA¯W,Q=FW,A2Q,A2c1ai,c2ai,ma,S.①
SinceA1 is honest, B1 sends a correct W to TTP, and the protocol will be executed correctly.②
WhatB2 sends to TTP depends on the actual selection of A2. B2 sends Q to A2 under the ideal model. A2 sends A2Q to B2 in the practical cases, and B2 sends A2Q to TTP. Finally, TTP outputs FW,A2Q.③
Ideally,B2 uses the FW,A2Q sent by TTP to try to get viewB2FW,A2Q that is indistinguishable from the viewA2FW,A2Q calculated by A2 in practice and make it the output of A2 in the practical cases.That is,B2 selects W′ to make FA1W,Q′=FA1W,Q, performs all the calculations in Algorithm 2, obtains ma′ and c1ai′,c2ai′, and records the received sequence S′ in the zero-knowledge proof. Thus, the protocol proceeds, and we get(11)IDEALB¯W,Q=FW,A2Q,A2c1ai′,c2ai′,ma′,S′.Because ciphertexts are encrypted ideally and practically using the same probability algorithm, there arec1ai′≡cc1ai and c2ai′≡cc2ai. The random number ai is indistinguishable from ai′, so REALA¯W,Q=IDEALB¯W,Q.(2)
IfA1 is dishonest and A2 is honest, there are two situations:Actually,A1 completes the zero-knowledge proof and publishes the results:(12)REALA¯W,Q=A1c1bi,c2bi,mb,S,FW,Q.Actually,A1 does not publish the results or execute the zero-knowledge proof:(13)REALA¯W,Q=A1c1bi,c2bi,mb,S,⊥.
①
BecauseA2 is honest, B2 will send correct Q to TTP, and the protocol will be carried out correctly.②
WhatB1 will send to TTP depends on the choice of A1 in the practical situation. Ideally, B1 sends W to A1; practically, A1 sends A1W to B1, and B1 sends A1W to TTP. Finally, TTP outputs FA1W,Q.③
IfA1 does not publish the results or do not conduct the zero-knowledge proof in practice, B2 in the ideal model will get ⊥ from TTP.④
Ideally,B1 uses the FA1W,Q sent by TTP to try to obtain viewB1A1W,Q that is indistinguishable from viewA1A1W,Q calculated by A1 in the practical situation and to make it to be the output of A1 in the practical situation.
That is,B1 selects Q′ to make FA1W,Q′=FA1W,Q. And Algorithm 2 is carried out. Finally, under the ideal model, B1 obtains mb′ and c1bi′,c2bi′ and records the sequence S′ received through the zero-knowledge proof. In this way, we get the following.
Ideally, whenB1 does not publish results to B2 via TTP:(14)IDEALB¯W,Q=A1c1bi′,c2bi′,mb′,S′,⊥.
Ideally, whenB1 announces results to B2 via TTP:(15)IDEAL,B¯W,Q=A1c1bi′,c2bi′,mb′,S′,FA1W,Q,
wherec1bi′,c2bi′, and c1bi,c2bi are encrypted by the same ECC encryption algorithm. mb′ and mb are computed by both random numbers and constant operations. The zero-knowledge proof guarantees S′≡cS. Therefore, for any algorithm in the practical protocol A¯=A1,A2, there exists B¯=B1,B2 in the ideal protocol, which makes(16)IDEALB¯W,Q≡cREALA¯W,Q.
Thus, the protocol’s security is proven.


## 5. Efficiency Analysis

### 5.1. Computational Complexity

Reference [24] proposed a protocol to solve the millionaires’ problem based on the decision Diffie–Hellman hypothesis (DDH) and performed 4nt+n modular multiplications. Reference [25] designed a millionaires’ problem comparison protocol with 0-1 coding rules based on ElGamal encryption, which needs 2m+3logP+5m modular multiplications. Reference [22] designed an antimalicious millionaires’ problem protocol based on the Paillier encryption and performed 10mlogN+2 modular multiplications.During the execution of Algorithm 1, the computational complexity mainly includes:m times ECC encryption operations of Alice and 1 time ECC decryption operation of Bob, with a total of 2m+1 modular multiplications. During the execution of Algorithm 2, the computational complexity mainly includes: m times ECC encryption operations and 1 time ECC decryption operation of Alice and several modular multiplication operations during message verification. A total of 11m+10 modular multiplications are performed, and the rest are ordinary multiplication and addition operations, which can be ignored.


### 5.2. Communication Complexity

There are two rounds of communication in Algorithm 1; reference [24] carried out three rounds of communication; reference [25] carried out three rounds of communication; reference [22] carried out three rounds of communication; and Algorithm 2 carried out six rounds of communication, as shown in Table 2.Table 2
Performance comparison of the efficiency of the four protocols in terms of computational complexity, number of communication rounds, and whether they can resist malicious attacks.
ProtocolFair for both partiesComputational complexity (modular multiplications)Communication (rounds)Resist malicious attacksAlgorithm 1No2m+12×Reference [24]No4nt+n3nlogP×Reference [25]No2m+3logP+5m3×Reference [22]Yes10mlogN+23√Algorithm 2Yes11m+106√


### 5.3. Experimental Simulation

To verify the validity of the above protocols more intuitively, we compare Algorithm 2 with reference [22, 24, 25]. The experimental environment is Windows10 (64 bit) operating system, Intel (R) Core (TM) i7-5500U CPU @ 2.40 GHz processor, 8.00 GB memory, and the experiment is carried out by Python language.The Paillier encryption, ElGamal encryption, and GM encryption have the same size of inputs in the experiment, and the time of protocol preprocessing is ignored in the experiment. Figure2 is a comparison of the protocol time consumption in experiment 1 with the increase of modulus. The data held by each participant in experiment 1 is an integer from 0 to 100 (set length is set to 100). The average execution time (the ordinate coordinate) of the four protocols is calculated under 128, 256, 512, and 1,024 bit modules (the horizontal coordinate). As can be seen from Figure 2, the time consumed by Algorithm 2 is lower than those of other references.Figure 2
Time consumption comparison of different modules. The data held by each participant is an integer from 0 to 100 (set length is set to 100).Figure3 is a comparison of the execution time of experiment 2 with the increase of data range. In experiment 2, each participant held the input data in the range of 0–100, 100–200, 200–300, 300–400, 400–500, 500–600, 600–700, 700–800, 800–900, and 900–1,000 under the same module. As can be seen from Figure 3, Algorithm 2 takes less time in different data ranges than other protocols, and the time consumption is relatively stable.Figure 3
Time consumption comparison for different input ranges under the same module.The results show that under the same security performance, Algorithm 2 is slightly more efficient than reference [24] and has obvious advantages than Reference [22, 25]. Algorithm 2 can resist malicious attacks and has higher security and greater practical value. (Note: For Algorithm 2, increased the bitcoin commitment, cut-choose, and zero-knowledge proof methods will result in significantly higher computational complexity and lower execution efficiency, making malicious model protocols no more efficient than semihonest model protocols. However, preprocessing or computing outsourcing can be used to improve efficiency, and both methods are available in Algorithm 2).


### 5.4. Applications

This paper uses efficient ECC encryption to design and study the classic millionaires’ problem in SMC. It not only solves the problem of comparison between two numbers but also distinguishes whether two numbers are equal or not. The protocol can be widely applied to sort confidentially. Alice hasX=a1,a2,...,am; Bob has y; Bob wants to query the ranking position of y in X; and both sides do not want to expose any information about X and y. This problem is an important application of SMC in data query and has wide application prospects, such as secret ranking of college entrance examination results: after the college entrance examination, candidates want to check their ranking in the reported candidates, and the school does not want to disclose any information about other candidates. The problem can be solved by our protocol.The same method can be applied to the smart contract quality evaluation in the blockchain. Blockchain technology is considered to be the next generation of disruptive core technology after steam engine, power, and Internet. In order to establish a high-quality blockchain application environment, excellent smart contract developers will be rewarded by obtaining some form, such as tokens. However, there is no good evaluation method for the quality of the smart contract. Most of them are sorted by the number of contract calls and the total amount of contract transactions. Therefore, using our protocol to construct the sorting method, the screened high-ranking users have strong authenticity and security and are not easy to forge.


## 5.1. Computational Complexity

Reference [24] proposed a protocol to solve the millionaires’ problem based on the decision Diffie–Hellman hypothesis (DDH) and performed 4nt+n modular multiplications. Reference [25] designed a millionaires’ problem comparison protocol with 0-1 coding rules based on ElGamal encryption, which needs 2m+3logP+5m modular multiplications. Reference [22] designed an antimalicious millionaires’ problem protocol based on the Paillier encryption and performed 10mlogN+2 modular multiplications.During the execution of Algorithm 1, the computational complexity mainly includes:m times ECC encryption operations of Alice and 1 time ECC decryption operation of Bob, with a total of 2m+1 modular multiplications. During the execution of Algorithm 2, the computational complexity mainly includes: m times ECC encryption operations and 1 time ECC decryption operation of Alice and several modular multiplication operations during message verification. A total of 11m+10 modular multiplications are performed, and the rest are ordinary multiplication and addition operations, which can be ignored.


## 5.2. Communication Complexity

There are two rounds of communication in Algorithm 1; reference [24] carried out three rounds of communication; reference [25] carried out three rounds of communication; reference [22] carried out three rounds of communication; and Algorithm 2 carried out six rounds of communication, as shown in Table 2.Table 2
Performance comparison of the efficiency of the four protocols in terms of computational complexity, number of communication rounds, and whether they can resist malicious attacks.
ProtocolFair for both partiesComputational complexity (modular multiplications)Communication (rounds)Resist malicious attacksAlgorithm 1No2m+12×Reference [24]No4nt+n3nlogP×Reference [25]No2m+3logP+5m3×Reference [22]Yes10mlogN+23√Algorithm 2Yes11m+106√


## 5.3. Experimental Simulation

To verify the validity of the above protocols more intuitively, we compare Algorithm 2 with reference [22, 24, 25]. The experimental environment is Windows10 (64 bit) operating system, Intel (R) Core (TM) i7-5500U CPU @ 2.40 GHz processor, 8.00 GB memory, and the experiment is carried out by Python language.The Paillier encryption, ElGamal encryption, and GM encryption have the same size of inputs in the experiment, and the time of protocol preprocessing is ignored in the experiment. Figure2 is a comparison of the protocol time consumption in experiment 1 with the increase of modulus. The data held by each participant in experiment 1 is an integer from 0 to 100 (set length is set to 100). The average execution time (the ordinate coordinate) of the four protocols is calculated under 128, 256, 512, and 1,024 bit modules (the horizontal coordinate). As can be seen from Figure 2, the time consumed by Algorithm 2 is lower than those of other references.Figure 2
Time consumption comparison of different modules. The data held by each participant is an integer from 0 to 100 (set length is set to 100).Figure3 is a comparison of the execution time of experiment 2 with the increase of data range. In experiment 2, each participant held the input data in the range of 0–100, 100–200, 200–300, 300–400, 400–500, 500–600, 600–700, 700–800, 800–900, and 900–1,000 under the same module. As can be seen from Figure 3, Algorithm 2 takes less time in different data ranges than other protocols, and the time consumption is relatively stable.Figure 3
Time consumption comparison for different input ranges under the same module.The results show that under the same security performance, Algorithm 2 is slightly more efficient than reference [24] and has obvious advantages than Reference [22, 25]. Algorithm 2 can resist malicious attacks and has higher security and greater practical value. (Note: For Algorithm 2, increased the bitcoin commitment, cut-choose, and zero-knowledge proof methods will result in significantly higher computational complexity and lower execution efficiency, making malicious model protocols no more efficient than semihonest model protocols. However, preprocessing or computing outsourcing can be used to improve efficiency, and both methods are available in Algorithm 2).


## 5.4. Applications

This paper uses efficient ECC encryption to design and study the classic millionaires’ problem in SMC. It not only solves the problem of comparison between two numbers but also distinguishes whether two numbers are equal or not. The protocol can be widely applied to sort confidentially. Alice hasX=a1,a2,...,am; Bob has y; Bob wants to query the ranking position of y in X; and both sides do not want to expose any information about X and y. This problem is an important application of SMC in data query and has wide application prospects, such as secret ranking of college entrance examination results: after the college entrance examination, candidates want to check their ranking in the reported candidates, and the school does not want to disclose any information about other candidates. The problem can be solved by our protocol.The same method can be applied to the smart contract quality evaluation in the blockchain. Blockchain technology is considered to be the next generation of disruptive core technology after steam engine, power, and Internet. In order to establish a high-quality blockchain application environment, excellent smart contract developers will be rewarded by obtaining some form, such as tokens. However, there is no good evaluation method for the quality of the smart contract. Most of them are sorted by the number of contract calls and the total amount of contract transactions. Therefore, using our protocol to construct the sorting method, the screened high-ranking users have strong authenticity and security and are not easy to forge.


## 6. Summary and Prospect

As the cornerstone of SMC, the millionaires’ problem is still under constant researches by experts and scholars. However, most of the schemes are designed under the semihonest model, which cannot resist malicious attacks and affect the practical application of the protocols. This paper uses the 0-1 encoding method and ECC encryption algorithm, first designs a semihonest model protocol, and then improves it for malicious behaviors. The millionaires’ problem protocol under the malicious model solves the problem of malicious attacks in practical applications. By comparing with the existing protocols, our protocol is more efficient and practical.



---

*Source: 6923610-2022-03-24.xml*