Three-Party Integer Comparison and Applications

We give a general model for comparisons in this paper. The participants are divided into two parts: one is called judge with no private input like the auctioneer in an auction, the other is called competitors which is a set of participants holding private inputs like bidders. The judge wants to obtain the sorted order of the secret inputs, which the owners does not wants to reveal. Assume there are $N$ ($N\!\geq\!2$) competitors and one judge in the following. In TPIC, $N\!=\!2$.

Let $\mathcal{P}$ be a set of participants, who perform a protocol $\Pi$ to compute an ideal function $\mathcal{F}$ given inputs $In_{\mathcal{P}}$ and outputs $Out_{\mathcal{P}}$. For a corrupted subset $I$ of $\mathcal{P}(I\subseteq\mathcal{P})$, the view of $I$ is denoted by $\mathbf{VIEW}^{\Pi}_{I}(In_{\mathcal{P}},Out_{I},\phi_{I})$, where $\phi_{I}$ contains messages and random numbers selected by $P_{i,i\in I}$ and related information during running $\Pi$. Let $\mathbf{Sim}_{I}$ be a simulator that takes the inputs of all $P_{i,i\in I}$ $(In_{I})$ and the outcome of $\mathcal{F}$ received by $P_{i}$ $(Out_{I})$ to produce a transcript of the protocol.

In our schemes, the blockchain-based commitment scheme (CS) with deposits in [26] is used to bind the input with its owner, forcing the owner to follow the protocol.

Assume a committer $\mathbf{C}$ wants to commit $y$ to a recipient $\mathbf{R}$ via blockchain. Initially, a hash function $\mathcal{H}$ is negotiated by the committer $\mathbf{C}$ and recipient $\mathbf{R}$. At the commitment phase, $\mathbf{C}$ computes $h=\mathcal{H}(S\|y)$ with some randomness $S$ as a commitment to $y$. Then he broadcasts a transaction $CS.Commit$ on blockchain revealing the commitment $h$ with some deposits $v$, which is contained in some transaction possessed by $\mathbf{C}$. The deposits will be redeemed by $\mathbf{C}$ during the opening phase with a transaction $CS.Open$ if he opens the correct commitment. Otherwise, the deposits will be claimed by $\mathbf{R}$ as punishment for $\mathbf{C}$. Afterwards, a transaction $CS.Fuse$ is created by $\mathbf{C}$ and sent to $\mathbf{R}$ with his signature on it enabling $\mathbf{R}$ to claim the deposits.

At the opening phase, $\mathbf{C}$ reveals $S$ and $y$ via a transaction $CS.Open$ to redeem his deposits. If the transaction $CS.Open$ is not recorded on the blockchain after a deadline, then $\mathbf{R}$ broadcasts the transaction $CS.Fuse$ to gain the deposits of $\mathbf{C}$, or $\mathbf{R}$ learns $S$ and $y$ if $CS.Open$ appears on the blockchain then $\mathbf{C}$ redeems his deposits.

For an honest committer, the deposits will be redeemed after opening the commitment. If the committer can not correctly open the commitment, then the recipient will claim the deposits. CS satisfies the $binding$ property of a commitment scheme since hash function is collision-resistant while $hiding$ is guaranteed by unpredictability of the hash function.

In this subsection, a secure TPIC against semi-honest adversary $\mathcal{A}_{2}$ is given. We improve the two-party integer comparison protocol in [7] and give security proofs. Assume that two competitors, $P_{1}$ and $P_{2}$, holding $\alpha$ and $\beta$, respectively, want to prove to a judge $\mathbf{A}$ which one of $\alpha$ and $\beta$ is larger without uncovering them.

