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

ACM Symposium on Principles of Distributed Computing (PODC)

Distributing the setup in universally composable multi-party computation

Jonathan I. Katz, Aggelos Kiayias, Hong-Sheng Zhou, Vassilis Zikas

Published Jul 15, 2014• 4 citations
Publisher

Abstract

Universally composable (UC) protocols retain their security properties even when run concurrently alongside arbitrary other protocols. Unfortunately, it is known that UC multiparty computation (for general functionalities, and without assuming honest majority) is impossible without some form of setup. To circumvent this impossibility, various complete setup assumptions have been proposed. With only a few exceptions, past work has viewed these setup assumptions as being implemented by some ideal, incorruptible entity. Any such entity is thus a single point of failure, and security fails catastrophically in case the setup entity is subverted by an adversary. We propose here a clean, general, and generic approach for distributing trust among m arbitrary setups, by modeling potential corruption of setups within the UC framework, where such corruption might be fail-stop, passive, or arbitrary and is in addition to possible corruption of the parties themselves. We show several feasibility and impossibility results in this model, for different specifications of the corruptible sets. For example, we show that given m complete setups, up to t of which might be actively corrupted in an adaptive manner, general multiparty computation with no honest majority is possible if and only if t < m/2.

DOI
10.1145/2611462.2611480

Related papers

Universally Composable Protocols with Relaxed Set-Up Assumptions

Boaz Barak, Ran Canetti, Jesper Buus Nielsen +1 more

A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•219 citations

Universally Composable Multiparty Computation with Partially Isolated Parties.

Ivan Damgård, Jesper Buus Nielsen, Daniel Wichs

Abstract. It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a trusted third party generate some global setup such as a common reference string (CRS) or a public key infrastructure (PKI). The recent work of Katz shows that we may instead rely on physical assumptions, and in particular tamper-proof hardware tokens. In this paper, we consider a similar but strictly weaker physical assumption. We assume that a player (Alice) can partially isolate another player (Bob) for a brief portion of the computation and prevent Bob from communicating more than some limited number of bits with the environment. For example, isolation might be achieved by asking Bob to put his functionality on a tamper-proof hardware token and assuming that Alice can prevent this token from communicating to the outside world. Alternatively, Alice may interact with Bob directly but in a special office which she administers and where there are no high-bandwidth communication channels to the outside world. We show that, under standard cryptographic assumptions, such physical setup can be used to UC-realize any two party and multiparty computation in the presence of an active and adaptive adversary corrupting any number of players. We also consider an alternative scenario, in which there are some trusted third parties but

•Jan 1, 2007•4 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 Multi-Party Computation with an Unreliable Common Reference String.

Vipul Goyal, Jonathan I. Katz

Abstract. Universally composable (UC) multi-party computation has been studied in two settings. When a majority of parties are honest, UC multi-party computation is possible without any assumptions. Without a majority of honest parties, UC multi-party computation is impossible in the plain model, but feasibility results have been obtained in various augmented models. The most popular such model posits a common reference string (CRS) available to parties executing the protocol. In either of the above settings, some assumption regarding the protocol execution is made: i.e., that many parties are honest in the first case, or that a legitimately-chosen string is available in the second. If this assumption is incorrect then all security is lost. A natural question is whether it is possible to design protocols secure if either one of these assumptions holds, i.e., a protocol which is secure if either at most s players are dishonest or if up to t> s players are dishonest but the CRS is chosen in the prescribed manner. We show that such protocols exist if and only if s + t < n. 1

•Jan 1, 2007•0 citations

New notions of security: achieving universal composability without trusted setup

Manoj Prabhakaran, Amit Sahai

We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion involves comparing the real protocol execution with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.

ACM Symposium on Theory of Computing (STOC)•Jun 13, 2004•147 citations

New Notions of Security: Achieving Universal Composability without Trusted Setup.

Manoj Prabhakaran, Amit Sahai

We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion, involves comparing the protocol executions with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework. 1

•Jan 1, 2004•8 citations
Universally composable (UC) protocols retain their security properties even when run concurrently alongside arbitrary other protocols. Unfortunately, it is known that UC multiparty computation (for general functionalities, and without assuming honest majority) is impossible without some form of setup. To circumvent this impossibility, various complete setup assumptions have been proposed. With only a few exceptions, past work has viewed these setup assumptions as being implemented by some ideal, incorruptible entity. Any such entity is thus a single point of failure, and security fails catastrophically in case the setup entity is subverted by an adversary. We propose here a clean, general, and generic approach for distributing trust among m arbitrary setups, by modeling potential corruption of setups within the UC framework, where such corruption might be fail-stop, passive, or arbitrary and is in addition to possible corruption of the parties themselves. We show several feasibility and impossibility results in this model, for different specifications of the corruptible sets. For example, we show that given m complete setups, up to t of which might be actively corrupted in an adaptive manner, general multiparty computation with no honest majority is possible if and only if t < m/2.
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.
Abstract. It is well known that universally composable multiparty computation cannot, in general, be achieved in the standard model without setup assumptions when the adversary can corrupt an arbitrary number of players. One way to get around this problem is by having a trusted third party generate some global setup such as a common reference string (CRS) or a public key infrastructure (PKI). The recent work of Katz shows that we may instead rely on physical assumptions, and in particular tamper-proof hardware tokens. In this paper, we consider a similar but strictly weaker physical assumption. We assume that a player (Alice) can partially isolate another player (Bob) for a brief portion of the computation and prevent Bob from communicating more than some limited number of bits with the environment. For example, isolation might be achieved by asking Bob to put his functionality on a tamper-proof hardware token and assuming that Alice can prevent this token from communicating to the outside world. Alternatively, Alice may interact with Bob directly but in a special office which she administers and where there are no high-bandwidth communication channels to the outside world. We show that, under standard cryptographic assumptions, such physical setup can be used to UC-realize any two party and multiparty computation in the presence of an active and adaptive adversary corrupting any number of players. We also consider an alternative scenario, in which there are some trusted third parties but
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
Abstract. Universally composable (UC) multi-party computation has been studied in two settings. When a majority of parties are honest, UC multi-party computation is possible without any assumptions. Without a majority of honest parties, UC multi-party computation is impossible in the plain model, but feasibility results have been obtained in various augmented models. The most popular such model posits a common reference string (CRS) available to parties executing the protocol. In either of the above settings, some assumption regarding the protocol execution is made: i.e., that many parties are honest in the first case, or that a legitimately-chosen string is available in the second. If this assumption is incorrect then all security is lost. A natural question is whether it is possible to design protocols secure if either one of these assumptions holds, i.e., a protocol which is secure if either at most s players are dishonest or if up to t> s players are dishonest but the CRS is chosen in the prescribed manner. We show that such protocols exist if and only if s + t < n. 1
We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion involves comparing the real protocol execution with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework.
We propose a modification to the framework of Universally Composable (UC) security [3]. Our new notion, involves comparing the protocol executions with an ideal execution involving ideal functionalities (just as in UC-security), but allowing the environment and adversary access to some super-polynomial computational power. We argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. We generalize the Universal Composition theorem of [3] to the new setting. Then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. This is known to be impossible under the UC framework. 1