IJNSA 02

SPDZ-BASED OPTIMISTIC FAIR MULTI-PARTY
COMPUTATION

Chung-Li Wang
Alibaba Inc., Sunnyvale, California, USA

ABSTRACT
The fairness of multi-party computation has been investigated for long time. Classic results demonstrate that fair exchange can be achieved by utilizing cryptographic tools, as most of them are based on garbled circuits.For the secret-sharing schemes, such as SPDZ, it may incur significant overhead to simply apply a fair escrow scheme, since it encrypts all the shares of delivered results. To address this issue, we design a twolevel secret-sharing mechanism. The escrow encryption is only for the first level of sharing and performed in preprocessing. The second level of sharing is used for computation and always handled by plaintexts, such that the online phase is still efficient. Our work also employs a semi-trusted third party (TTP) which provide optimistic escrow for output delivery. The verification and delivery procedures prevent the malicious parties from corrupting the outcome or aborting, when there is at least one honest party. Furthermore, the TTP has no knowledge of output, so even if he is malicious and colluding, we only lose fairness. The escrow decryption is needed only when misconduct is detected for opening the first-level shares.

KEYWORDS
Optimistic Multi-Party Computation, Secret-Sharing, Verifiability, Fairness, Semi-Trusted Third Party

1. INTRODUCTION
In recent years, secure multi-party computation (MPC) has gained widespread attention from researchers due to its capability to securely aggregate data from multiple users and produce powerful results. SPDZ [1] and its variants (e.g., [2]-[3]) have played significant rolesin the success of MPC. These protocols have two phases: an input-independent offline phase for preprocessing and an input-dependent online phase that is highly efficient. However, a single malicious party can cause the computation to fail by deviating from the protocol or providing false results. In this scenario, honest parties are unable to learn the outcome of the computation, while the malicious party may still gain access to it. It is investigated in [7] and proven to imply robustness assuming a broadcast channel.

Fairness. The fairness is defined as the property that corrupted parties should not be able to prevent honest parties from receiving their output. In general, this property can be achieved by using cryptographic tools as in [8] and [9]. The escrow scheme [9] integrated garbled circuits and an optimistic escrow scheme with a semi-trusted third party. However, for SPDZ-like protocols, these similar approaches were all considered to be unaffordable, as discussed in [4]. As a consequence, the protocols with identifiable abort in [3] and [4][4] have to publicly reconstruct the secret before verifying the result, allowing corrupted parties to learn the output even though they cheated. The work in [12] uses threshold-t secret-sharing to support fairness and robustness. Despite of its better efficiency and usability, when the number of dishonest parties is not known, it is difficult to choose appropriate design parameters. For example, in its design only t server parties are needed to corrupt to obtain the secret without public opening. As a result, even with identifiable abort and verifiability, if a malicious majority is assumed, having fairness is still an open problem for someof secret-sharing schemes.

Our Contribution. In the standard model, it is impossible to guarantee fairness with corrupted majority [17]. To overcome this impossibility, many protocols (e.g. [10]) have been proposed to achieve fairness in non-standard models using a trusted third party (TTP). The proposed solution is a public auditable MPC with identifiable abort and fairness using an optimistic escrow phase. Similarly as in SDPZ, the framework has the offline preprocessing phase and online computation phase. Our scheme uses a novel two-level secret sharing, the first-level is input-independent and randomly generated in the offline preprocessing, and the second-level is used in the online computation with correlated randomness.

Efficient Online Phase. Parties that engage in manipulating the computation can be identified by examining their commitments. A TTP manages the escrow scheme, which is not needed if all parties behave honestly for opening the shares. Our scheme provides better privacy than [13] asthe TTP does not participate in the outcome delivery. Besides, if the TTP is dishonest, we only lose fairness and robustness, and the protocol is still public auditable with identifiable abort. The escrow scheme requires cryptographic tools, but our protocol takes advantage of two-level sharing and has the complexity overhead in the offline phase.

Verifiable Offline Phase. Our scheme improves upon the approaches in Overdrive’s LowGear [5] to compute two-level shares of random values and triples in a single, trackable routine. The correctness and fairness of the computation is guaranteed by verifying the zero-knowledge proof (ZKP) of encrypted shares. This creates a checkpoint and adds an extra layer of security and auditability. In addition, our verification covers the generation of multiplicative triples and thus does not need an additional information-theoretic check as in [3].

Related Works. Typical approaches to have fairness involves employing semi-trusted third partiesor other assumptions. [8] proposed an optimistic fair exchange using a TTP, and then it was recently shown that fair computation can be achieved by similar techniques in [9], [10], and [14], in which the output is encrypted and requires a third party to support a verifiable escrow scheme. As the encryption of shares demands excessive overhead in the online phase, this way is too expensive for SPDZ protocols. To save verification overhead, the trusted service is used in [14] but not assumed in this paper, but our work can be adapted in that case. An MPC with identifiable abort is proposed in [12], where fairness is obtained by t-secure secret-sharing when t or more servers are honest. A cryptographic solution, described in [13], is suggested to achieve fairness, but it incurs high complexity and relies on the TTP for decryption. We delay the in-depth comparisons of related works in the last chapter.

2. OVERVIEW
2.1. Security Model
Before designing the specific implementation, we must first establish the security model. Secure computation in the standalone model is defined through the real-ideal world paradigm. Throughout this paper, we will consider protocols that are executed over a synchronous network with static and rushing adversaries. In the real world, all parties communicate through the protocol Π, while in the ideal world, the parties send their inputs to an ideal functionality ℱ, also known as the trusted party, which computes the desired function 𝒞 and returns the result to the parties. In informal terms, the protocol Π is considered to securely realize the functionality ℱ if, for every real-world adversary 𝒜, there exists an ideal-world adversary 𝒮 (also known as the simulator) such that the joint output distribution of the honest parties and the adversary 𝒜 in the real world is indistinguishable from the joint output distribution of the honest parties and 𝒮 in the ideal world.