The strategy involves three homomorphic public key encryption (PKE) schemes, by which to do computations under ciphertexts: 1)$PKE_{1}\!=\!(\textbf{Gen}_{1},\textbf{Enc}_{1},\textbf{Dec}_{1})$ from [7] is semantically secure with threshold property that if $m_{1}\!+\!m_{2}\!<\!d$, then $\textbf{Enc}_{1}(m_{1})^{b^{m_{2}}}\!=\!\textbf{Enc}_{1}(m_{1}\!+\!m_{2})$, otherwise, $\textbf{Enc}_{1}(m_{1})^{b^{m_{2}}}\!=\!\textbf{Enc}_{1}(0)$. 2)$PKE_{2}\!=\!(\textbf{Gen}_{2},\textbf{Enc}_{2},\textbf{Dec}_{2})$ with message space $\mathcal{M}_{2}$ is multiplicatively homomorphic. 3)$PKE_{3}\!=\!(\textbf{Gen}_{\oplus},\textbf{Enc}_{\oplus},\textbf{Dec}_{\oplus})$ is semantically secure and additively homomorphic with message space $\mathcal{M}_{\oplus}$ satisfying $\textbf{Enc}_{\oplus}(\mathcal{M}_{\oplus})\subseteq\mathcal{M}_{2}$. An efficient candidate for $PKE_{3}$ is [27] and proper candidates for $PKE_{2}$ can be RSA or ElGamal encryption.

Let $\alpha=\alpha_{k-1}d^{k-1}+\alpha_{k-2}d^{k-2}+\cdots+\alpha_{1}d+\alpha_{0}$ and $\beta=\beta_{k-1}d^{k-1}+\beta_{k-2}d^{k-2}+\cdots+\beta_{1}d+\beta_{0}$, where $0\leq\alpha_{i},\beta_{i}<d$. If exactly one of the $k$ Boolean expressions below is True: $(\alpha_{k-1}>\beta_{k-1})$, $(\alpha_{k-1}=\beta_{k-1})\wedge(\alpha_{k-2}>\beta_{k-2})$, $(\alpha_{k-1}=\beta_{k-1})\wedge(\alpha_{k-2}=\beta_{k-2})\wedge(\alpha_{k-3}>\beta_{k-3})$, $\cdots$, $(\alpha_{k-1}=\beta_{k-1})\wedge(\alpha_{k-2}=\beta_{k-2})\wedge\cdots\wedge(\alpha_{0}>\beta_{0})$, then $\alpha>\beta$; otherwise $\alpha\leq\beta$.

Specifically, $P_{i}(i=1,2)$ runs $\mathbf{Gen}_{i}(1^{\lambda})$ to generate the key pair $(\mathcal{PK}_{i},\mathcal{SK}_{i})$ while the judge $\mathbf{A}$ runs $\textbf{Gen}_{\oplus}(1^{\lambda})$ to get the key pair $(\mathcal{PK}_{3},\mathcal{SK}_{3})$. They publish their public keys $\mathcal{PK}_{i}$ to each other where $\mathcal{PK}_{1}=(n,b,d,g,h,u)$. In the following, let $\ell=k-1,\dots,0$ and the notation $x\leftarrow_{\$}S$ denotes that a value $x$ is chosen uniformly at random from a set $S$.

1. 1.

   $P_{1}$ selects $r_{1,\ell}\!\!\leftarrow_{\$}\!\!\{1,\dots,2^{u}\!-\!1\}$ and computes $C_{\ell}=g^{b^{(d-\alpha_{\ell}-1)}}h^{r_{1,\ell}}$, then he publishes $C$ on blockchain, where $C\!\!=\!\!(C_{k-1}$, $\dots,C_{0})$.

2. 2.

   $P_{2}$ selects $r_{2,\ell}\!\!\leftarrow_{\$}\!\!\{1,\dots,2^{u}\!-\!1\}$, $s_{\ell}\!\!\leftarrow_{\$}\!\!\{1,\dots,b^{d}\!-\!1\}$, $s.t.,s_{\ell}\!\!\not\equiv\!\!0\bmod b$ and computes $D_{\ell}\!\!=\!\!C_{\ell}^{b^{\beta_{\ell}}}g^{s_{\ell}}h^{r_{2,\ell}}$; $A_{2,k-1}=\textbf{Enc}_{2}(\textbf{Enc}_{\oplus}(s_{k-1}))$, $A_{2,k-2}\!\!=\!\!\textbf{Enc}_{2}(\textbf{Enc}_{\oplus}(\beta_{k-1}\|s_{k-2}))$, $\dots$, $A_{2,0}\!\!=\!\!\textbf{Enc}_{2}(\textbf{Enc}_{\oplus}(\beta_{k-1}\|\beta_{k-2}\|\cdots\|s_{0}))$. She puts $(D$, $A_{2})$ on blockchain, where $D=(D_{k-1},\dots,D_{0})$ and $A_{2}=(A_{2,k-1}$, $\dots,A_{2,0})$.

