Universal Composability

Resources

Ran Canetti

Detailed presentation of UC, its shortcomings, and ways around it

25 episodes / 4 hours

Tutorial style papers

Christian Badertscher, Ueli Maurer, Daniel Tschudi and Vassilis Zikas

See Ouroboros

Questions on Cryptography StackExchange

Preliminaries

Model of protocol execution: A protocol execution consists of a set of interacting computing elements modelled as interactice Turing machines (ITMs).

Adversary: An adversary is another ITM with the following properties:

Controls a subset of parties

Control over scheduling and delivering messages (subject to synchrony property)

Inputs: Parties are interacting on a given set of inputs

Global outputs: Each party eventually generates a local output. The global output is the concatenation of all parties and the adversary local output.

Ideal process: In the ideal process for evaluating some function f, all parties ideally hand their inputs to an incorruptible trusted party, who computes the function values and hands them to the parties as specified. Here the adversary is limited to interacting with the trusted party in the name of the corrupted parties. Protocol π securely evaluates a function f if for any adversary A (that interacts with the protocol) there exists an ideal-process adversary S such that, for any set of inputs to the parties, the global output of running π with A is indistinguishable from the global output of the ideal process for f with adversary S.

This definition does not hold for the concurrent execution of processes!

In UC, the adversary can freely interact with the environment (information exchange after messages or generated output)

https://gyazo.com/1eed9e14ed9c941e887c9226ad5ebf58

UC model

Idea: The security of a system is reflected only in its effects on the rest of the external environment.

Design an ideal functionality F with a certain specification.

System P UC-realizes F if for any environment E the execution cannot determine if it is on the ideal functionality with a simulator or the sytem.

Construction of UC

Model: $ (\mathcal{E}, \mathcal{A}, \pi_1, .., \pi_n) (Environment, Adversary, protocol instance 1 to n)

Execution: $ \mathrm{EXEC}_{\pi, \mathcal{A}, \mathcal{E}} represents the esemble of distributions form the input of the environment from {0,1}

Protocol execution

https://gyazo.com/3c0533e56b519a253fffa09baae881b4

Ideal protocol

https://gyazo.com/d44972b05dd3b8744f76ac9fd933203a

Definition (protocol emulation, informal statement): Protocol $ \pi UC-emulates (ideal) protocol $ \phi if for any adversary $ \mathcal{A} there exists an adversary $ \mathcal{S} such that, for any environment $ \mathcal{E} the ensembles $ \mathrm{EXEC}_{\pi, \mathcal{A}, \mathcal{E}} and $ \mathrm{EXEC}_{\phi, \mathcal{S}, \mathcal{E}} are indistinguishable. That is, on any input, the probability that $ \mathcal{E} outputs 1 after interacting with $ \mathcal{A} and parties running $ \pidiffers by at most a negligible amount from the probability that $ \mathcal{E}outputs 1 after interacting with $ \mathcal{S} and $ \phi.

F-hybrid protocols

Parties in an arbirtrary protocol make calls to an ideal functionality F.

There are multiple instances of F and parties can make calls to those instances.

The instances of F run at the same time without any global coordination.

The protocol needs to distinguish the instances of F (UC only provides the session identifiers)

Approach of UC

Define the ideal functionalities of the ledger

Define the protocol(s) that implement the ledger

Define the simulators that interact with the environment

Prove that ideal functionality and the protocol with the simulators are indistinguishable

Prove chain specific properties (common prefix, chain growth, chain quality etc.) from the ideal ledger functionality later

Protocols

UC allows to handle sub-protocols

Prove that sub-protocol is secure and than use composition to prove that the resulting protocol is also secure

Interactice Turing Machine/Instances

Basic model of "units" or processes in UC are Interactive Turing machines with a range of tapes

Assumption: each ITM is able to complete their computations at polynomial time

An instance of an ITM is called an Interatice Turing machine Instance (ITI)

Extensions

Ran Cohen, Sandro Coretti, Juan Garay and Vassilis Zikas

Crypto '16 slide

Define secure multi-party computation (MPC) with probabilistic termination in the UC framework and prove a universal composition theorem for probabilistic-termination protocols

Kevin Liao (University of Illinois), Matthew A. Hammer (DFINITY) and Andrew Miller (University of Illinois)

Juan Garay (AT&T Labs), Jonathan Katz (University of Maryland), Ueli Maurer (ETH Zurich) , Bj¨orn Tackmann (ETH Zurich) and Vassilis Zikas (UCLA)