The security requirements of the protocol are defined through the concept of ideal functionality with Public Accountability with Output Fairness (PAOF). In this setup, there is a polynomial-time honest party 𝑃𝐴, that can retrieve all the output messages from the trusted party, assess theircorrectness, and output the correct result and/or a set of parties 𝐿, that are deemed responsible for any misbehavior. The output of the protocol is in the form of a 2-tuple (𝑦, ⊥), (𝑦, 𝐿), or (⊥, 𝐿).

The Ideal Model with PAOF. Assume 𝒫 = {𝑃𝑖}𝑖∈{𝑛} to be the set of computing server parties, ℐ = {𝐼𝑘}𝑘∈{𝑚} the set of input client parties, 𝐷 ⊂ 𝒫 the set of corrupted computing parties, and 𝒟𝐼 ⊆ ℐ the set of corrupted input parties. Before the execution, the non-adaptive adversary 𝒜 decides ℒ𝐼 ⊆ 𝒟𝐼 and ℒ𝑓, ℒ𝑝, ℒ𝑜, ℒ𝑘 ⊆ 𝒟. Let ℒ𝐼 be the set of input parties hanging or giving illformed inputs, ℒ𝑝 be the set of computing parties manipulating the computation results, ℒ𝑜 be the set of computing parties cheating with the ciphertexts of MUSS ciphers, and ℒ𝑘 be the set of computing parties cheating with the plaintexts of MUSS ciphers. With 𝑚 ≤ 𝑛, the evaluation function 𝒞 has 𝑚 input and 𝑚 output gates. The execution of ideal model with PAOF is denoted as ℱOnline, which is briefly described as follows.

Inputs: The i-th party’s input is denoted by 𝑥𝑖 and 𝒙 = (𝑥1 … , 𝑥𝑛). We assume that all valid inputs are defined in 𝔽. The adversary receives an auxiliary input 𝑧. Initialization: The trusted party informs the adversary 𝒜 of the beginning of execution with the parameter set (𝒞, 𝔽, 𝔾). 𝒜 sends the lists of malicious parties that corrupt the input and evaluation outcome to the trusted party. This decision is made by 𝒜 and may depend on (𝒞, 𝔽, 𝔾) and the auxiliary input 𝑧. If misconduct is detected, the trusted party will catch ℒ𝑓 and abort the process.

Send Inputs to Trusted Party: Any honest party 𝐼𝑖 sends its input 𝑥𝑖 to the trusted party. The corrupted parties, controlled by 𝒜, may either send their received input or send some other input to the trusted party. This decision is made by 𝒜 and may depend on the input from the corrupted parties and the auxiliary input. If the invalid input is from 𝐼𝑖 ∈ ℒ𝐼 , the trusted party will catch 𝐼𝑖 and abort the process

Compute: For the i-th gate 𝑓𝑖 ∈ 𝒞, the trusted party computes 𝑦𝑖 = 𝑓𝑖 (𝒙) for computation gates, and for output gates it sets the outcome to ⊥ with replying Reject if the computation or output is corrupted. Otherwise it replies Accept.

Trusted Party Answers Auditor: Upon the request by the auditor, the trusted party outputs ℒ𝑝 with
Reject or replies Accept if no cheating is found.

Open: Upon the request by all parties, the trusted party outputs the result 𝒚, if no misbehaviour occurs. Or it sends out ℒ𝑜 if the ciphertexts of MUSS ciphers fail the verification, and it sends ℒ𝑘 if the plaintexts of MUSS ciphers are incorrect. Then if the TTP 𝑃𝑇 is honest, 𝒚 will be delivered fairly to all parties. If 𝑃𝑇 actively corrupts the decryption, the ideal model only loses fairness, and 𝑃𝑇 will be identified.

The Real Model with PAOF. Let us consider the real model in which a real 𝑛-party protocol Π is executed with the set of 𝑛 computing parties, 𝑚 input parties, and trusted honest parties 𝑃𝐴 and 𝑃𝑇. Let 𝒟 and 𝒟𝐼 denote the set of corrupted computing and input parties, controlled by an adversary 𝒜. In this case, the adversary 𝒜 sends all messages in place of corrupted parties, and may decide a polynomial-time strategy arbitrarily. In contrast, the honest parties follow the instructions of Π. Then the real execution of Π on inputs 𝒙, auxiliary input 𝑧 to 𝒜, and security parameter 𝜆, denoted by RealΠ,𝒜(𝑧),{𝒟,𝒟𝐼 }(𝒙, λ), is defined as the output vector of the honest parties and the adversary 𝒜 from the real execution of Π.

Definition 1 (PAOF): Let 𝒞 be a circuit with inputs 𝒙. A protocol Π is called publicly accountable with output fairness whenever one computing party, 𝑃𝐴, and 𝑃𝑇 are honest, for every non-uniform probabilistic polynomial-time adversary 𝒜 for the real model, there exist a non-uniform

Figure 1. . Ideal functionalities for the commitment, random oracle, and public bulletin.

probabilistic polynomial-time adversary 𝑆 for the ideal model ℱOnline such that for every
𝒟⊂ 𝒫, 𝒟𝐼 ⊆ ℐ, every balanced vector 𝒙 ∈ 𝔽 𝑚, and every auxiliary input 𝑧 ∈ 𝔽:
IdealℱOnline,𝑆(𝑧),{𝒟,𝒟𝐼 }(𝒙, λ) =𝑐 RealΠ,𝒜(𝑧),{𝒟,𝒟𝐼}(𝒙, λ)
in any sense, the following theorem will be proven in the full version by constructing a protocol in
the ℱOnline-hybrid model.

2.2. Important Blocks
Let 𝔾 be some Abelian multiplicative subgroup of order 𝑞 where the DLP is hard to solve (with respect to a given computational security parameter λ). The protocol will evaluate a circuit 𝒞 over 𝔽 = ℤ𝑞 whereas we use the group 𝔾 to commit to the output. We let 𝑔, ℎ ∈ 𝔾 be two generators of the group 𝔾 where 𝑔 and ℎ are chosen by some random oracle with a common reference string (CRS) as the input.