3. 3.

   $P_{1}$ computes $w_{\ell}\!\!=\!\!\textbf{Dec}_{1}(D_{\ell})$; $A^{\prime}_{1,k-1}\!\!=\!\!\textbf{Enc}_{2}(\textbf{Enc}_{\oplus}(-w_{k-1}))\cdot$ $A_{2,k-1}$, $A^{\prime}_{1,k-2}=\textbf{Enc}_{2}(\textbf{Enc}_{\oplus}(-\\ (\alpha_{k-1}\|w_{k-2})))\cdot A_{2,k-2}$, …, $A^{\prime}_{1,0}=\textbf{Enc}_{2}(\textbf{Enc}_{\oplus}(-(\alpha_{k-1}\|\alpha_{k-2}\|\cdots\|w_{0})))\cdot A_{2,0}$. Then he blinds $A_{1,\ell}^{\prime}$ by computing $A_{1,\ell}\!=\!(A^{\prime}_{1,\ell})^{r_{\ell}}$ for $0\!\neq\!r_{\ell}$ $\leftarrow_{\$}\mathcal{M}_{\oplus}$. He gets $A_{1}=(A_{1,k-1^{\prime}},\dots,A_{1,0^{\prime}})$ by shuffling $(A_{1,k-1},\dots,A_{1,0})$ via a random permutation $\pi_{1}$. He puts $A_{1}$ on blockchain.

4. 4.

   $P_{2}$ computes $A_{0,\ell}^{\prime}=\textbf{Dec}_{2}(A_{1,\ell})$ and blinds $A_{0,\ell}^{\prime}$ by computing $A_{0,\ell}=(A^{\prime}_{0,\ell})^{r_{\ell}^{\prime}}$ for $0\neq r_{\ell}^{\prime}\leftarrow_{\$}\mathcal{M}_{\oplus}$. Then, she shuffles $(A_{0,k-1},\dots,A_{0,0})$ to $A_{0}=(A_{0,k-1^{\prime}},\dots,A_{0,0^{\prime}})$ by a random permutation $\pi_{2}$. She publishes $A_{0}$ on blockchain.

5. 5.

   $\mathbf{A}$ computes $m_{\ell}=\textbf{Dec}_{\oplus}(A_{0,\ell})$. If for all $\ell$, $m_{\ell}\neq 0$, then, $\alpha\geq\beta$; otherwise, $\alpha\!<\!\beta$.

Note that the string $\beta_{k-1}\|\beta_{k-2}\|\cdots\|s_{0}$ is regarded as an integer to be encrypted, which can be achieved by choosing appropriate message spaces.

Correctness. $P_{1}$ computes $w_{\ell}\!\!=\!\!(b^{d-\alpha_{\ell}-1+\beta_{\ell}}\!+\!s_{\ell})\bmod b^{d}$. If $\beta_{\ell}\!\!\geq\!\!\alpha_{\ell}+1$ holds, then $w_{\ell}\!\!=\!\!s_{\ell}$. Since the encryptions, $PKE_{2}$ and $PKE_{3}$, are homomorphic, we have $A_{1,\ell}\!\!=\!\!\textbf{Enc}_{2}[(\textbf{Enc}_{\oplus}(\beta_{k-1}\|\!\cdots\!\|\beta_{\ell+1}\|s_{\ell})\cdot$ $\textbf{Enc}_{\oplus}(\!-(\alpha_{k-1}\|\!\!\cdots\!\!\|\alpha_{\ell+1}\|w_{\ell})))^{r_{\ell}}\!]$ and $A_{0,\ell}\!\!=\!\!\textbf{Enc}_{\oplus}[r_{\ell}r_{\ell}^{\prime}(\beta_{k-1}\|\!\cdots\!\|\beta_{\ell+1}\|s_{\ell}\!-\!\alpha_{k-1}\|\cdots\|\alpha_{\ell+1}\|w_{\ell})]$. If there exists only one $\ell$, $s.t.$, $m_{\ell}=0$, then $(\alpha_{k-1}=\beta_{k-1})\wedge(\alpha_{k-2}=\beta_{k-2})\wedge\cdots\wedge(\alpha_{\ell+1}=\beta_{\ell+1})\wedge(w_{\ell}=s_{\ell})$ holds, and the $\ell$-th Boolean expressions is True, $i.e.$, $\alpha<\beta$. Otherwise, if $m_{\ell}\neq 0$ for all $\ell$, then $\alpha\geq\beta$ holds.

