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

On the Necessary and Sufficient Assumptions for UC Computation.

Ivan Damgård, Jesper Buus Nielsen, Claudio Orlandi

Published Jan 1, 2009• 2 citations
OpenAlex

Abstract

Abstract. We study the necessary and sufficient assumptions for universally composable (UC) computation, both in terms of setup and computational assumptions. We look at the common reference string model, the uniform random string model and the key-registration authority model (KRA), and provide new results for all of them. Perhaps most interestingly we show that: – For even the minimal meaningful KRA, where we only assume that the secret key is a value which is hard to compute from the public key, one can UC securely compute any poly-time functionality if there exists a passive secure oblivious-transfer protocol for the stand-alone model. Since a KRA where the secret keys can be computed from the public keys is useless, and some setup assumption is needed for UC secure computation, this establishes the best we could hope for the KRA model: any non-trivial KRA is sufficient for UC computation. – We show that in the KRA model one-way functions are sufficient for UC commitment and UC zero-knowledge. These are the first examples of UC secure protocols for non-trivial tasks which do not assume the existence of public-key primitives. In particular, the protocols show that non-trivial UC computation is possible in Minicrypt. 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

A Zero-One Law for Cryptographic Complexity with Respect to Computational UC Security

Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek

It is well-known that most cryptographic tasks do not have universally composable (UC) secure protocols, if no trusted setup is available in the framework. On the other hand, if a task like fair coin-tossing is available as a trusted setup, then all cryptographic tasks have UC-secure protocols. What other trusted setups allow UC-secure protocols for all tasks? More generally, given a particular setup, what tasks have UC-secure protocols?We show that, surprisingly, every trusted setup is either useless (equivalent to having no trusted setup) or all-powerful (allows UC-secure protocols for all tasks). There are no “intermediate” trusted setups in the UC framework. We prove this zero-one law under a natural intractability assumption, and consider the class of deterministic, finite, 2-party functionalities as candidate trusted setups.One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality. Another contribution of independent interest is to optimize the hardness assumption used by Canetti et al. (STOC 2002) in showing that the common random string functionality is complete (a result independently obtained by Damgård et al. (TCC 2010)).

Lecture notes in computer science•Jan 1, 2010•36 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

Practical UC security with a Global Random Oracle.

Ran Canetti, Abhishek Jain, Alessandra Scafuro

We show that there exist commitment, zero-knowledge and general function evaluation pro-tocols with universally composable security, in a model where all parties and all protocols have access to a single, global, random oracle and no other trusted setup. This model provides sig-nificantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [CCS’93] or even the common reference string model. Indeed, these latter models provide no security guarantees in the presence of arbitrary protocols that use the same random oracle (or reference string or hash function). Furthermore, our protocols are highly efficient. Specifically, in the interactive setting, our commitment and general computation protocols are much more efficient than the best known ones due to Lindell [Crypto’11,’13] which are secure in the common reference string model. In the non-interactive setting, our protocols are slightly less efficient than the best known ones presented by Afshar et al. [Eurocrypt ’14] but do away with the need to rely on a non-global (programmable) reference string. 1

•Jan 1, 2014•0 citations

UC-Secure Non-interactive Public-Key Encryption

Jan L. Camenisch, Anja Lehmann, Gregory Neven +1 more

The universal composability (UC) framework enables the modular design of cryptographic protocols by allowing arbitrary compositions of lower-level building blocks. Public-key encryption is unarguably a very important such building block. However, so far no UC-functionality exists that offers non-interactive encryption necessary for modular protocol construction. We provide an ideal functionality for non-committing encryption (i.e., public-key encryption secure against adaptive corruptions) with locally generated, and therefore non-interactive, ciphertexts. As a sanity check, we also provide a property-based security notion that we prove to be equivalent to the UC notion. We then show that the encryption scheme of Camenisch et al. (SCN '16) based on trapdoor permutations securely implements our notion in the random-oracle model without assuming secure erasures. This is the best one can hope to achieve as standard-model constructions do not exist due to the uninstantiability of round-optimal adaptively secure message transfer in the standard model (Nielsen, Crypto '02). We illustrate the modular reusability of our functionality by constructing the first non-interactive signcryption scheme secure against adaptive corruptions without secure erasures in the UC framework.

IEEE Computer Security Foundations Workshop (CSFW)•Aug 1, 2017•7 citations

Efficient and Universally Composable Security Oblivious Transfer

Fenghua Li

Non-committing encryption achieved only semantic security,in contrast,applications often require security against chosen ciphertext attacks.A main ingredient in the previous adaptive universally composable(UC)oblivious transfer protocols are non-committing encryptions.the previous proposals are not UC secure against adaptive adversaries in the so-called non-erase model.A new UC secure oblivious transfer protocols were proposed and schemes utilize two primitives of the verifiably smooth projective hashing and deniable encryption as constructed by.the double trapdoor decryption mechanism based on trapdoor commitment.Our construction is based on the decisional composite residuosity in common reference string (CRS) model.We constructed a two-message(1-round) string oblivious transfer protocol,which improves computational efficient that supports message spaces of size exponential and save O(n)-1 rounds communications efficient than bit-OT protocols.