We assume a secure point-to-point network between all parties and a broadcast functionality. We also use the commitment functionality ℱCom, the random oracle ℱRnd for giving a random value over 𝔽 to all parties, and the bulletin ℱBlt to handle all communication, such that nothing in the bulletin can ever be changed or erased. These functionalities are outlined in Figure 1.

2.2.1 Novel Secret-Sharing
The online phase of the computation is conducted using the novel two-level sharing scheme,
which is defined as below:
Definition 1 (MUSS): Let x, y, e ∈ 𝔽, 𝜶 = (𝛼1, . . . , 𝛼𝑛) and then the Multiplicative-Ciphered Secret-Sharing of x is defined as [𝑥]𝜶 = ((𝑥1, . . . , 𝑥𝑛), (𝑥̃1, . . . , 𝑥̃𝑛)) , where the correlation x = ∑ 𝛼𝑖𝑛𝑖=1 𝑥𝑖 = ∑𝑥̃𝑖𝑛=1holds. Since the keys 𝜶 are fixed for the whole session, [𝑥]𝜶 can be denoted as [𝑥] without confusion. Each player 𝑃𝑖 will hold its MUSS shares 𝑥𝑖 and 𝑥̃𝑖 of [𝑥]. The key 𝛼𝑖 for

𝑃𝑖 is additively shared by all players, such that every player has 𝛼𝑖𝑗 and 𝛼𝑖 = ∑ 𝛼𝑖𝑗𝑛𝑖=1
. Moreover,we define [𝑥] + [𝑦] = ((𝑥1 + 𝑦1, . . . , 𝑥𝑛 + 𝑦𝑛), (𝑥̃1+𝑦̃1, . . . , 𝑥̃𝑛+𝑦̃𝑛)) , 𝑒 ∙ [𝑥] = ((𝑒 ∙ 𝑥1, . . . , 𝑒∙𝑥𝑛), (𝑒 ∙ 𝑥̃1, . . . , 𝑒 ∙ 𝑥̃𝑛)). We say that [𝑥] ≜ [𝑦] if the shares of x, y in [𝑥], [𝑦] reconstruct to the same value.

Obviously, MUSS is linear. If all parties agree to apply one of defined linear functions, then they can perform these on the MUSS shares without interaction. For the addition between the MUSS share and a public value 𝑒, one needs to open a random MUSS share (e.g. [𝑟]) as a gadget, so [𝑒 + 𝑥] = [𝑥] + (𝑒𝑟−1) ∙ [𝑟].

Security and Privacy. Assuming the sharing of two secrets 𝑎 = 𝛾𝑑 + 𝛿𝑐 and 𝑎′ = 𝛾𝑑′ + 𝛿𝑐′, when opening the encoded shares (𝑑, 𝑐) and (𝑑′, 𝑐′), the question is that, if there is any advantage of guessing the secret 𝑎 and 𝑎′. The answer is no. Since [𝑑 𝑐  𝑑′ 𝑐′] is a full-rank matrix with a probability close to 1 [24], 𝑎 and 𝑎′ are indistinguishable to two independent uniform random samples. Formally, we have the following theorem to show the security of opening encoded shares:

Theorem 1 (Perfect Secrecy): Assume a cipher ℋ = (𝔽𝑚, 𝔽𝑛,𝐾𝐺, Φ, Ψ) with message space 𝔽𝑚and key space 𝔽𝑛 that a probabilistic PTTM Φ: 𝔽𝑚 × 𝔽𝑛 → 𝔽𝑚𝑛 and Ψ: 𝔽𝑚𝑛 × 𝔽𝑛 → 𝔽𝑚 with the definition Ψ (𝐃,𝐠) → 𝐃𝐠 𝑇 = 𝒂 = (𝑎1 … , 𝑎𝑚) with 𝐃 = {𝑑𝑖,𝑗} 𝑖∈{𝑚},𝑗∈{𝑛} and 𝐠 = (𝑔1 … 𝑔𝑛) for m≤ 𝑛. If 𝐃 has full rank, and 𝐠 is statistically indistinguishable from samples drawn from uniform random distribution in 𝔽𝑛, the scheme ℋ has perfect secrecy except a negligibleprobability.

The additive sharing with MAC in SPDZ is vulnerable to corruption by two collusive parties who lie about their shares without altering the sum. This renders Lemma 1 in [3] false, as the parties can deviate from the protocol and still pass the check. Despite this, the corruption can still be detected during the audit, and therefore, it does not undermine the security proof of [3]. However, the maliciously controlled share values can reduce the security level and lead to information leakage, which may give an advantage to an eavesdropper. Our work overcomes this issue by using random MUSS ciphers, resulting in a negligible success probability of such cheating.

2.2.2 Commitment Scheme
The proposed protocol forces the result given by the computing parties to be bound by a public witness. First, the parties have to commit the input by sending commitment to the bulletin. Since the commitment scheme uses a one-way function with homomorphic property, the expected commitment of output can be derived by a public auditor. The ways to catch the cheater include checking if each share opens the commitments correctly (as in [3]), and letting the party provide ZKP to prove its ability to give the correct decommitment (as in [12]). Our commitment scheme has a similar format as in [3]: we carry both the MUSS share of secret [𝑥] as well as the MUSS share of randomness [𝑟] of the commitment throughout the whole computation. The commitment handle to a value 𝑥 is a Pedersen commitment 𝖤(𝑔,ℎ)(𝑥, 𝑟) = 𝑔𝑥ℎ𝑟 with 𝖤(𝑔,ℎ)([𝑥],[𝑟]) =((𝑔𝑥1ℎ𝑟1, … , 𝑔𝑥𝑛ℎ𝑟𝑛), (𝑔𝑥̃1ℎ𝑟1̃, … , 𝑔𝑥̃𝑛ℎ𝑟𝑛̃)). When opening MUSS shares, we reconstruct the

Figure 2. ΠOnline: Protocol for the online phase (Part 1)