Considering malicious $\mathcal{A}_{2}$ who may corrupt $P_{1}$ or $P_{2}$, we improve the comparison protocol of Fischlin [5], where Goldwasser-Micali (GM) [20] encryption is used. The public key is $pk=(n,z)$ while the private key is $sk\!=\!\frac{(p\!-\!1)(q\!-\!1)}{4}$, where $n\!=\!pq$, $p\!\equiv\!q\!\equiv\!3\bmod 4$, $z\!\equiv\!-1\bmod n$. One can encrypt a bit $b$ by computing $c\!=\!r^{2}z^{b}\!\bmod\!n$ with randomly chosen $r$ from $Z_{n}^{\ast}$ and decrypt $c$ by computing $1\!-\!c^{sk}\!\bmod\!n$. GM is homomorphic for encryptions of two bits $b_{1}$ and $b_{2}$: $Enc(b_{1})\cdot Enc(b_{2})\!=\!Enc(b_{1}\oplus b_{2})$ (XOR), $Enc(b_{1})\cdot z\!=\!Enc(1\!-\!b_{1})$ (NOT). For a GM ciphertext $c$, re-encryption is $ReEnc(c)\!=\!c\!\cdot\!Enc(0)$.

AND-homomorphic. GM encryption can be modified to support Boolean AND homomorphic following [28], by which, a single bit is encrypted to $\iota$-element sequence, where $\iota$ is the soundness parameter. $Enc^{AND}(1)\!=\!(Enc(0),\dots,Enc(0))$ and $Enc^{AND}(0)\!=\!(Enc(a_{1}),\dots,Enc(a_{\iota}))$ for $\iota$ randomly chosen bits. The AND-decryption outputs $1$ if each element in the sequence is decrypted to $0$; otherwise, it outputs $0$. This decryption is correct with probability $1\!-\!2^{-\iota}$. For two ciphertexts $Enc^{AND}(b_{1})\!=\!(c_{1},\dots,c_{\iota})$ and $Enc^{AND}(b_{2})\!=\!(c^{\prime}_{1},\dots,c^{\prime}_{\iota})$, $Enc^{AND}(b_{1})\!\cdot\!Enc^{AND}(b_{2})\!=\!(c_{1}\!\cdot\!c^{\prime}_{1},\dots,c_{\iota}\!\cdot\!c^{\prime}_{\iota})\!=\!Enc^{AND}(b_{1}\!\wedge\!b_{2})$ (AND). Re-encryption for AND-encryption is defined as $ReEnc^{AND}(c_{1},\dots,c_{\iota})\!=\!(ReEnc(c_{1}),\dots,ReEnc(c_{\iota}))$.

AND-embedding. An existing GM ciphertext $c$ of bit $b$ can be embedded to AND-ciphertext $Enc^{AND}(b)\!=\!(c_{1},\dots,c_{\iota})$ without decryption. For $\iota$ randomly chosen bits $a_{1},\dots,a_{\iota}$, if $a_{i}\!=\!1$, then set $c_{i}\!=\!Enc(0)$; otherwise, set $c_{i}\!=\!Enc(0)\!\cdot\!c\!\cdot\!z\bmod n$. Such embedding is correct with probability $1\!-\!2^{-\iota}$.

