Effective multi-party computation protocols have been developed, but concerns regarding privacy and correctness persist. Classic results demonstrate that guaranteed output delivery can be achieved by assuming fairness and identifiable abort. However, if the majority is malicious, it is still challenging to design an efficient implementation that can deliver correct outputs while maintaining robustness and fairness. To address this issue, we have redesigned the secret-sharing mechanism and employed a semi-trusted third party (TTP) as the key manager to provide optimistic backup for output delivery. The verification and delivery procedures prevent the malicious parties from “stealing” the output, 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 decryption is needed only when misconduct is detected. Our scheme also enables identified abort for offline preprocessing, and the audit of the offline sub-protocols can be publicly performed, holding corrupted parties accountable before receiving private inputs. With fairness and identifiable abort, output delivery is guaranteed by excluding the cheaters.
Effective multi-party computation protocols have been developed, but concerns regarding privacy and correctness persist. Classic results demonstrate that guaranteed output delivery can be achieved by assuming fairness and identifiable abort. However, if the majority is malicious, it is still challenging to design an efficient implementation that can deliver correct outputs while maintaining robustness and fairness. To address this issue, we have redesigned the secret-sharing mechanism and employed a semi-trusted third party (TTP) as the key manager to provide optimistic backup for output delivery. The verification and delivery procedures prevent the malicious parties from “stealing” the output, 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 decryption is needed only when misconduct is detected. Our scheme also enables identified abort for offline preprocessing, and the audit of the offline sub-protocols can be publicly performed, holding corrupted parties accountable before receiving private inputs. With fairness and identifiable abort, output delivery is guaranteed by excluding the cheaters.
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.
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.
Dishonest majority considered in the SPDZ(the nickname of the protocol of Damgard et al. from Crypto 2012) protocols implies the impossibility of fairness(which means that corrupted parties can prevent the honest parties from learning output). The corrupted parties can learn the outputs of the honest parties and abort the protocol. Settling for the second best, there are many works focusing on the detection of the cheaters. We construct a SPDZ-like protocol which achieves fairness when at mostn/2parties behave maliciously and supports identifiable abort for dishonest majority. We suggest a sharing stage after the parties finish their computation. The parties share the returns of the computation in this stage. The correctness of the sharing is guaranteed by verifiable secret sharing and homomorphic signature. The honest parties can reconstruct the outputs of the cheaters in the setting of an honest majority. We can't prevent the corrupted parties from learning the outputs and aborting the protocol for dishonest majority. Therefore, the sharing stage does not harm to the honest parties. Instead, we provide the honest parties with the identities of all cheaters in this case.
Multi-party fair exchange (MFE) and fair secure multi-party computation (fair SMPC) are under-studied fields of research, with practical importance. In particular, we consider MFE scenarios where at the end of the protocol, either every participant receives every other participant’s item, or no participant receives anything. We analyze the case where a trusted third party (TTP) is optimistically available, although we emphasize that the trust put on the TTP is only regarding the fairness , and our protocols preserve the privacy of the exchanged items against the TTP. In the fair SMPC case, we prove that a malicious TTP can only harm fairness, but not security . We construct an asymptotically optimal multi-party fair exchange protocol that requires a constant number of rounds (in comparison to linear) and O(n 2 ) messages (in comparison to cubic), where n is the number of participating parties. In our protocol, we enable the parties to efficiently exchange any item that can be efficiently put into a verifiable encryption (e.g., signatures on a contract). We show how to apply this protocol on top of any SMPC protocol to achieve fairness with very little overhead (independent of the circuit size). We then generalize our protocol to efficiently handle any exchange topology (participants exchange items with arbitrary other participants). Our protocol guarantees fairness in its strongest sense: even if all n-1 other participants are malicious and colluding with each other, the fairness is still guaranteed.
In recent years, lattice-based secure multi-party computation (MPC) has seen a rise in popularity and is used more and more in large scale applications like privacy-preserving cloud computing, electronic voting, or auctions. Many of these applications come with the following high security requirements: a computation result should be publicly verifiable, with everyone being able to identify a malicious party and hold it accountable, and a malicious party should not be able to corrupt the computation, force a protocol restart, or block honest parties or an honest third-party (client) that provided private inputs from receiving a correct result. The protocol should guarantee verifiability and accountability even if all protocol parties are malicious. While some protocols address one or two of these often essential security features, we present the first publicly verifiable and accountable, and (up to a threshold) robust SPDZ-like MPC protocol without restart. We propose protocols for accountable and robust online, offline, and setup computations. We adapt and partly extend the lattice-based commitment scheme by Baum et al. (SCN 2018) as well as other primitives like ZKPs. For the underlying commitment scheme and the underlying BGV encryption scheme we determine ideal parameters. We give a performance evaluation of our protocols and compare them to state-of-the-art protocols both with and without our target security features: public accountability, public verifiability and robustness.
In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these proper-ties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial func-tions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.