secret through either 𝑥𝑖 or 𝑥̃𝑖, and the randomness (𝑟𝑖 or 𝑟̃𝑖) is also revealed. For simplicity, since (𝑔, ℎ) is fixed within one session, 𝖤(𝑔,ℎ)([𝑥],[𝑟]) can be denoted as 𝖤([𝑥],[𝑟]). As discussed in [4], the computation of commitments is excluded in the circuit evaluation and invoked only after

Figure 3. ΠOnline: Protocol for the online phase (Part 2).

the failure of information-theoretic checks. This “on-demand” scheme yields favorable saving,
especially when the adversary cheats at a lower rate in a large circuit.

The online phase of our protocol uses ℱ Offline for offline preprocessing that is demonstrated in the full version of the paper. The commands of ℱOffline support single-instruction multiple-data (SIMD) processing with factors σ𝑓. Taking 𝑚 inputs, the circuit 𝒞 over 𝔽 has νin input gates, νmul multiplication gates, and 𝑚 output gates, with 𝑚 ≤ 𝑛, the number of computing parties. The online phase is presented in Figure 2 and Figure 3, which evaluates the circuit 𝒞 of 𝑚 input gates and m output gates. The stages Input and Compute are executed for each input and function gate of 𝒞, respectively, and Initialization, Audit, and Open are invoked only once per circuit.

Initialization. The ideal functionality of the offline phase ℱOffline sets up the MUSS ciphers. The commitment scheme obtains the key from the random oracle 𝒦. The public-key infrastructure (PKI) is given by ℋ and will be elaborated in Sec. 3.3.1. The TTP publishes the global public key 𝑝𝑘𝑜. Each computing party 𝑃𝑗 privately keeps the additive shares 𝛼𝑖,𝑗 for 𝑖 ∈ {𝑛}, where we set ∑𝑖∈{𝑛} 𝛼𝑖,𝑗𝛼𝑖. With 𝜶̅𝑗 = {𝛼𝑖,𝑗}𝑖∈{𝑛}, 𝑃𝑗 commits to 𝜶̅𝑗 toward ℱBlt by 𝑑𝑗 = 𝖤(𝒈,ℎ)(𝑛)(𝜶̅𝑗, 𝛽𝑗) and encrypts (𝜶̅𝑗, 𝛽𝑗) to have 𝑐𝑗 = ⟦(𝜶̅𝑗, 𝛽𝑗)⟧𝑝𝑘𝑜 along with its ZKP ζ𝑗 to show the same plaintexts of 𝑐𝑗 and 𝑑𝑗 The generation and verification of ζ𝑗 will be provided in Sec. Error! Reference source not found.. Finally, the protocol asks the functionality ℱOffline to generate random values and multiplication triples. ℱOffline has its own check and audit for the output to ensure each player to have the correct share values as they committed to. If the misconduct is detected in ℱOffline, the malicious parties will be identified as 𝐿𝑓, and the protocol will be aborted.

Input. Each input client party in 𝐼 is allowed to submit a value to the computation, where two random values are secretly opened to it. The client can then check that the commitment is correct, and blinds its input using the opened values. Here the protocol can only detect the blatant cheating,such as hanging or ill-formed input, we cannot prevent the malicious input client from giving an incorrect blinded input. 

Compute (Add and Multiply). The protocol uses the linearity of the MUSS shares to perform linear operations on the shared values, and multiplies two representations using the multiplication triples from the preprocessing using the circuit randomization technique [18]. The multiplication requires to reconstruct values, and this is done by only opening the plain shares to keep the ciphers private. We do not check the recovered values in this stage and defer the check to the output gate.

Compute (Out). First, we check all the multiplications in the circuit by ΠChkPln σ (Figure 6 and cf.Sec. 3.1.2) for the opened plain shares, where checking ⟨𝜂⟩, ⟨𝜌⟩, and ⟨𝑡⟩ takes random values ⟨𝜂′⟩, ⟨𝜌′⟩, and ⟨𝑡′⟩ as additional input. Then the encoded shares of output are published, and the correlation is checked by using the protocol ΠChkEnc σ (Figure 4 and cf. Sec. 3.1.1). If any of them fails, the auditor 𝑃𝐴 will invoke Audit. If both checks output Accept, all parties will invoke Open to output the result.

Audit. There are two audit procedures in the online protocol, which will be invoked by 𝑃𝐴 when the precedented information-theoretic checks fail. One is to check the plain shares opened in Multiply, and the other is to check the encode shares for output delivery. If the audit passes, it means that the encoded shares are correct, and we are still going to Open. Please be noted that we do not identify anyone regarding the misbehavior happening in ΠChkEncσ and ΠChkPln σ since it eventually does not prevent opening.

Open. Once all the parties agree that encoded shares are correct, each computing 𝑃𝑗 will broadcast the ciphertext 𝑐𝑗, commitment 𝑑𝑗, and ZKP ζ𝑗 to all the other parties, so all parties can verify the correctness using an RO 𝒵 (cf. Sec. Error! Reference source not found.). If the check fails, the process will be aborted here. If 𝑐𝑗 is correct, 𝑃𝑇 opens the global secret key, and all computing parties release the plaintext shares 𝛼𝑖,𝑗  If 𝑃𝑇 gives the correct key, or the plaintexts are correct, the result will be known to everyone. Otherwise 𝑃𝑇 or malicious parties that give the corrupted key, ciphertexts, or plaintexts will be identified.

The security of ΠOnline is proven in Sec. 4.1 by the following theorem.
Theorem 2 (Online Security): In the (ℱOffline ,ℱBlt,ℱCom,ℱKGD )-hybrid model with random oracles 𝒦 and 𝒵, the protocol ΠOnline implements ℱOnline with computational security against any static adversary corrupting all parties except one computing party and the auditor 𝑃𝐴 if the DLP is hard in the group 𝔾.

Next, we introduce present how to check the correlation without opening the cipher, and how to check the opened plain shares used in Multiply.