Fischlin [5] proposed secure protocol to compare two integers against semi-honest adversaries, which is a bit-wise comparison. Given $\eta$-bit integers $\alpha$ and $\beta$ with bit representations $\alpha\!=\!\alpha_{1}\dots\alpha_{\eta}$ and $\beta\!=\!\beta_{1},\dots,\beta_{\eta}$, one can compute $\alpha\!>\!\beta$ by evaluating Boolean circuit $F\!=\!\bigvee_{\ell=1}^{\eta}(\alpha_{\ell}\!\wedge\!\neg\beta_{\ell}\wedge\bigwedge_{u=\ell+1}^{\eta}(\alpha_{u}\!=\!\beta_{u})).$ $F\!=\!1$ if and only if $\alpha\!>\!\beta$. $\bigvee_{\ell=1}^{\eta}$ is XOR operation and exactly one term will be 1 if $\alpha\!>\!\beta$; otherwise, all terms will be 0. Moreover, $(\alpha_{u}\!=\!\beta_{u})$ equals $\neg(\alpha_{u}\!\oplus\!\beta_{u})$. Thus, $F$ can be homomorphically evaluated using GM encryption.

We improve the protocol of Fischlin [5] to be a secure three-party scheme against malicious $P_{\!1}$ and $P_{2}$. $\mathbf{A}$ gets the comparison result, while $P_{\!1}$ and $P_{\!2}$ protect their private inputs $\alpha$ and $\beta$. It is assumed that $\mathbf{A}$ will not collude with $P_{1}$ or $P_{2}$. Except for GM encryption, RSA is also used in our scheme. $\mathbf{A}$ generates a GM key pair and publishes the public key before the comparison. For $i\!=\!1,2$, $P_{i}$ generates RSA public/ private key pair $(e_{i},d_{i})$. The private inputs are first encrypted by GM, then encrypted by RSA, such double encryption is called GM-RSA encryption in the following. Since, RSA is multiplicatively homomorphic, the homomorphic properties (NOT,XOR,AND) of GM will not be affected involving only multiplication. In the following, encrypting a sequence means encrypting each element separately.

1. 1.

   $P_{i}$ bit-wisely encrypts its private input by GM into $C_{i}\!=\!(C_{i,1},\dots,C_{i,\eta})$, then, encrypts $C_{i}$ by RSA into $D_{i}\!=\!(C_{i})^{e_{i}}$. To prove the knowledge of the private input, a non-interactive zero-knowledge (NIZK) proof $\pi_{i}$ given below is added. Finally, $P_{i}$ publishes $\langle e_{i},D_{i},\pi_{i}\rangle$ on blockchain.

2. 2.

   $P_{2}$ encrypts $C_{2}$ into $D_{2,1}\!=\!C_{2}^{e_{1}}$ using $e_{1}$ of $P_{1}$ with a NIZK $\hat{\pi}$ proving $C_{2}$ is contained in $D_{2}$ and $D_{2,1}$. $P_{2}$ homomorphically computes all $\neg(\alpha_{u}\!\oplus\!\beta_{u})$ and $\neg\beta_{\ell}$. $P_{2}$ embeds $C_{1}$ and $C_{2}$ into AND-homomorphic GM by manipulating ciphertexts $D_{1},D_{2,1}$. Specifically, $P_{2}$ selects random coins and perform GM-RSA encryption on them, which then multiplied by $D_{1},D_{2,1}$. $P_{2}$ also attaches knowledge proofs $\pi_{2,1}$ of the random coins following the construction of $\pi$ below. For each $\ell\!=\!1,\dots,\eta$, $P_{2}$ then computes a ciphertext $\bar{c}_{\ell}$ of $\bar{b}\!=\!\alpha_{\ell}\!\wedge\!\neg\beta_{\ell}\wedge\bigwedge_{u=\ell+1}^{\eta}(\alpha_{u}\!=\!\beta_{u})$. $P_{2}$ randomly shuffles sequence $(\bar{c}_{1},\dots,\bar{c}_{\eta})$ to $\overline{res}_{2,1}\!=\!shuffle(\bar{c}_{1},\dots,\bar{c}_{\eta})$ by a random permutation $shuffle$ with a NIZK proof $P_{2,1}^{shuffle}$ of $shuffle$ following [29, 30]. Let proof $P_{2,1}^{eval}\!=\!(D_{2,1},\hat{\pi},\pi_{2,1},P_{2,1}^{shuffle})$. $P_{2}$ encrypts $P_{2,1}^{eval}$ into $[P_{2,1}^{eval}]$ by the public key of $\mathbf{A}$ such that the proof is visible only to $\mathbf{A}$. $P_{2}$ puts $\langle\overline{res}_{2,1},[P_{2,1}^{eval}]\rangle$ on blockchain. $P_{\!1}$ performs operations similarly to $P_{2}$ and publishes $\langle\overline{res}_{1,2},[P_{1,2}^{eval}]\rangle$.