Dianzi xuebao•Jan 1, 2008•1 citation
Abstract. We study the necessary and sufficient assumptions for universally composable (UC) computation, both in terms of setup and computational assumptions. We look at the common reference string model, the uniform random string model and the key-registration authority model (KRA), and provide new results for all of them. Perhaps most interestingly we show that: – For even the minimal meaningful KRA, where we only assume that the secret key is a value which is hard to compute from the public key, one can UC securely compute any poly-time functionality if there exists a passive secure oblivious-transfer protocol for the stand-alone model. Since a KRA where the secret keys can be computed from the public keys is useless, and some setup assumption is needed for UC secure computation, this establishes the best we could hope for the KRA model: any non-trivial KRA is sufficient for UC computation. – We show that in the KRA model one-way functions are sufficient for UC commitment and UC zero-knowledge. These are the first examples of UC secure protocols for non-trivial tasks which do not assume the existence of public-key primitives. In particular, the protocols show that non-trivial UC computation is possible in Minicrypt. 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.
It is well-known that most cryptographic tasks do not have universally composable (UC) secure protocols, if no trusted setup is available in the framework. On the other hand, if a task like fair coin-tossing is available as a trusted setup, then all cryptographic tasks have UC-secure protocols. What other trusted setups allow UC-secure protocols for all tasks? More generally, given a particular setup, what tasks have UC-secure protocols?We show that, surprisingly, every trusted setup is either useless (equivalent to having no trusted setup) or all-powerful (allows UC-secure protocols for all tasks). There are no “intermediate” trusted setups in the UC framework. We prove this zero-one law under a natural intractability assumption, and consider the class of deterministic, finite, 2-party functionalities as candidate trusted setups.One important technical contribution in this work is to initiate the comprehensive study of the cryptographic properties of reactive functionalities. We model these functionalities as finite automata and develop an automata-theoretic methodology for classifying and studying their cryptographic properties. Consequently, we completely characterize the reactive behaviors that lead to cryptographic non-triviality. Another contribution of independent interest is to optimize the hardness assumption used by Canetti et al. (STOC 2002) in showing that the common random string functionality is complete (a result independently obtained by Damgård et al. (TCC 2010)).
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.
We show that there exist commitment, zero-knowledge and general function evaluation pro-tocols with universally composable security, in a model where all parties and all protocols have access to a single, global, random oracle and no other trusted setup. This model provides sig-nificantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [CCS’93] or even the common reference string model. Indeed, these latter models provide no security guarantees in the presence of arbitrary protocols that use the same random oracle (or reference string or hash function). Furthermore, our protocols are highly efficient. Specifically, in the interactive setting, our commitment and general computation protocols are much more efficient than the best known ones due to Lindell [Crypto’11,’13] which are secure in the common reference string model. In the non-interactive setting, our protocols are slightly less efficient than the best known ones presented by Afshar et al. [Eurocrypt ’14] but do away with the need to rely on a non-global (programmable) reference string. 1
The universal composability (UC) framework enables the modular design of cryptographic protocols by allowing arbitrary compositions of lower-level building blocks. Public-key encryption is unarguably a very important such building block. However, so far no UC-functionality exists that offers non-interactive encryption necessary for modular protocol construction. We provide an ideal functionality for non-committing encryption (i.e., public-key encryption secure against adaptive corruptions) with locally generated, and therefore non-interactive, ciphertexts. As a sanity check, we also provide a property-based security notion that we prove to be equivalent to the UC notion. We then show that the encryption scheme of Camenisch et al. (SCN '16) based on trapdoor permutations securely implements our notion in the random-oracle model without assuming secure erasures. This is the best one can hope to achieve as standard-model constructions do not exist due to the uninstantiability of round-optimal adaptively secure message transfer in the standard model (Nielsen, Crypto '02). We illustrate the modular reusability of our functionality by constructing the first non-interactive signcryption scheme secure against adaptive corruptions without secure erasures in the UC framework.
Non-committing encryption achieved only semantic security,in contrast,applications often require security against chosen ciphertext attacks.A main ingredient in the previous adaptive universally composable(UC)oblivious transfer protocols are non-committing encryptions.the previous proposals are not UC secure against adaptive adversaries in the so-called non-erase model.A new UC secure oblivious transfer protocols were proposed and schemes utilize two primitives of the verifiably smooth projective hashing and deniable encryption as constructed by.the double trapdoor decryption mechanism based on trapdoor commitment.Our construction is based on the decisional composite residuosity in common reference string (CRS) model.We constructed a two-message(1-round) string oblivious transfer protocol,which improves computational efficient that supports message spaces of size exponential and save O(n)-1 rounds communications efficient than bit-OT protocols.