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

Resource Fairness and Composability of Cryptographic Protocols.

Juan A. Garay, Philip MacKenzie, Manoj Prabhakaran, Ke Yang

Published Jan 1, 2005• 16 citations
OpenAlex

Abstract

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

Related papers

Fair Multi-Party Computation

Juan A. Garay

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.

•Jan 1, 2004•2 citations

On the Limitations of Universally Composable Two-Party Computation Without Set-up Assumptions.

Ran Canetti, Eyal Kushilevitz, Yehuda Lindell

Abstract. The recently proposed universally composable (UC) security framework, for analyzing security of cryptographic protocols, provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when deployed in arbitrary multi-party, multi-protocol, multi-execution environments. Protocols for securely carrying out essentially any cryptographic task in a universally composable way exist, both in the case of an honest majority (in the plain model, i.e., without set-up assumptions) and in the case of no honest majority (in the common reference string model). However, in the plain model, little was known for the case of no honest majority and, in particular, for the important special case of two-party protocols. We study the feasibility of universally composable two-party function evaluation in the plain model. Our results show that very few functions can be computed in this model so as to provide the UC security guarantees. Specifically, for the case of deterministic functions, we provide a full characterization of the functions computable in this model. (Essentially, these are the functions that depend on at most one of the parties’ inputs, and furthermore are “efficiently invertible ” in a sense defined within.) For the case of probabilistic functions, we show that the only functions computable in this model are those where one of the parties can essentially uniquely determine the joint output. 1

•Jan 1, 2004•0 citations

Universally composable security: a new paradigm for cryptographic protocols

Ran Canetti

We propose a novel paradigm for defining security of cryptographic protocols, called universally composable security. The salient property of universally composable definitions of security is that they guarantee security even when a secure protocol is composed of an arbitrary set of protocols, or more generally when the protocol is used as a component of an arbitrary system. This is an essential property for maintaining security of cryptographic protocols in complex and unpredictable environments such as the Internet. In particular, universally composable definitions guarantee security even when an unbounded number of protocol instances are executed concurrently in an adversarially controlled manner, they guarantee non-malleability with respect to arbitrary protocols, and more. We show how to formulate universally composable definitions of security for practically any cryptographic task. Furthermore, we demonstrate that practically any such definition can be realized using known techniques, as long as only a minority of the participants are corrupted. We then proceed to formulate universally composable definitions of a wide array of cryptographic tasks, including authenticated and secure communication, key-exchange, public-key encryption, signature, commitment, oblivious transfer, zero knowledge and more. We also make initial steps towards studying the realizability of the proposed definitions in various settings.

Annual Symposium on Foundations of Computer Science•Jan 1, 2001•3,416 citations

How Fair is Your Protocol? A Utility-based Approach to Protocol Optimality

Juan A. Garay, Jonathan I. Katz, Björn Tackmann +1 more

Security of distributed cryptographic protocols usually requires privacy (inputs of the honest parties remain hidden), correctness (the adversary cannot improperly affect the outcome), and fairness (if the adversary learns the output, all honest parties do also). Cleve's seminal result (STOC '86) implies that satisfying these properties simultaneously is impossible in the presence of dishonest majorities, and led to several proposals for relaxed notions of fairness. While these works also suggest completeness results (i.e., the ability to design protocols which achieve their fairness notion), their assessment is typically of an all-or-nothing nature. In this work we put forth a new approach for defining relaxed fairness guarantees that allows for a quantitative comparison between protocols with regard to the level of fairness they achieve. The basic idea is to use an appropriate utility function to express the preferences of an adversary who wants to violate fairness. We also show optimal protocols with respect to our notion, in both the two-party and multi-party settings.

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 17, 2015•23 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

Hidden Δ\DeltaΔ-fairness: A Novel Notion for Fair Secure Two-Party Computation