3. 3.

   $\mathbf{A}$ verifies $P_{2,1}^{eval},P_{1,2}^{eval}$ by checking the NIZK proofs. Then, $\mathbf{A}$ published the verification results on blockchain.

4. 4.

   $P_{1}$ decrypts $\overline{res}_{2,1}$ by $d_{1}$ into $res_{2,1}$ and puts $\langle res_{2,1}\rangle$ on the blockchain. Similarly, $P_{2}$ publishes $\langle res_{1,2}\rangle$.

5. 5.

   $\mathbf{A}$ can verify correctness of $res_{2,1}$ by re-encrypting (via $e_{1}$) before decrypting. If exactly one $1$ is contained, then $\alpha\!>\!\beta$. Otherwise, $\mathbf{A}$ decrypts $res_{1,2}$. If exactly one $1$ is obtained, then $\alpha\!<\!\beta$. Otherwise $\alpha\!=\!\beta$.

NIZK-$\pi$. For a GM public key $(n,z)$, a RSA public key $(e,N)$, a GM-RSA ciphertext $C\!=\!c^{e}\!=\!(r^{2}z^{b}\!\bmod\!n)^{e}\!\bmod\!N$ of a bit $b$, a prover can prove the knowledge of $b$ in $\kappa$ rounds as in [31]. The prover randomly chooses $\kappa$ numbers $\{r_{i}\}_{i=\!1}^{\kappa}$, and computes $\{A_{i}\!=\!r_{i}^{4e}\}_{i=\!1}^{\kappa}$. With the help of a publicly known random oracle $\mathcal{H}\!:\!\{0,1\}^{\ast}\!\to\!\{0,1\}^{\kappa}$, the prover computes challenges $\gamma\!=\!\mathcal{H}(A_{1},\dots,A_{\kappa})$ regarded as a bit string. The prover concludes the proof by sending responses $(\gamma,\{R_{i}\!=\!(r^{\gamma_{i}}\!\cdot\!r_{i})^{e}\}_{i=\!1}^{\kappa})$. A verifier computes all $A_{i}^{\prime}\!=\!\frac{R_{i}^{4}}{C^{2\gamma_{i}}}$ and accepts if $\gamma\!=\!\mathcal{H}(A_{1}^{\prime},\dots,A_{\kappa}^{\prime})$. The security relies on the security of RSA and the original proof of knowledge $b$ for GM ciphertext in [31].

The proposed comparison protocols can be used for joint bidding [25], which is a multi-party scenario. Joint bidding is a form of alliance and is used extensively in the construction and insurance industries, allowing a group of firms to collectively undertake a big project beyond any single. The logic is to take advantage of the collective size of the group. To choose proper partners, the project owner needs to check their financial assets which they do not like to uncover.

A solution is given and instantiated by the three-party comparison for malicious competitors. In our design, all the firms $\mathbf{B_{i}}$ run parallelized TPIC with the project owner $\mathbf{A}$. At last, $\mathbf{A}$ learns the order of all assets to select needed partners. If the owner wants to choose partners possessing assets more that a prefer value $x$, it can play a role of firm to compare all assets with $x$. $\mathbf{A}$ then chooses firms whose assets is larger than $x$ whilst $x$ is not known to them.

At the beginning, $\mathbf{A}$ broadcasts the GM public key, all firms perform the following scheme.

1. 1.

   Each firm $\mathbf{B_{i}}$ publishes $\langle e_{i},D_{i},\pi_{i}\rangle$ on blockchain committing to assets $y_{i}$. If a prefer value $x$ is needed, $\mathbf{A}$ publishes $\langle e,D,\pi\rangle$ on chain committing to $x$.