3.1.1 Check and Audit for Encoded Shares
In the online phase, we use a purely information-theoretic check as the first step of verification. The advantage of checking the correlation before the audit is lower complexity for optimistic models. Moreover, since the correctness of shares is eventually verified by the audit, we will not identify the cheater that corrupts the correlation check. This keeps the design simple. The MUSS correlation can be used to verify the opened shares, and thus we call this “correlation check” and use it as the first step of the delivery, playing the same role of MAC in [4] as an effective way to verify the output. The correlation check protocol ΠChkEncσ for the published encoded share is summarized in Figure 4 which keeps the share 𝑥𝑖(𝑘)and cipher key 𝛼𝑖 private. The protocol is designed to verify σ shares simultaneously by using a random vector 𝒘. The correctness and soundness are stated as in following lemma, and the proof is omitted due to the length limit.

Figure 4. ΠChkEnc σ : Protocol for the correlation check of encoded shares

Lemma 1 (Correlation Check for Encoded Shares): The protocol ΠChkEnc σ is correct, i.e. it accepts if the encoded shares (𝑧𝑖(𝑘), 𝑟𝑖(𝑘)) for all 𝑖 ∈ {n} and 𝑘 ∈ {σ} are correctly computed as defined in Def. 2. Moreover, it is sound, i.e. it rejects except with probability 𝑜(1/𝑞) in case at least one (𝑧𝑖(𝑘), 𝑟𝑖(𝑘)) is notcorrectly computed, or any server deviates from the protocol.

If ΠChkEncσpasses, the encoded shares (𝑧𝑖(𝑘), 𝑟𝑖(𝑘)) are verified, and 𝒛 is ready to be recovered once the key 𝜶 is opened. If it returns Reject, we are not sure if the encoded shares are incorrect, some parties lied on the check outcome, or both happen, so in Audit 𝑃A needs to verify the expected commitments to find out the cause. The audit protocol is demonstrated by ΠAudit in Figure 5. If the audit passes, the encoded shares are verified, the protocol still goes to output delivery. If both the check and audit fail, the encoded shares are considered incorrect, and the malicious parties that corrupt the output will be identified in the audit. The audit protocol can be accelerated by the technique in [3].

Not only the encoded shares but also the plain shares opened for multiplication need to go for the audit, if they fail the correlation check. In the online protocol, all shares that need audit are taken care of in one stage, such that batch processing can give additional efficiency improvement. The check of plain shares is more complicated than that of encoded shares and will be described in the
next section.

3.1.2 Check for Plain Shares
The correlation check protects the computations defined in Def. 2, not including the multiplication, because it uses three random values which are obtained from opening the plain shares of ⟨𝜂⟩, ⟨𝜌⟩, and ⟨𝑡⟩. We need a correlation check for the opened plain shares, which is described as ΠChkPlnσ in Figure 6. The approach is similar except using random shares ⟨𝒔⟩ and secret value 𝑣𝑖 for hiding the encoded shares 𝑧𝑖(𝑘) and 𝑟𝑖(𝑘). Its correctness and soundness are stated in following lemma, and the proof is omitted due to the length limit. If ΠChkPln σ fails, the auditor 𝑃A will check the commitments in the audit stage.

Figure 5. ΠAudit: Sub-protocol for the audit of encoded shares.

Lemma 2 (Correlation Check for Plain Shares): The protocol ΠChkPlnσ is correct, i.e. it accepts if the plain shares (𝑧̃𝑖(𝑘), 𝑟̃𝑖(𝑘)) for all 𝑖 ∈ {n} and 𝑘 ∈ {σ} are correctly computed as defined in Def.2. Moreover, it is sound, i.e. it rejects except with probability 𝑜(1/𝑞) in case at least one(𝑧̃𝑖(𝑘), 𝑟̃𝑖(𝑘)) is not correctly computed, or any server deviates from the protocol.

3.2 Fairness
We see that if the encoded shares of random values and triples are statistically indistinguishable from the samples from uniform distribution, and then those of the immediate values and final results have the same property. This implies fairness property. Proposition 1 (Fairness): The protocol  ΠOnline has public accountability and fairness, that is, themalicious parties know the result only if the honest ones know. If the TTP 𝑃𝑇 is malicious and colluding with other adversarial parties, ΠOnline still has  public accountability in the hybrid modelwith ℱOffline, ℱRnd, ℱCom, ℱBlt, 𝒵, and 𝒦, if one computing party and 𝑃𝐴 are honest.

Remark 1: Until Open of ΠOnline, 𝑃𝑇 has no information of the output result, since any set of n −1 shares are indistinguishable to samples from uniform distribution. The adversary gains no advantage from the existence of malicious 𝑃𝑇. During the Open stage of ΠOnline, by providing an incorrect key, 𝑃𝑇 is only able to prevent the output delivery and cannot modify the output. If 𝑃𝑇 is colluding, the adversary will know the result before the honest parties but cannot force the protocol to output wrong results. Besides, if 𝑃𝑇 can be assumed to be honest, we can modify the protocol and model such that the global key g eneration only needs to be invoked once. Furthermore, withhonest 𝑃𝑇, Step 1 of the Open stage can be done in the offline phase.

3.3 Offline Phase
The protocol ΠOffline describes the full offline phase in Figure 7. Here we give a view to integrate all ideas that will be discussed later. During Initialize the parties will generate two key pairs to encrypt random MUSS ciphers α𝑖 and the key (𝑔, ℎ) for the commitment scheme. With encrypted

Figure 6. ΠAudit: Sub-protocol for the audit of encoded shares.

ciphers, Single uses the procedure ΠComShrσ which generates random MUSS shares, together with commitments to the values. For multiplication triples, ΠGenTrpσ computes a product of the two random values and output them with commitments in Triples. These sub-protocols can be found in Figure 8. If we assume the presence of at least one honest server and that the adversary has a static strategy to corrupt the servers, ΠCPRZKσ(Error! Reference source not found.) and ΠChkZKP σ(Error! Reference source not found.) work as the audit to ensure that the following properties hold:

