Universal composability

An ideal functionality is a protocol in which a trusted party that can communicate over perfectly secure channels with all protocol participants computes the desired protocol outcome. We say that a cryptographic protocol that cannot make use of such a trusted party fulfills an ideal functionality, if the protocol can emulate the behavior of the trusted party for honest users, and if the view that an adversary learns by attacking the protocol is indistinguishable from what can be computed by a simulator that only interacts with the ideal functionality.

The computation model of universal composability is that of interactive Turing machines that can activate each other by writing on each other's communication tapes. An interactive Turing machine is a form of multi-tape Turing machine and is commonly used for modelling the computational aspects of communication networks in cryptography.

The communication model in the bare UC framework is very basic. The messages of a sending party are handed to the adversary who can replace these messages with messages of his own choice that are delivered to the receiving party. This is also the Dolev–Yao threat model (based on the computational model all parties are modeled as interactive Turing machines).

All communication models that add additional properties such as confidentiality, authenticity, synchronization, or anonymity are modeled using their own ideal functionality. An ideal communication functionality takes a message as input and produces a message as output. The (more limited) powers for the adversary $\backslash mathcal\{A\}$ are modeled through the (limited) capacity of the adversary to interact with this ideal functionality.

For an optimal ideal authenticated channel, the ideal functionality $\backslash mathcal\{F\}\_\{\backslash mathsf\{Auth\}\}$ takes a message $m$ from a party with identity $P$ as input, and outputs the same message together with the identity $P$ to the recipient and the adversary. To model the power of the adversary to delay asynchronous communication the functionality $\backslash mathcal\{F\}\_\{\backslash mathsf\{Auth\}\}$ may first send a message to the adversary $\backslash mathcal\{A\}$ and would only deliver the message $m,P$ once it receives the command to do so as a reply.

In an ideal secure channel, the ideal functionality $\backslash mathcal\{F\}\_\{\backslash mathsf\{Sec\}\}$ only outputs the identity of the sender to both the recipient and the adversary, while the message is only revealed to the recipient. This models the requirement that a secure channel is both authenticated and private. To model some leakage about the information that is being transferred, $\backslash mathcal\{F\}\_\{\backslash mathsf\{Sec\}\}$ may reveal information about the message to the adversary, e.g. the length of the message. Asynchronous communication is modeled through the same delay mechanism as for $\backslash mathcal\{F\}\_\{\backslash mathsf\{Auth\}\}$.

While the technical means, and the physical assumptions behind anonymous and pseudonymous communication are very different,Douglas Wikström: "A Universally Composable Mix-Net". TCC 2004: 317–335. {{doi|10.1007/978-3-540-24638-1_18}} the modeling of such channels using ideal functionalities is analogous. See also onion routing and Anonymous P2P. Similar functionalities can be defined for broadcast communication, or synchronous communication.

In an ideal anonymous channel, the ideal functionality, $\backslash mathcal\{F\}\_\{\backslash mathsf\{Anon\}\}$ takes a message $m$ from a party with identity $P$ as input, and outputs the same message but without disclosing the identity $P$ to the recipient and the adversary.

In an ideal pseudonymous channel, the participating parties first register unique pseudonyms with the ideal functionality $\backslash mathcal\{F\}\_\{\backslash mathsf\{Pseu\}\}$. To do a transfer $\backslash mathcal\{F\}\_\{\backslash mathsf\{Pseu\}\}$ takes a message $m$ and the pseudonym $nym$ of the recipient as input. The ideal functionality looks up the owner of the pseudonym and transfers the message $m,\; nym$ without revealing the identity of the sender.

These formalizations abstract from the implementation details of the concrete systems that implement such channels. In their pure form an ideal functionality may be found to be unrealizable. It may be necessary to relax the functionality by leaking more information to the adversary (degree of anonymity). On the other hand communication channels can be physical,Tatsuaki Okamoto: [https://dl.acm.org/doi/10.5555/646336.688247 "On the Relationship among Cryptographic Physical Assumptions".] ISAAC 1993: 369–378 Waka Nagao, Yoshifumi Manabe, Tatsuaki Okamoto: "Relationship of Three Cryptographic Channels in the UC Framework". ProvSec 2008: 268–282. {{doi|10.1007/978-3-540-88733-1_19}} e.g. a mobile device can achieve an anonymous channel by constantly changing its location before transmitting messages that do not contain identifiers.

There exists no bit commitment protocol that is universally composable in the standard model of cryptography. The intuition is that in the ideal model, the simulator has to extract the value to commit to from the input of the environment. This would allow the receiver in the real protocol to extract the committed value and break the security of the protocol. This impossibility result can be applied to other functionalities.

To circumvent the above impossibility result, additional assumptions are required.

Additional setup and trust assumptions, such as the common reference string model and the assumption of a trusted certification authority are also modeled using ideal functionalities in UC.

• Reactive SimulatabilityMichael Backes and Birgit Pfitzmann and Michael Waidner. The Reactive Simulatability (RSIM) Framework for Asynchronous Systems. Cryptology ePrint Archive: Report 2004/082

is a similar model developed concurrently with the universal composability model.

• Abstract/Constructive CryptographyUeli Maurer, Renato Renner:

Abstract Cryptography. ICS 2011: 1–21Ueli Maurer.

Constructive Cryptography - A New Paradigm for Security Definitions and Proofs. TOSCA 2011: 33–56 is a more recent general-purpose model for the composable analysis of cryptographic protocols.

• The GNUC and IITM model are reformulations of universal composability by other researcher (prominently, Victor Shoup and Ralf Kuesters) that influenced new versions of the canonical model by Ran Canetti.

• Abstraction
• Burrows–Abadi–Needham logic
• Hybrid argument
• Mathematical model
• Secure multi-party computation

{{Cryptography navbox}}

Category:Theory of cryptography