Universal composability
Encyclopedia
The framework of Universal Composability (UC) is a general-purpose model for the analysis of cryptographic protocols. It guarantees very strong security properties. Protocols remain secure even if arbitrarily composed with other instances of the same or other protocols. Security is defined in the sense of protocol emulation. Intuitively, a protocol is said to emulate another one, if no environment (observer) can distinguish the executions. Literally, the protocol may simulate the other protocol (without having access to the code). The notion of security is derived by implication. Assume a protocol P_1 is secure per definition. If another protocol P_2 emulates protocol P_1 such that no environment tells apart the emulation from the execution of the protocol, then the emulated protocol P_2 is as secure as protocol P_1.
that only interacts with the ideal functionality.
.
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 produce a message as output. The (more limited) powers for the adversary
are modeled through the (limited) capacity of the adversary to interact with this ideal functionality.
Ideal authenticated channel: For an optimal ideal authenticated channel, the ideal functionality
takes a message 
from a party with identity 
as input, and outputs the same message together with the identity 
to the recipient and the adversary. To model the power of the adversary to delay asynchronous communication
the functionality
may first send a message to the adversary 
and would only deliver the message 
once it receives the command to do so as a reply.
Ideal secure channel: In an ideal secure channel
, the ideal functionality
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, 
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
.
and Anonymous P2P
. Similar functionalities can be defined for broadcast communication, or synchronous communication.
Ideal anonymous channel: In an ideal anonymous channel
, the ideal functionality,
takes a message 
from a party with identity 
as input, and outputs the same message but without disclosing the identity 
to the recipient and the adversary.
Ideal pseudonymous channel: In an ideal pseudonymous channel
, the participating parties first register unique pseudonyms with the ideal functionality
. To do a transfer 
takes a message 
and the pseudonym 
of the recipient as input. The ideal functionality looks up the owner of the pseudonym and transfers the message 
without revealing the identity of the sender.
These formalisations 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 , e.g. a mobile device can achieve an anonymous channel by constantly changes its location before transmitting messages that do not contain identifiers.
, or the assumption of a trusted certification authority are also modeled using ideal functionalities in UC.
Ideal functionality
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 fulfils an ideal functionality, if the protocol can emulate the behaviour 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 simulatorSimulation (disambiguation)
Simulation may refer to:* Simulation, the imitation of some real thing, state of affairs, or process* Computer simulation, simulation via computers* Simulation game, a video game that is a computer simulation...
that only interacts with the ideal functionality.
Computation model
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 cryptographyCryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
Communication model
The communication model in the bare UC framework is very basic. The message of a sending party are handed to the adversary who can replace these messages with a messages of his own choice that is 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
Confidentiality
Confidentiality is an ethical principle associated with several professions . In ethics, and in law and alternative forms of legal resolution such as mediation, some types of communication between a person and one of these professionals are "privileged" and may not be discussed or divulged to...
, authenticity
Authentication
Authentication is the act of confirming the truth of an attribute of a datum or entity...
, synchronization
Synchronization
Synchronization is timekeeping which requires the coordination of events to operate a system in unison. The familiar conductor of an orchestra serves to keep the orchestra in time....
, or anonymity
Anonymity
Anonymity is derived from the Greek word ἀνωνυμία, anonymia, meaning "without a name" or "namelessness". In colloquial use, anonymity typically refers to the state of an individual's personal identity, or personally identifiable information, being publicly unknown.There are many reasons why a...
are modeled using their own ideal functionality. An ideal communication functionality takes a message as input and produce a message as output. The (more limited) powers for the adversary
are modeled through the (limited) capacity of the adversary to interact with this ideal functionality.Ideal authenticated channel: For an optimal ideal authenticated channel, the ideal functionality
takes a message from a party with identity as input, and outputs the same message together with the identity to the recipient and the adversary. To model the power of the adversary to delay asynchronous communicationAsynchronous communication
In telecommunications, asynchronous communication is transmission of data without the use of an external clock signal, where data can be transmitted intermittently rather than in a steady stream. Any timing required to recover data from the communication symbols is encoded within the symbols...
the functionality
may first send a message to the adversary and would only deliver the message once it receives the command to do so as a reply.Ideal secure channel: In an ideal secure channel
Secure channel
In cryptography, a secure channel is a way of transferring data that is resistant to interception and tampering.A confidential channel is a way of transferring data that is resistant to interception, but not necessarily resistant to tampering....
, the ideal functionality
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, may reveal information about the message to the adversary, e.g. the length of the message. Asynchronous communicationAsynchronous communication
In telecommunications, asynchronous communication is transmission of data without the use of an external clock signal, where data can be transmitted intermittently rather than in a steady stream. Any timing required to recover data from the communication symbols is encoded within the symbols...
is modeled through the same delay mechanism as for
.More advanced channels
While the technical means, and the physical assumptions behind anonymous and pseudonymous communication are very different, the modeling of such channels using ideal functionalities is analogous. See also onion routingOnion routing
Onion routing is a technique for anonymous communication over a computer network. Messages are repeatedly encrypted and then sent through several network nodes called onion routers. Like someone unpeeling an onion, each onion router removes a layer of encryption to uncover routing instructions, and...
and Anonymous P2P
Anonymous P2P
An anonymous P2P communication system is a peer-to-peer distributed application in which the nodes or participants are anonymous or pseudonymous...
. Similar functionalities can be defined for broadcast communication, or synchronous communication.
Ideal anonymous channel: In an ideal anonymous channel
Anonymous remailer
An anonymous remailer is a server computer which receives messages with embedded instructions on where to send them next, and which forwards them without revealing where they originally came from...
, the ideal functionality,
takes a message from a party with identity as input, and outputs the same message but without disclosing the identity to the recipient and the adversary.Ideal pseudonymous channel: In an ideal pseudonymous channel
Pseudonymous remailer
A pseudonymous remailer or nym server, as opposed to an anonymous remailer, is an Internet software program designed to allow people to write pseudonymous messages on Usenet newsgroups and send pseudonymous email. Unlike purely anonymous remailers, it assigns its users a user name, and it keeps a...
, the participating parties first register unique pseudonyms with the ideal functionality
. To do a transfer takes a message and the pseudonym of the recipient as input. The ideal functionality looks up the owner of the pseudonym and transfers the message without revealing the identity of the sender.These formalisations 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
Degree of anonymity
In anonymity networks it is important to be able to measure quantitatively the guarantee that is given to the system. The degree of anonymity d is a device that was proposed at the 2002 Privacy Enhancing Technology conference...
). On the other hand communication channels can be physical , e.g. a mobile device can achieve an anonymous channel by constantly changes its location before transmitting messages that do not contain identifiers.
Setup and trust assumptions
Additional setup and trust assumptions, such as the common reference string modelCommon reference string model
In cryptography, the common reference string model captures the assumption that a trusted setup in which all involved parties get access to the same string crs taken from some distribution D exists. Schemes proven secure in the CRS model are secure given that the setup was performed correctly...
, or the assumption of a trusted certification authority are also modeled using ideal functionalities in UC.
See also
- Virtual Party Protocol
- Secure channelSecure channelIn cryptography, a secure channel is a way of transferring data that is resistant to interception and tampering.A confidential channel is a way of transferring data that is resistant to interception, but not necessarily resistant to tampering....
- Burrows-Abadi-Needham logicBurrows-Abadi-Needham logicBurrows–Abadi–Needham logic is a set of rules for defining and analyzing information exchange protocols. Specifically, BAN logic helps its users determine whether exchanged information is trustworthy, secured against eavesdropping, or both...
- AbstractionAbstractionAbstraction is a process by which higher concepts are derived from the usage and classification of literal concepts, first principles, or other methods....
- Mathematical modelMathematical modelA mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...
- Common reference string modelCommon reference string modelIn cryptography, the common reference string model captures the assumption that a trusted setup in which all involved parties get access to the same string crs taken from some distribution D exists. Schemes proven secure in the CRS model are secure given that the setup was performed correctly...