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

Universally Composable Multi-Party Computation with an Unreliable Common Reference String.

Vipul Goyal, Jonathan I. Katz

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

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

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

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

Obtaining Universally Composable Security: Towards the Bare Bones of Trust.

Ran Canetti

A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security in the standard, “plain” model of computation. Impossibility holds even if ideally authenticated communication channels are provided. In contrast, it has been demonstrated that general secure computation can be obtained in a number of idealized models. Each one of these models represents a form of trust that is put in some of the system’s components. This survey examines and compares some of these trust models, both from the point of view of their sufficiency for building UC secure protocols, and from the point of view of their practical realizability. We start with the common reference string (CRS) model, and then describe several relaxations and alternatives including the Defective CRS model, the key registration models, the hardware token model, the global and augmented CRS models, and a timing assumption. Finally, we briefly touch upon trust models for obtaining authenticated communication.

•Jan 1, 2007•5 citations

Distributing the setup in universally composable multi-party computation

Jonathan I. Katz, Aggelos Kiayias, Hong-Sheng Zhou +1 more

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.

ACM Symposium on Principles of Distributed Computing (PODC)•Jul 15, 2014•4 citations

Universally Composable Commitments.

Ran Canetti, Marc Fischlin

Abstract. We propose a new security measure for commitment pro-tocols, called Universally Composable (UC) Commitment. The measure guarantees that commitment protocols behave like an \\ideal commitment service, " even when concurrently composed with an arbitrary set of pro-tocols. This is a strong guarantee: it implies that security is maintained even when an unbounded number of copies of the scheme are running concurrently, it implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols), it provides resilience to selective decommitment, and more. Unfortunately, two-party uc commitment protocols do not exist in the plain model. However, we construct two-party uc commitment proto-cols, based on general complexity assumptions, in the common reference string model where all parties have access to a common string taken from a predetermined distribution. The protocols are non-interactive, in the sense that both the commitment and the opening phases consist of a single message from the committer to the receiver.

•Jan 1, 2001•2 citations

Cryptography from Sunspots: How to Use an Imperfect Reference String

Ran Canetti, Rafael Pass, Abhi A. Shelat

The common reference string (CRS) model equips all protocol participants with a common string that is sampled from a pre-specified distribution, say the uniform distribution. This model enables otherwise-impossible cryptographic goals such as removing interaction from protocols and guaranteeing composable security. However, knowing the precise distribution of the reference string seems crucial for all known protocols in this model, in the sense that current security analyses fail when the actual distribution of the reference string is allowed to differ from the specified one even by a small amount. This fact rules out many potential implementations of the CRS model, such as measurements of physical phenomena (like sunspots), or alternatively using random sources that might be adversarially influenced. We study the possibility of obtaining universally composable (UC) security in a relaxed variant of the CRS model, where the reference string it taken from an adversarially specified distribution that's unknown to the protocol. On the positive side, we demonstrate that UC general secure computation is obtainable even when the reference string is taken from an arbitrary, adversarially chosen distribution, as long as (a) this distribution has some minimal min-entropy, (b) it has not too long a description, (c) it is efficiently samplable, and (d) the sampling algorithm is known to the adversary (and simulator). On the negative side, we show that if any one of these four conditions is removed then genera! UC secure computation becomes essentially impossible.

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•48 citations
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
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. 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
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally Composable (UC) security provides this guarantee in a strong sense: A UC-secure protocol maintains its security properties even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, many interesting cryptographic tasks are provably impossible to realize with UC security in the standard, “plain” model of computation. Impossibility holds even if ideally authenticated communication channels are provided. In contrast, it has been demonstrated that general secure computation can be obtained in a number of idealized models. Each one of these models represents a form of trust that is put in some of the system’s components. This survey examines and compares some of these trust models, both from the point of view of their sufficiency for building UC secure protocols, and from the point of view of their practical realizability. We start with the common reference string (CRS) model, and then describe several relaxations and alternatives including the Defective CRS model, the key registration models, the hardware token model, the global and augmented CRS models, and a timing assumption. Finally, we briefly touch upon trust models for obtaining authenticated communication.
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.
Abstract. We propose a new security measure for commitment pro-tocols, called Universally Composable (UC) Commitment. The measure guarantees that commitment protocols behave like an \\ideal commitment service, " even when concurrently composed with an arbitrary set of pro-tocols. This is a strong guarantee: it implies that security is maintained even when an unbounded number of copies of the scheme are running concurrently, it implies non-malleability (not only with respect to other copies of the same protocol but even with respect to other protocols), it provides resilience to selective decommitment, and more. Unfortunately, two-party uc commitment protocols do not exist in the plain model. However, we construct two-party uc commitment proto-cols, based on general complexity assumptions, in the common reference string model where all parties have access to a common string taken from a predetermined distribution. The protocols are non-interactive, in the sense that both the commitment and the opening phases consist of a single message from the committer to the receiver.
The common reference string (CRS) model equips all protocol participants with a common string that is sampled from a pre-specified distribution, say the uniform distribution. This model enables otherwise-impossible cryptographic goals such as removing interaction from protocols and guaranteeing composable security. However, knowing the precise distribution of the reference string seems crucial for all known protocols in this model, in the sense that current security analyses fail when the actual distribution of the reference string is allowed to differ from the specified one even by a small amount. This fact rules out many potential implementations of the CRS model, such as measurements of physical phenomena (like sunspots), or alternatively using random sources that might be adversarially influenced. We study the possibility of obtaining universally composable (UC) security in a relaxed variant of the CRS model, where the reference string it taken from an adversarially specified distribution that's unknown to the protocol. On the positive side, we demonstrate that UC general secure computation is obtainable even when the reference string is taken from an arbitrary, adversarially chosen distribution, as long as (a) this distribution has some minimal min-entropy, (b) it has not too long a description, (c) it is efficiently samplable, and (d) the sampling algorithm is known to the adversary (and simulator). On the negative side, we show that if any one of these four conditions is removed then genera! UC secure computation becomes essentially impossible.