2. 2.

   Each $\mathbf{B_{i}}$ computes $\langle\overline{res}_{i,j},[P_{i,j}^{eval}]\rangle$ for all $j\!\neq\!i$ and puts them on blockchain.

3. 3.

   $\mathbf{A}$ verifies all NIZK proofs and publishes the verification results.

4. 4.

   $\mathbf{B_{i}}$ decrypts all $\overline{res}_{j,i}$ into $res_{j,i}$ and publishes them on blockchain.

5. 5.

   $\mathbf{A}$ decrypts $res_{i,j}$ getting the order of all $y_{i}$ (and $x$). Then $\mathbf{A}$ can select proper partners according to the ranking of assets (larger than $x$).

Here, the commitment with deposits can also be used to incentivize honest performance.

The security is guaranteed by theorem 3.3. One can refer to [22] for the time cost for GM encryption and related NIZK proofs. For primes $|p|\!=\!|q|\!=\!768$, 32-bit integers, $\kappa\!=\!\iota\!=\!40$ for soundness error $2^{-40}$, the total time is less than 1s. To guarantee RSA is compatible with GM, we test encryption and decryption time setting $|p|\!=\!|q|\!=\!1152$ on PC (AMD PRO A10-8770 R7, 10 COMPUTE CORES 4C+6G) running at 3.5GHz. The total RSA encryption time for $1280(=\eta\iota)$ times is less than 200ms while 6s for decryption. The time cost is acceptable in the real.

The scheme runs in 4 blocks and the per-firm communication cost in each step is given in table 1, where $\eta$ is bit length for the asset value, $\iota$ is the soundness parameter in AND homomorphic of GM, $\kappa$ is the soundness parameter in NIZK proofs, $|p|$ is the prime size for RSA, $N$ is the number of firms. The communication coat in step 2 does not contain the ciphertexts $[P_{i,j}^{eval}]$. $P_{i,j}^{eval}$ can be encrypted by an alternative scheme instead of GM since GM is a bit-wise encryption, thus consumes much communication.

In this subsection, a general version of three-party comparison is presented by a privacy-preserving auction scheme running in a constant number of rounds. In an auction scenario, $N$ bidders submit bids hoping to win without revealing the bid information while the auctioneer expects to determine a winner with the highest bid. Traditional seal-bid scheme heavily relies on the auctioneer $\mathbf{A}$ who is assumed to be trusted since $\mathbf{A}$ learns all bid information. This dependence will however lead to unfairness as $\mathbf{A}$ may collude with a bidder or leak the bids of the honest to a malicious bidder. On the other hand, a bidder may perform badly to influence the outcome of the auction. In our instantiation, the commitment scheme (CS) with deposits is used to bind bid as well as the ciphertexts with each bidder. The deposits are used to punish bidders with bad behavior like inconsistent commitment or wrong complaint. The three-party protocol for semi-honest competitors is used to compare all bids under ciphertexts to preserve privacy.

Roughly, each bidder $\mathbf{B_{i}}$ is required to run CS to broadcast $CS.Commit_{i}$ on blockchain with some deposits committing to his bid $y_{i}$ and its ciphertexts. He is also supposed to provide a transaction $CS.Fuse_{i}$ for the auctioneer $\mathbf{A}$ with his signature on it. Then, $\mathbf{B_{i}}$ runs TPIC to compare his bid with that of $\mathbf{B_{j}}$ for all $j\!\neq\!i$ in parallel. At the last round of TPIC, $\mathbf{A}$ gets all the comparison results and announces the highest bid holder to be the auction winner. The determined winner $\mathbf{B_{w}}$ should open his commitment on blockchain and other bidders can verify its soundness. A bidder $\mathbf{B_{i}}$ who loses the auction can redeem the deposits by $CS.Open_{i}$ which will disclose the bid information, thus an alternative $CS.Refund_{i}$ is used to return the deposits. $CS.Refund_{i}$ contains no bid information and is valid only signed by both $\mathbf{B_{i}}$ and $\mathbf{A}$. If a complainer $\mathbf{B}$ submits a complaint towards $\mathbf{B^{\prime}}$, $\mathbf{B}$ is required to open his commitment to $\mathbf{A}$ for consistency verification. Then they run TPIC again, after which $\mathbf{A}$ gets the result and penalizes the loser by broadcasting the transaction $CS.Fuse$ on blockchain to confiscate his deposits before exclusion. The punishment is necessary to prevent bid information extraction from malicious comparisons by continuous complaint submission, because each comparison will reveal a lower or upper bound of the bid. Finally, $\mathbf{A}$ signs the transaction $CS.Refund$ from the honest bidders and broadcasts them on blockchain to return their deposits.