• All commitments of shares have ZKP’s. All ciphertexts and commitments of MUSS ciphers
have ZKP’s, which are verified in the online phase.
• The procedure ΠCPRZK 𝜎 was executed such that the ciphertexts of MUSS ciphers were correctly
encrypted from the plaintexts.
• The procedure ΠChkZKP𝜎 was executed such that the generation of shares followed the protocol, otherwise the malicious parties that cheat in Single and Triples of ΠOffline were identified. The security of offline protocol is provided as below with the proof deferred to Sec. 4.2. The reader can refer to [26] for the details of ΠChkZKP𝜎, which are omitted here.

Theorem 3 (Offline Security): Let ℋ be a semi-homomorphic cryptosystem. Then ΠOfflineimplements ℱ Offline with computational security against any static adversary corrupting all parties but one honest computing party and auditor in the (ℱKGD, ℱCom, ℱBlt)-hybrid model if the DLP is hard in 𝔾.

While we do not consider guaranteed output delivery for the offline phase, we compose playerelimination on the online phase, that invokes a copy of the offline phase to achieve the robustness.Since information is revealed due to the failed audit, everything will need to be generated again fora newly setup copy in the next iteration.

3.3.1 Distributed Encryption

Figure 7. ΠOffline: Protocol for the offline phase.

We have a semi-homomorphic encryption scheme ℋ = (𝖪𝖦, 𝖤𝗇𝖼,𝖣𝖾𝖼,⊕,⊗) with a message space 𝔽 and randomness distribution 𝜒. The ciphertext encrypted by 𝐻 is denoted as ⟦𝑥⟧𝑝𝑘∶= 𝖤𝗇𝖼𝑝𝑘(𝑥, 𝑟) with key pair (𝑝𝑘, 𝑠𝑘). In addition, ℋ has a predicate 𝐂𝐨𝐫:{0, 1}𝑛(λ) × {0, 1}𝑛(λ) × {0, 1}𝑛(λ) × {0, 1}𝑛(λ) → {0,1}

Figure 8. Sub-protocols for the generation of MUSS shares.

(𝑝𝑘, 𝑐, 𝑥, 𝑟) → 𝐂𝐨𝐫 (𝑝𝑘, 𝑐, 𝑥, 𝑟), that maps to 1 if 𝑝𝑘$← 𝖪𝖦(1𝜆), 𝑥 ∈ 𝔽, 𝑟$← 𝜒 and c ← 𝖤𝗇𝖼𝑝𝑘(𝑥, 𝑟), but otherwise indicates that at least one of these four conditions are not true. The operator ⊕ then guarantees that 𝖣𝖾𝖼𝑠𝑘(⟦𝑥 + 𝑦⟧𝑝𝑘) = 𝖣𝖾𝖼𝑠𝑘(⟦𝑥⟧𝑝𝑘 ⊕ ⟦𝑦⟧𝑝𝑘), whereas we do not use homomorphic multiplication. The scalar multiplication ⊗ guarantees that 𝖣𝖾𝖼𝑠𝑘(𝑦 ⊗ ⟦𝑥⟧𝑝𝑘) = 𝖣𝖾𝖼𝑠𝑘( ⟦𝑥 ∙ 𝑦⟧𝑝𝑘).In addition, we require the interactive functionality ℱKGD that will be used for the preprocessing.The key pair can be securely generated by a key-generation protocol, where the secret key is

Figure 9. Sub-protocols for the generation of MUSS shares.

additively shared by all parties. The ciphertext can be jointly decrypted by yielding the plaintext publicly from all parties, or providing it to a specific party privately.

3.3.2 Generation of Multiplicative Ciphers
The ciphers are jointly generated by the computing parties. The protocol has two key pairs (𝑝𝑘𝑑, 𝑠𝑘𝑑) and (𝑝𝑘𝑜, 𝑠𝑘𝑜) . The first one is obtained using ℱKGD invoked by all computing parties. The second one is given by the external TTP. Henceforth, each party encrypts his share twice with 𝑝𝑘𝑑 and 𝑝𝑘𝑜 . With 𝟏 = {1}𝑖∈{ℓ}, 𝒓𝑖,𝑗$← 𝔽ℓ, and 𝑢𝑗$← 𝔽 the ciphertext 𝑏𝑖,𝑗 = ⟦𝟏 ∙𝛼𝑖,𝑗⟧𝑝𝑘𝑑= 𝖤𝗇𝖼𝑝𝑘𝑑(𝟏 ∙ 𝛼𝑖,𝑗, 𝒓𝑖,𝑗) is broadcasted for the generation of correlated randomness, andc𝑗 = 𝖤𝗇𝖼𝑝𝑘𝑜({𝜶̅𝑗, 𝛽𝑗}, 𝑢𝑗) for 𝜶̅𝑗 = {𝛼𝑖,𝑗}i∈{𝑛} is always held private until the output delivery of online phase. The relation between two ciphertexts is built by committing 𝛼𝑖,𝑗 toward the bulletin. Therefore, we need ZKP to ensure that these encryptions are all derived from the same plaintext. For 𝖤(𝒈,ℎ)(𝑛)(𝜶̅𝑗, 𝛽𝑗) = ∏ 𝖤(𝑔𝑖,ℎ)(𝛼𝑖,𝑗, 𝛽𝑗)𝑛𝑖=1and 𝜶𝑗 = {𝛼𝑖,𝑗}𝑖∈{𝑛}, and the relation is formalized as: 𝑅𝐶𝑃𝑅,𝑗(𝑛,ℓ) = {(𝐬,𝒂)|𝐬 = ({𝑏𝑖,𝑗}𝑖∈{𝑛}, 𝑐𝑗, 𝑑𝑗, 𝑝𝑘𝑑,𝑝𝑘𝑜) , 𝒂 = (𝜶𝑗, 𝛽𝑗, 𝒓𝑖,𝑗, 𝑢𝑗), 𝐂𝐨𝐫(𝑝𝑘𝑑, 𝑏𝑖,𝑗, (𝟏 ∙

Figure 10. 𝒮Online: Simulator for the protocol ΠOnline.

𝛼𝑖,𝑗), 𝑟𝑖,𝑗) = 1, 𝐂𝐨𝐫(𝑝𝑘𝑜, 𝑐𝑗,{𝜶̅𝑗, 𝛽𝑗}, 𝑢𝑗) = 1,{𝑏𝑖,𝑗}𝑖∈{𝑛}= {⟦𝟏 ∙ 𝛼𝑖,𝑗⟧𝑝𝑘𝑑}𝑖∈{𝑛}, c𝑗 =𝖤𝗇𝖼𝑝𝑘𝑜({𝜶̅𝑗, 𝛽𝑗}, 𝑢𝑗), 𝑑𝑗=𝖤(𝒈,ℎ)(𝑛)(𝜶̅𝑗, 𝛽𝑗)}.Based on [19], the ZKP protocol ΠCPRZK(𝑛,ℓ)is described in the conference version of this paper [26].

