Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Optimally-Fair Multi-party Exchange Without Trusted Parties

Ivo Maffei, Andrew William Roscoe

Published Jan 1, 2024• 1 citation
Publisher

Abstract

Abstract We present a multi-party exchange protocol that achieves optimal partial fairness even in the presence of a dishonest majority. We demonstrate how this protocol can be applied to any type of multi-party exchange scenario where the network topology is complete. When combined with standard secure multi-party computation techniques, our protocol enables SMPC with partial fairness when a dishonest majority is involved. Fairness optimality is proven in an abstract model which applies to all protocols based on the concept of concealing the point when the secrets are exchanged. Our protocol improves known results via the use of timed-release encryption and commutative blinding.

DOI
10.1007/978-3-031-50594-2_16

Related papers

Optimally Efficient Multi-party Fair Exchange and Fair Secure Multi-party Computation

Handan Kılınç Alper, Alptekın Küpçü

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.

ACM Transactions on Privacy and Security•Nov 23, 2021•13 citations

Optimally-Fair Exchange of Secrets via Delay Encryption and Commutative Blinding

Ivo Maffei, Andrew William Roscoe

Abstract We propose a new fair exchange protocol that takes advantage of delay encryption and commutative encryption to achieve optimal partial fairness among all protocols involving one-way messages. Our protocol consists of 3 setup messages and $$2N+1$$ 2 N + 1 exchange messages and it is fair against covert adversaries with probability $$1- \frac{1}{2N}$$ 1 - 1 2 N . We prove that this is optimal up to shortening the setup phase which is notably more efficient than existing protocols.

Lecture notes in computer science•Nov 30, 2023•3 citations

Efficient and Secure Multi-Party Computation with Faulty Majority and Complete Fairness.

Juan A. Garay, PHILIP D. MACKENZIE, Ke Yang

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.

•Jan 1, 2004•16 citations

An Entropy-View Secure Multiparty Computation Protocol Based on Semi-Honest Model

Yun Luo, Yuling Chen, Tao Li +3 more

Data interaction scenarios involving multiple parties in network communities have problems of trust, data security, and reliability of the parties, and secure multiparty computation(SMPC) can effectively solve these problems. To address the security and fairness issues of SMPC, this study considers that semi-honest participants can lead to deviations in the security and fairness of the protocol, and combines information entropy and mutual information to present an n-round information exchange protocol in which each participant broadcasts a relevant information value in each round without revealing other information. The uncertainty of the correct outcome value is blurred by the interaction information in each round, and each participant is not sure of the correct outcome value until the end of the protocol, which effectively prevents malicious behavior and ensures the correct execution of the protocol. Security and fairness analysis shows that our protocol guarantees the security and relative fairness of the output obtained by the participants after completing the protocol.

Journal of Organizational and End User Computing•Jul 14, 2022•10 citations

Multi-party fair exchange with an off-line trusted neutral party

Feng Bao, Robert Huijie Deng, Khanh Quoc Nguyen +1 more

Recently developed cryptographic techniques make it possible to construct fair exchange protocols with an off-line trusted third party (TTP). The technique is referred to as a verifiable encryption scheme (VES) and proves that a ciphertext is the result of the encryption of a specified value without revealing this value. In this paper we apply the technique to multi-party fair exchange (MPFE) protocols which leads to the trusted neutral party (TNP, it is not the third party in multi-party protocols) involved in the protocol to be off-line. Multi-party fair exchange has been studied by Asokan et al. (1996) and Franklin and Tsudik (1998) where the TNP is on-line. For off-line TNP-based MPFE, the issues are different from that of on-line TNP MPFE. We give a definition of fairness of the MPFE with off-line TNP. We then present our MPFE protocol and prove its fairness.

International Workshop on Database and Expert Systems Applications (DEXA)•Jan 1, 1999•35 citations

A multiparty fair-exchange protocol

Zhengquan Li

Based on the secret sharing technique,this paper proposes a multi-party fair exchange protocol.The protocol uses an online trusted third party(TTP) in order to help the participants to realize fair exchange.The advantage of a protocol implemented with an online TTP is that the TTP is semi-trusted.Fairness of the proposed protocol is proved in this paper.

Journal of Yangzhou University•Jan 1, 2008•0 citations
Abstract We present a multi-party exchange protocol that achieves optimal partial fairness even in the presence of a dishonest majority. We demonstrate how this protocol can be applied to any type of multi-party exchange scenario where the network topology is complete. When combined with standard secure multi-party computation techniques, our protocol enables SMPC with partial fairness when a dishonest majority is involved. Fairness optimality is proven in an abstract model which applies to all protocols based on the concept of concealing the point when the secrets are exchanged. Our protocol improves known results via the use of timed-release encryption and commutative blinding.
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 propose a new fair exchange protocol that takes advantage of delay encryption and commutative encryption to achieve optimal partial fairness among all protocols involving one-way messages. Our protocol consists of 3 setup messages and 2N+12N+12N+1 2 N + 1 exchange messages and it is fair against covert adversaries with probability 1−12N1- \frac{1}{2N}1−2N1​ 1 - 1 2 N . We prove that this is optimal up to shortening the setup phase which is notably more efficient than existing protocols.
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.
Data interaction scenarios involving multiple parties in network communities have problems of trust, data security, and reliability of the parties, and secure multiparty computation(SMPC) can effectively solve these problems. To address the security and fairness issues of SMPC, this study considers that semi-honest participants can lead to deviations in the security and fairness of the protocol, and combines information entropy and mutual information to present an n-round information exchange protocol in which each participant broadcasts a relevant information value in each round without revealing other information. The uncertainty of the correct outcome value is blurred by the interaction information in each round, and each participant is not sure of the correct outcome value until the end of the protocol, which effectively prevents malicious behavior and ensures the correct execution of the protocol. Security and fairness analysis shows that our protocol guarantees the security and relative fairness of the output obtained by the participants after completing the protocol.
Recently developed cryptographic techniques make it possible to construct fair exchange protocols with an off-line trusted third party (TTP). The technique is referred to as a verifiable encryption scheme (VES) and proves that a ciphertext is the result of the encryption of a specified value without revealing this value. In this paper we apply the technique to multi-party fair exchange (MPFE) protocols which leads to the trusted neutral party (TNP, it is not the third party in multi-party protocols) involved in the protocol to be off-line. Multi-party fair exchange has been studied by Asokan et al. (1996) and Franklin and Tsudik (1998) where the TNP is on-line. For off-line TNP-based MPFE, the issues are different from that of on-line TNP MPFE. We give a definition of fairness of the MPFE with off-line TNP. We then present our MPFE protocol and prove its fairness.