Specifically, all bidders and the auctioneer negotiate a hash function $\mathcal{H}$ and the deposits value used in the commitment. Each $\mathbf{B_{i}}$ runs both $\mathbf{Gen}_{1}(1^{\lambda})$ and $\mathbf{Gen}_{2}(1^{\lambda})$ to generate the key pairs $(\mathcal{PK}^{1}_{i},\mathcal{SK}^{1}_{i})$ and $(\mathcal{PK}^{2}_{i},\mathcal{SK}^{2}_{i})$ while $\mathbf{A}$ runs $\textbf{Gen}_{\oplus}(1^{\lambda})$ to get the key pair $(\mathcal{PK}_{3},\mathcal{SK}_{3})$. They all publish their public keys, and then run the following parallelized TPIC, where $N$ is the number of bidders, $i,j\!\in\!\{1,2,\dots,N\},i\!\neq\!j$, and $m_{i,j}$ denotes that the message $m$ in TPIC is computed by $\mathbf{B_{i}}$ and transferred to the target receiver $\mathbf{B_{j}}$.

1. 1.

   Each $\mathbf{B_{i}}$ encrypts $y_{i}$ into $C_{i}$ via $PKE_{1}$, and computes $H_{y_{i}}^{C_{i}}\!=\!\mathcal{H}(y_{i}\|C_{i}\|S_{i})$ with a random string $S\!_{i}$ as his commitment. $\mathbf{B_{i}}$ creates two transactions $(CS.Fuse_{i},CS.Refund_{i})$ and encrypts them by $\mathcal{PK}_{\!3}$ of $\mathbf{A}$ into $[CS.Fuse_{i},CS.Refund_{i}]$. Finally, $P_{\!1}$ broadcasts

   $$\langle H_{y_{i}}^{C_{i}},C_{i},[CS.Fuse_{1},CS.Refund_{1}]\rangle$$

   on blockchain by a transaction $CS.Commit_{i}$ with some deposits;

2. 2.

   $\mathbf{B_{i}}$ computes $(D,A_{2})_{i,j}$ for all $j\neq i$ and puts them on blockchain;

3. 3.

   $\mathbf{B_{i}}$ computes $(A_{1})_{i,j}$ for all $j\neq i$ and publishes them on blockchain;

4. 4.

   $\mathbf{B_{i}}$ computes $(A_{0})_{i,j}$ for all $j\neq i$ and posts them on blockchain;

5. 5.

   For $\ell=k-1,\dots,0$, $\mathbf{A}$ computes $(m_{\ell})_{i,j}=\textbf{Dec}_{\oplus}((A_{0,\ell})_{i,j})$. If $\exists i$ for $\forall j\neq i,\forall\ell$, $(m_{\ell})_{i,j}\neq 0$, then $\mathbf{A}$ determines $\mathbf{B_{i}}$ to be the winner who is required to open his commitment for public verification.

6. 6.

   If a complainer $\mathbf{B}$ submits a complaint towards $\mathbf{B^{\prime}}$ on blockchain, then he is required to reveal $y\|C\|S$ to $\mathbf{A}$ for consistency verification. If it is not consistent, $\mathbf{A}$ penalizes $\mathbf{B}$ by broadcasting his $CS.Fuse$ on blockchain confiscating his deposits. Otherwise, they run TPIC with the complained bidder, after which, $\mathbf{A}$ gets the result and penalizes the loser who is excluded from now on. Finally, $\mathbf{A}$ signs the transaction $CS.Refund$ from the honest bidders and broadcasts them on blockchain to return their deposits.