Secure multiparty computation allows mutually distrusting parties to compute a function on their private inputs such that nothing but the function output is revealed. Achieving fairness --- that all parties learn the output or no one does -- is a long studied problem with known impossibility results in the standard model if a majority of parties are dishonest. We present a new model for achieving fairness in MPC against dishonest majority by using public bulletin boards implemented via existing infrastructure such as blockchains or Google's certificate transparency logs. We present both theoretical and practical constructions using either witness encryption or trusted hardware (such as Intel SGX). Unlike previous works that either penalize an aborting party or achieve weaker notions such as
Δ-fairness, we achieve complete fairness using existing infrastructure.
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 most
n/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.
In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their private inputs. The computation should be carried out in a secure way, meaning that the properties privacy, correctness, independence of inputs, fairness and guaranteed output delivery should all be preserved. Unfortunately, in the case of no honest majority – and specifically in the important two-party case – it is impossible to achieve fairness and guaranteed output delivery. In this paper, we show how a legal infrastructure that respects digital signatures can be used to enforce fairness in two-party computation. Our protocol has the property that if one party obtains output while the other does not (meaning that fairness is breached), then the party not obtaining output has a digitally signed cheque from the other party. Thus, fairness can be “enforced ” in the sense that any breach results in a loss of money by the adversarial party. 1
Secure two-party computation allows two mutually distrusting parties to compute a joint function over their inputs, guaranteeing properties such as \emph{input privacy} or \emph{correctness}. For many tasks, such as joint computation of statistics, it is important that when one party receives the result of the computation, the other party also receives the result. Unfortunately, this property, which is called \emph{fairness}, is unattainable in the two-party setting for arbitrary functions. So weaker variants have been proposed. One such notion, proposed by Pass \etal (EUROCRYPT 2017) is called \emph{
Δ-fairness}. Informally, it guarantees that if a corrupt party receives the output in round
r and stops participating in the protocol, then the honest party receives the output by round
Δ(r). This notion is achieved by using so-called \emph{secure enclaves}. In many settings,
Δ-fairness is not sufficient, because a corrupt party is \emph{guaranteed} to receive its output before the honest party, giving the corrupt party an advantage in further interaction. Worse, as
Δ is known to the corrupt party, it can abort the protocol when it is most advantageous. We extend the concept of
Δ-fairness by introducing a new fairness notion, which we call \emph{hidden
Δ-fairness}, which addresses these problems. First of all, under our new notion, a corrupt party may not benefit from aborting, because it may not, with probability $\nicefrac{1}{2}$, learn the result first. Moreover,
Δ and other parameters are sampled according to a given distribution and remain unknown to the participants in the computation. We propose a 2PC protocol that achieves hidden
Δ-fairness, also using secure enclaves, and prove its security in the Generalized Universal Composability (GUC) framework.
Secure multiparty computation (MPC) enables privacy-preserving collaborative computation over sensitive data held by multiple mutually distrusting parties. Unfortunately, in the most natural setting where a majority of the parties are maliciously corrupt (also called the dishonest majority setting), traditional MPC protocols incur high overheads and offer weaker security guarantees than are desirable for practical applications. In this paper, we explore the possibility of circumventing these drawbacks and achieving practically efficient dishonest majority MPC protocols with strong security guarantees by assuming an additional semi-honest, non-colluding helper party HP .1We believe that this is a more realistic alternative to assuming an honest majority, since many real-world applications of MPC involving potentially large numbers of parties (such as dark pools) are typically enabled by a central governing entity that can be modeled as the HP.In the above model, we are the first to design, implement and benchmark a practically-efficient and general multi-party framework, Asterisk. Our framework requires invoking HP only a constant number of times, achieves the strong security guarantee of fairness (either all parties learn the output or none do), scales to hundreds of parties, outperforms all existing dishonest majority MPC protocols, and is, in fact, competitive with state-of-the-art honest majority MPC protocols. Our experiments show that Asterisk achieves 228 – 288× speedup in preprocessing as compared to the best dishonest majority MPC protocol. With respect to online time, Asterisk supports 100-party evaluation of a circuit with 106multiplication gates in approximately 20 seconds. We also implement and benchmark practically efficient and highly scalable dark pool instances using Asterisk. The corresponding run times showcase the effectiveness of Asterisk in enabling efficient realizations of real-world privacy-preserving applications with strong security guarantees.
Secure computation is a fundamental problem in modern cryptography in which multiple parties join to compute a function of their private inputs without revealing anything beyond the output of the function. A series of very strong results in the 1980’s demonstrated that any polynomial-time function can be computed while guaranteeing essentially every desired security property. The only exception is the fairness property, which states that no player should receive their output from the computation unless all players receive their output. While it was shown that fairness can be achieved whenever a majority of players are honest, it was also shown that fairness is impossible to achieve in general when half or more of the players are dishonest. Indeed, it was proven that even boolean XOR cannot be computed fairly by two parties.
The fairness property is both natural and important, and as such it was one of the first questions addressed in modern cryptography (in the context of signature exchange). One contribution of this thesis is to survey the many approaches that have been used to guarantee different notions of partial fairness. We then revisit the topic of fairness within a modern security framework for secure computation. We demonstrate that, despite the strong impossibility result mentioned above, certain interesting functions can be computed fairly, even when half (or more) of the parties are malicious. We also provide a new notion of partial fairness, demonstrate feasibility of achieving this notion for a large class of functions, and show impossibility for certain functions outside this class. We consider fairness in the presence of rational adversaries, and, finally, we study the difficulty of achieving fairness by exploring how much external help is necessary for providing fair secure computation.