Splittability and Characterizing Useless/Complete

2PC functionalities

ECE 598AM Ideal Functionalities in cryptography�

https://www.iacr.org/archive/crypto2008/51570262/51570262.pdf

​

Short interlude: Category Theory

Category Theory: a very generic set of notation rules that apply to very many mathematical definitions. We can use it to pick default notation choices.

A Category is a collection of Objects and Arrows between objects, satisfying

- (Identities) There is an identity arrow for each object.

- (Composition) Arrows are Closed under composition

- (Associativity) (f o g) o h = f o (g o h)

More examples from Category theory

Initial object: there’s an arrow from this object to every other

Terminal object: there’s an arrow from every object to this one

More examples from Category theory

Endofunctor: a function M mapping objects to objects, arrows to arrows,�Satisfying:

- For every arrow p from A to B, M(p) is an arrow from M(A) to M(B)

- (Identity preserving) M(id_A) = id_M(A)

- (Composition preserving) M(p) o M(q) = M(p o q)

Focus for today: Two Party secure computations

We can use FCom (plus channels) to instantiate generic 2PC for any function.

​

We have shown an impossibility result for FCom in the plain model (just channels and hardness assumptions, but no trusted setup).

We’ve also shown two setup functionalities (F_RandOrcl, F_CommonRefStr) that suffice to implement FCom, and hence the rest.

What other functionalities could be used as setup to realize FCom? (Complete)

What functions are realizable in the plain model? (Useless)�Is there anything in between?

Complete functionalities��Can realize Commitment

Useless functionalities��Can be realized in plain model

Are there 2-party functionalities that are neither useless nor complete?

Unsplittable

Splittable

Not splittable, but not unsplittable

Restricting focus further: 2REGULAR

We’ll only look at realizing Ideal Functionalities that:

- Only interacts with a sender S and receiver R, not with adv

- The input/output behavior is the same regardless of which parties are corrupt

​

Note that F_2PC, F_Com, F_p2p all satisfy this

(F_Auth, F_RBC, other broadcasts, do not)

Splittability: a game characterizing useless/complete funcs

F is Splittable if there exists a T such that these two experiments are indisting.

Property of an ideal functionality (not of a protocol, or of a setup functionality)

​

​

Note there is no protocol, hybrid world func, only T.

Example: Functionality outputting a one way function

Example: Functionality outputting a one way function

Example: Functionality outputting a one way function

We’re stuck. T would need to invert the OWF.

This is *Unsplittable*

Splittability: a game characterizing useless/complete funcs

Theorems to go over today:

F is useless (can be realized in plain model) iff it is splittable

F is complete (can realize F_Com from it) iff it is unsplittable

Warmp: If splittable, we can realize this in plain model

Converse: If F is UC realizable in the plain model,

then we can show it is splittable.

By assuming pi realizes F, in the case that no parties are corrupted.

(The double arrow indicates p2p private communication channel)

Now consider an environment Z’ that corrupts the sender P1, but still follows the ordinary protocol (e.g., benign corruption).

Real world (benign corrupt sender)

Real world (no corruptions)

Because we assumed pi realizes F, we have a simulator for the Sender-Corrupt case

Real world (benign corrupt sender)

Ideal world (benign corrupt sender)

Ideal world (benign corrupt sender)

Real world (corrupt receiver)

Now consider a new environment Z’’ that corrupts the receiver, but internally runs the S2 simulator

Real world (corrupt receiver)

Ideal world (corrupt receiver)

Again because pi realizes F, we have a simulator S1 for the corrupt receiver case

Ideal world (corrupt receiver)

Finally we’ve shown that F is splittable.�QED

Given an unsplittable F, we can construct an FCom

Notes on the approach:

- We’ll use F to upgrade �1. an ordinary binding/hiding (non-UC) commitment protocol�2. A standalone secure 2pc

- To give just the key idea, �will only show corrupt rcvr.

- Will only show for concrete� F based on OWF as before

(a non-equivocal commitment)

Constructing FCom from �an unsplittable functionality

Standalone secure �Subprotocol:

From environment, instructions for dummy adversary (corrupt receiver)

From FCom in ideal world

Since the simulator runs the subprotocol honestly, it does not need to be UC secure

FCom

Z