PROOFS

Figure 11. ℱOffline: Ideal functionality for the offline phase.

4.1 Security of the Online Phase

We will now prove security for the construction from Sec. 3.1 in the UC framework. which implies thatΠOnline implements ℱ Online as in Figure 9 in a hybrid model as defined in Theorem 2. Proof: The prooof the statement is provided by the simulator 𝒮Online in Figure 10, which requires at least onehonestparty to run an instance of ΠOnline. The simulator and the honest parties are controlled by 𝒜. During Initialize, Input, Add, Multiply, 𝒮Online performs the same steps as in

Figure 12. 𝒮Offline: Simulator for the protocol ΠOffline

ΠOnline and obtains MUSS ciphers α𝑖 from ℱOffline. It also sets up the Random Oracle (RO) for commitment keys and uses a fixed default input 𝑢̃𝑖 defined by 𝒞 for the simulated honest parties during Input.

Every set of at most 𝑛 − 1 MUSS encoded and plain shares of a value is uniformly random and does not reveal any information about the shared secret, so it is indistinguishable from a real transcript. During Output, the shares of one simulated honest party are adjusted to match the correct output 𝑦 from ℱOnline. By obtaining shares from ℱCom, the simulator derived the result 𝑦′ of the simulation, so it can adjust the encoded and plain shares of a simulated honest party. For each encoded share 𝑦𝑖, there exists only one 𝑟𝑖 that opens the commitment 𝐸(𝑦𝑖, 𝑟𝑖) correctly, so it is indistinguishable. The same is true for the plain shares.

If the encoded shares generated by ℱOffline follow uniform distribution, the property still holds after any linear operation and scalar multiplication. It follows from Theorem 1 of [24] that except negligible probability o(1/q) the matrix composed of opened encoded shares achieves full rank, leading to perfect secrecy as stated in Theorem 1. This ensures that no information about the output can be gained from every set of MUSS encoded shares of 𝑚 results. In the ideal world, the simulator outputs Reject in Output if any of the values opened by the dishonest parties was inconsistent, while ΠOnline does so if ΠChkPln𝑡and ΠChkEnc𝑚 may pass. This occurs with a probability of o(1/p), which is negligible in λ.

At the beginning of execution, 𝒜 decides to stop the execution or affect the outcome by corrupting dishonest parties, then 𝒮Online will forward the set of malicious parties to the ideal functionality. During the Audit and Opening stage, we also do exactly the same as in the protocol. The MUSS ciphers α𝑖 given by ℱOffline are uniformly random and thus indistinguishable from the counterparts from ℱOnline.

4.2 Security of the Offline Phase
We will now prove security for the construction from ΠOffline in Figure 7 in the UC framework,
which implies that ΠOffline implements ℱOffline described in Figure 11 and Theorem 3.

Proof: The simulator 𝒮Offline in Figure 12 will generate MUSS shares that are uniformly random, and use the decryption key to fit these shares to the commitments that ℱOffline outputs for the honest parties. Hence, the values of the dishonest parties are consistent with those values that the honest parties obtain and are indistinguishable. If 𝒜 cheats during the decryption, then the simulator will always abort by running ΠChkZKP𝜎, which guarantee the correctness and soundness,assuming the existence of an honest verifier. We do not directly decrypt the ciphertexts and check MUSS correlation, because it is impossible to differentiate the misbehavior in the proofs and that in the corresponding shares. Since there is at least one honest computing party, the opening will always be invoked if the MUSS correlation is violated. One can see that if the check fails, 𝒮 makes ℱOffline abort which is consistent with the protocol.

5. DISCUSSIONS AND CONCLUSIONS
Comparisons. We compare our proposed MPC with the other three works in [9], [12], and [13], as summarized in Table 1. Cachin and Camenisch [9] use encrypted circuits for computation where two parties exchange input tokens through verifiable oblivious transfer. Moreover, it uses a TTP to resolve misbehavior. The protocol in [12] uses Shamir’s sharing to construct a public auditable MPC in a lack of the TTP. The fairness is achievable when there exist enough honest parties to recover the secret. Seo’s work in [13] requires all party to provide verifiable encrypted shares to the TTP such that it can verify and decrypt the shares.
Result delivery: “Decrypt to open?” means if the opening procedure requires decryption, which could be done unconditionally (by “Yes, always”) or in case of detected misbehavior (by “Yes,optimistic”). “Verify first” denotes the verification of results before revealing their plaintexts tothe parties, and “Reveal first” indicates the verification after the revealing. Fairness: [9], [13], and our work are fair if there exists at least one honest party and TTP to detect the misconduct of other malicious parties. However, [12] needs at least t honest party due to threshold- t sharing and the lack of TTP.

Privacy: [12] can protect privacy against at most t − 1 malicious and colluding computing parties

Table. 1. Comparisons with previous works in various properties.

due to threshold- t sharing. [13] and our work can do with at most n − 1 malicious ones. [9] is susceptible to input corruption attack, as mentioned in [14]. Furthermore, it should be noted that in the schemes of [9] and this paper TTP has no knowledge of secret, but the TTP in [13] has the access to opening share in plaintext.

