With the development of modern internet and mobile networks, there is an increasing need for privacy-preserving cooperative computation and cloud computing. Secure multi-party computation (SMPC) gives a general solution to these applications and has become a hot topic in privacy-carrying protocols. The commit-prove-fair-open protocol is one of multi-party fair exchange protocols against the malicious adversary in breaking the fair play of the participants, and it provides an important tool of SMPC to make it possible to achieve the fairness with corrupted majority according to the standard real/ideal world simulation paradigm framework. In this paper, we at first prove two lemmas about the simplified Camenisch-Shoup commitment and the time-lines, and then propose a very efficient resource-fair commit-prove-fair-open protocol. Compared with the other commit-prove-fair-open protocols, our new protocol enjoys two important advantages: 1) communications cost and computations price are less than 20%; 2) it allows commitment to obtain value 0, which is not implemented in the other constructions.
With the development of modern internet and mobile networks, there is an increasing need for privacy-preserving cooperative computation and cloud computing. Secure multi-party computation (SMPC) gives a general solution to these applications and has become a hot topic in privacy-carrying protocols. The commit-prove-fair-open protocol is one of multi-party fair exchange protocols against the malicious adversary in breaking the fair play of the participants, and it provides an important tool of SMPC to make it possible to achieve the fairness with corrupted majority according to the standard real/ideal world simulation paradigm framework. In this paper, we at first prove two lemmas about the simplified Camenisch-Shoup commitment and the time-lines, and then propose a very efficient resource-fair commit-prove-fair-open protocol. Compared with the other commit-prove-fair-open protocols, our new protocol enjoys two important advantages: 1) communications cost and computations price are less than 20%; 2) it allows commitment to obtain value 0, which is not implemented in the other constructions.
Commit-Prove-Fair-Open functionality Ou Ruan , Cai Fu a,* , Guohua Cui a a College of Compute Science & Technology, Huazhong University of Science & Technology, Wuhan, China, 430074 b College of Compute Science & Technology, Hubei University of Technology, Wuhan, China, 430068 ruanou@21cn.com, 12695133@qq.com,cgh3986@126.com *:Corresponding author: Cai Fu , 12695133@qq.com, stand_fucai@126.com Research supported in part by the National Natural Science Funds of China(60903175) Abstract. In TCC 2006, Garay et al. introduced the notion of commit-prove-fair-open functionality in order to achieve what they called resource of secure multi-party computation(MPC) with corrupted majority. The protocol realizing this notion of fairness follows the gradual release approach and, further, it can be proven secure in the simulation paradigm and enjoys composition properties. In this paper, we show a more efficient resource-fair protocol of FCPFO based on a new variant of Garay et al. time-lines and simplified Camenisch-Shoup(sCS) commitment,whose communication and computation complexity are less than 1/5 of Garay et al. construction. In addition, our new protocol allows commitment to value 0, which is not possible in the plain Garay et al. construction.
We consider the problem of constructing secure multi-party computation (MPC) protocols that are 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 fair multi-party computation (FMPC), 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 depend on 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 up to (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 of the existing secure MPC protocols can be easily transformed into fair protocols while preserving their security. Furthermore, these protocols remain secure when arbitrarily composed with any protocols, which means, in particular, that they are concurrently composable and non-malleable. This is joint work with Phil MacKenzie and Ke Yang.
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.
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.
With the development of modern Internet and ad hoc networks, there is an increasing need for autonomous entities cooperating together to perform knowledge-and information-based decision making. Data in its original form, however, typically contains sensitive information about individuals and unmanaged data exchange may violate individual privacy. Secure multi-party computation is proposed to solve this problem and has become a hot topic. Yao's garbled circuit approach is a major method in designing protocols for secure two-party computation. However, only few papers dealt with the fundamental property of fairness for Yao's garbled circuit protocol, in which one introduced a third party and others were based on cut-and-choose techniques that are inherently expensive. In this paper, we propose an efficient fair UC-secure Yao's garbled circuit protocol in the malicious model based on Jarecki et al.'s construction and Ou Ruan et al.'s gradual release commitment. The protocol avoids involving any third party or using cut-and-choose techniques, and it is more bandwidth-efficient than other Yao-based protocols. Furthermore, its security could be proved within the UC framework.
Abstract. We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. In this model we specify the ideally fair functionality as allowing parties to “invest resources ” in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a “wrapper.”) Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. Turning to constructions, we define a “commit-prove-fair-open ” functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as “timelines.” With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security. 1