Saskia Bayreuther, Robin Berger, Felix Dörre +2 more

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{$\Delta$-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 $\Delta(r)$. This notion is achieved by using so-called \emph{secure enclaves}. In many settings, $\Delta$-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 $\Delta$ is known to the corrupt party, it can abort the protocol when it is most advantageous. We extend the concept of $\Delta$-fairness by introducing a new fairness notion, which we call \emph{hidden $\Delta$-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, $\Delta$ 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 $\Delta$-fairness, also using secure enclaves, and prove its security in the Generalized Universal Composability (GUC) framework.

•Jan 1, 2024•0 citations
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
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.
Abstract. The recently proposed universally composable (UC) security framework, for analyzing security of cryptographic protocols, provides very strong security guarantees. In particular, a protocol proven secure in this framework is guaranteed to maintain its security even when deployed in arbitrary multi-party, multi-protocol, multi-execution environments. Protocols for securely carrying out essentially any cryptographic task in a universally composable way exist, both in the case of an honest majority (in the plain model, i.e., without set-up assumptions) and in the case of no honest majority (in the common reference string model). However, in the plain model, little was known for the case of no honest majority and, in particular, for the important special case of two-party protocols. We study the feasibility of universally composable two-party function evaluation in the plain model. Our results show that very few functions can be computed in this model so as to provide the UC security guarantees. Specifically, for the case of deterministic functions, we provide a full characterization of the functions computable in this model. (Essentially, these are the functions that depend on at most one of the parties’ inputs, and furthermore are “efficiently invertible ” in a sense defined within.) For the case of probabilistic functions, we show that the only functions computable in this model are those where one of the parties can essentially uniquely determine the joint output. 1
We propose a novel paradigm for defining security of cryptographic protocols, called universally composable security. The salient property of universally composable definitions of security is that they guarantee security even when a secure protocol is composed of an arbitrary set of protocols, or more generally when the protocol is used as a component of an arbitrary system. This is an essential property for maintaining security of cryptographic protocols in complex and unpredictable environments such as the Internet. In particular, universally composable definitions guarantee security even when an unbounded number of protocol instances are executed concurrently in an adversarially controlled manner, they guarantee non-malleability with respect to arbitrary protocols, and more. We show how to formulate universally composable definitions of security for practically any cryptographic task. Furthermore, we demonstrate that practically any such definition can be realized using known techniques, as long as only a minority of the participants are corrupted. We then proceed to formulate universally composable definitions of a wide array of cryptographic tasks, including authenticated and secure communication, key-exchange, public-key encryption, signature, commitment, oblivious transfer, zero knowledge and more. We also make initial steps towards studying the realizability of the proposed definitions in various settings.
Security of distributed cryptographic protocols usually requires privacy (inputs of the honest parties remain hidden), correctness (the adversary cannot improperly affect the outcome), and fairness (if the adversary learns the output, all honest parties do also). Cleve's seminal result (STOC '86) implies that satisfying these properties simultaneously is impossible in the presence of dishonest majorities, and led to several proposals for relaxed notions of fairness. While these works also suggest completeness results (i.e., the ability to design protocols which achieve their fairness notion), their assessment is typically of an all-or-nothing nature. In this work we put forth a new approach for defining relaxed fairness guarantees that allows for a quantitative comparison between protocols with regard to the level of fairness they achieve. The basic idea is to use an appropriate utility function to express the preferences of an adversary who wants to violate fairness. We also show optimal protocols with respect to our notion, in both the two-party and multi-party settings.
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 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{Δ\DeltaΔ-fairness}. Informally, it guarantees that if a corrupt party receives the output in round rrr and stops participating in the protocol, then the honest party receives the output by round Δ(r)\Delta(r)Δ(r). This notion is achieved by using so-called \emph{secure enclaves}. In many settings, Δ\DeltaΔ-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 Δ\DeltaΔ is known to the corrupt party, it can abort the protocol when it is most advantageous. We extend the concept of Δ\DeltaΔ-fairness by introducing a new fairness notion, which we call \emph{hidden Δ\DeltaΔ-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, Δ\DeltaΔ 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 Δ\DeltaΔ-fairness, also using secure enclaves, and prove its security in the Generalized Universal Composability (GUC) framework.