Communication: The protocol in [9] needs to check non-interactive ZKP (NIZKP) for each encrypted gate in a garbled circuit for each pair of parties. As a consequence, the number of messages is 𝑂(ℓλn2|𝒞|). Its offline number of messages is N/A because of its lack of preprocessing. The delivery procedure in [12] broadcasts NIZKP for the commitment of ach share to each party. Besides, using beaver triples needs to broadcast 𝑛 messages for each multiplication gate in online computing. The computing parties in [13] have to sends NIZKP of encrypted shares to the TPP, so the factor is only n. However, our work only requires 𝑂(n2 |𝒞|) for broadcasting shares in plaintext for result delivery and multiplication. In addition, [12], [13], and ours all use 𝑂(λn2 |𝒞|) messages to generate correlated randomness in offline preprocessing, and our work additionally sends 𝑂(ℓλ𝑛2) to broadcast NIZKP for ΠCPRZK𝜎.

Summary. We described a proposed scheme to address the issues of privacy and correctness in multi-party computation protocols. The solution introduced a semi-trusted third party as the key manager and redesigns the secret-sharing mechanism. The design ensures that the malicious parties cannot know the output by causing an abort, and the output delivery is guaranteed by excluding cheaters and restarting the protocol. The offline sub-protocols can be audited publicly by verifying zero-knowledge proofs based on KEA, holding corrupted parties accountable. The security of the protocol can be proven in the universal composability framework.

REFERENCES
[1] I. Damgård, V. Pastro, N. P. Smart, and S. Zakarias, “Multiparty Computation from Somewhat Homomorphic Encryption,” CRYPTO 2012, pp. 643-662, 2012.
[2] I. Damgard, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart, “Practical Covertly Secure MPC for Dishonest Majority – Or: Breaking the SPDZ Limits,” ESORICS 2013, pp. 1-18, 2013.
[3] C. Baum, I. Damgård, and C. Orlandi, “Publicly Auditable Secure Multi-Party Computation,” SCN 2014, pp. 175-196, 2014.
[4] G. Spini and S. Fehr, “Cheater Detection in SPDZ Multiparty Computation,” ICITS 2016, pp. 151-176, 2016.
[5] M. Keller, V. Pastro, and D. Rotaru, “Overdrive: Making SPDZ Great Again,” EUROCRYPT 2018, pp. 158-189, 2018.
[6] C. Baum, D. Cozzo, and N. P. Smart, “Using TopGear in Overdrive: A More Efficient ZKPoK for SPDZ,” SAC 2019, pp. 274-302, 2019.
[7] R. Cohen and Y. Lindell, “Fairness versus Guaranteed Output Delivery in Secure Multiparty Computation,” ASIACRYPT 2014, pp. 466-485, 2014.
[8] N. Asokan, V Shoup, and M. Waidner, “Optimistic Fair Exchange of Digital Signatures,” EUROCRYPT 1998, pp. 591-606, 1998.
[9] C. Cachin and J. Camenisch, “Optimistic Fair Secure Computation (Extended Abstract),” CRYPTO 2000, LNCS, vol. 1880, pp. 93-111, 2000.
[10]H. Kılınç and A. Küpçü, “Optimally Efficient Multi-Party Fair Exchange and Fair Secure Multi-Party Computation,” CT-RSA 2015, pp. 330-349, 2015.
[11]C. Baum, E. Orsini, and P. Scholl, “Efficient Secure Multiparty Computation with Identifiable Abort,”TCC 2016-B, pp. 461-490, 2016.
[12]M. Rivinius, P. Reisert, D. Rausch, and R. Küsters, “Publicly Accountable Robust Multi-Party Computation, ” IEEE S&P 2022, pp. 2430-2449, 2022.
[13]M. Seo, “Fair and Secure Multi-Party Computation with Cheater Detection,” Cryptography, vol. 5, no.3, pp. 19-39, 2021.
[14]A. Herzberg and H. Shulman, “Oblivious and Fair Server-Aided Two-Party Computation,” ARES 2012,pp. 75-84, 2012.
[15]M. Bellare and A. Palacio, “The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols, ” CRYPTO 2004, vol. 3152, pp. 273-289, 2004.
[16]J. Groth, “Short Pairing-Based Non-interactive Zero-Knowledge Arguments, ” ASIACRYPT 2010, col.6477, pp. 321-340, 2020.
[17]R. Cleve, “Limits on the Security of Coin Flips When Half the Processors Are Faulty (extendedabstract),” STOC, pages 364–369. ACM, 1986.
[18]D. Beaver, “Efficient Multiparty Protocols Using Circuit Randomization,” CRYPTO ’91, pp. 420-432,1991.
[19]R. Cramer and I. Damgård, “On the Amortized Complexity of Zero- Knowledge Protocols,” CRYPTO2009, pp. 177-191, 2009.
[20]R. Canetti, “Universally Composable Security: A New Paradigm for Cryptographic Protocols,” FOCS2001, pp. 136-145, 2001.
[21]MP-SPDZ 2022 [online] Available: https://github.com/data61/.
[22]M. Keller, “MP-SPDZ: A Versatile Framework for Multi-Party Computation,” CCS 2020, pp. 1575-1590, 2020.
[23]E. Orsini, “Efficient Actively Secure MPC with a Dishonest Majority: A Survey,” WAIFI 2020, pp. 42-71, 2020.
[24]C. Cooper, “On the distribution of rank of a random matrix over a finite field,” Random Structures and Algorithms, vol. 17, pp. 197-212, 2000.
[25]I. Damgård, “Non-Interactive Circuit Based Proofs and Non-Interactive Perfect Zero-Knowledge with Preprocessing, ” EUROCRYPT 1992, LNCS, vol. 658, pp. 341-355, 1992.
[26]C. Wang, ” Efficient Fair and Robust SPDZ-Like Multi-Party Computation,” CRYPIS 2023, Available: https://aircconline.com/csit/abstract/v13n13/csit131327.html.sit131327.html.

AUTHORS
Chung-Li Wang
He is a Ph. D. from University of California,
Davis and now a staff engineer with Alibaba, Inc. His research topic includessecure computation, cryptography,error-control coding, and information theory.