In multi-party computation field, one important branch is to construct an efficient and secure multi- party computation for some special problems. In this paper, we make use of secret sharing scheme to construct an efficient and secure multi-party computation for sequencing problem. Our protocols are perfectly secure against passive adversary if it can corrupt at most t ≤ (n-1)/2 participants, and is perfectly secure against active adversary if it can corrupt at most t < n/3 participants. The simplest sequencing problem is millionaire problem.
In multi-party computation field, one important branch is to construct an efficient and secure multi- party computation for some special problems. In this paper, we make use of secret sharing scheme to construct an efficient and secure multi-party computation for sequencing problem. Our protocols are perfectly secure against passive adversary if it can corrupt at most t ≤ (n-1)/2 participants, and is perfectly secure against active adversary if it can corrupt at most t < n/3 participants. The simplest sequencing problem is millionaire problem.
The problem of secure multi-party computation(SMPC) is one of the most fundamental problems in information security. First, we introduce the basic concept of SMPC and four SMPC basic agreement: key distribution,oblivious transfer, bit commitment and zero knowledge proof. Secondly, we separately illustrate commitment schemes commitment transfer protocol, commitment sharing protocol and commitment multiplication protocol. Finally, we present unconditionally secure multi-party computation with a passive adversary, an active adversary, general adversary structures.
Abstract. As an extension of multi-party computation (MPC), we propose the concept of secure parallel multi-party computation which is to securely compute multi-functions against an adversary with multistructures. Precisely, there are m functions f1,..., fm and m adversary structures A1,..., Am, where fi is required to be securely computed against an Ai-adversary. We give a general construction to build a parallel multi-party computation protocol from any linear multi-secret sharing scheme (LMSSS), provided that the access structures of the LMSSS allow MPC at all. When computing complicated functions, our protocol has more advantage in communication complexity than the “direct sum” method which actually executes a MPC protocol for each function. The paper also provides an efficient and generic construction to obtain from any LMSSS a multiplicative LMSSS for the same multi-access structure. 1
Abstract We study the problem of constructing secure multi-party computation (MPC) protocols thatare completely fair-- meaning that either all the parties learn the output of the function, or nobody does-- even when a majority of the parties are corrupted. We first propose a framework for fairmulti-party computation, within which we formulate a definition of secure and fair protocols. The definition follows the standard simulation paradigm, but is modified to allow the protocol to dependon the runing time of the adversary. In this way, we avoid a well-known impossibility result for fair MPC with corrupted majority; in particular, our definition admits constructions that tolerate upto ( n- 1) corruptions, where n is the total number of parties. Next, we define a "commit-prove-fair-open " functionality and construct an efficient protocol that realizes it, using a new variant of a cryptographic primitive known as "time-lines. " With this functionality, we show that some ofthe existing secure MPC protocols can be easily transformed into fair protocols while preserving their security. Putting these results together, we construct efficient, secure MPC protocols that arecompletely fair even in the presence of corrupted majorities. Furthermore, these protocols remain secure when arbitrarily composed with any protocols, which means, in particular, that they areconcurrently-composable and non-malleable. Finally, as an example of our results, we show a very efficient protocol that fairly and securely solves the socialist millionaires ' problem.
Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.
In this paper, we study a secure multi-party ranking problem: there are n parties, P1, P2, ... , Pn. Each party Pihas a secret input miisin {1, 2, ... ,N}. He wants to get the order of miin the ascending ranking sequence of the n parties' inputs, while not leaking the value of mi. This problem extends the famous Yao's millionaires' problem form two parties to n parties and is a multi-party Yao's Millionaires' problem. We propose a protocol for solving the secure multi-party ranking problem, using the encoding scheme and the El Gamal cryptosystem. We also prove the correctness and the security of our solution in the semi-honest model. The solution of secure multi-party ranking problem can make new-style electronic transactions, such as private bidding and auction, secret online transaction and so on, become better security.