Obvious transfer

Imagine Alice has $n$ values $m_{i}$ , and she wants to share one of this value with Bob. Note that Bob does not want to reveal what exactly value he has selected. The solution to this problem is called “Obvious transfer”. There exists a well known protocol that leverages an encryption scheme $E, D$ that owns a commutative property:

\forall k_{1}, k_{2} : D_{k_{1}} (D_{k_{2}} (E_{k_{1}} (E_{k_{2}} (m)))) = D_{k_{2}} (D_{k_{1}} (E_{k_{1}} (E_{k_{2}} (m))))

Then, the transfer protocol is follows:

Alice shares with Bob encryptions $E_{A} (m_{0}), E_{A} (m_{1}) \dots, E_{A} (m_{n - 1})$
Bob selects $j \in [n]$ and sends $E_{B} (E_{A} (m_{j}))$ to Alice
Alice decrypts the received message with her key and sends $E_{B} (m_{i})$
Bob decrypts the received message with his key and receives $m_{i}$

While working with malicious parties, the proof of valid encryptions end decryptions can also be added on the 1,2,3 stages._

Regarding the encryption protocol we can leverage any symmetric encryption scheme in the CTR mode, because of the usage of xor operation that owns a commutative property.

The usage of obvious transfer protocol allows us to build a generalized secure multi party computation of an arbitrary circuit.

Imagine Alice and Bob wants to evaluate the AND gate without sharing their input bits.

A	B	AND
1	1	1
1	0	0
0	1	0
0	0	0

Following the original definition let’s firstly define the case where Alice is the initiator. Firstly, Alice generates two symmetric keys: $K_{B}^{1}, K_{B}^{0}$ . By knowing self input (for example $1$ ), Alice takes a corresponding row from the table and encrypts each possible result.

B	AND
1	$E_{K_{B}^{1}} (1)$
0	$E_{K_{B}^{0}} (0)$

Then, Alice runs an Obvious transfer protocol with Bob, where Bob selects a corresponding key for his input (Alice notifies Bob which value corresponds for each bit).

Finally, Bob decrypts the result and shares it with the Alice.

Now, imagine we do not want to allow Alice generate a circuit by herself. Then, the third party builds a circuit with the following parameters:

for each participant (Alice and Bob) it generates a symmetric keys $K_{P}^{b}$ where $P \in {A, B}$ and $b \in {0, 1}$
it encrypts each possible output for the input pair $(x, y)$ as $E_{K_{A}^{x}} (E_{K_{B}^{y}} (AND (x, y)))$

A	B	AND
1	1	$E_{K_{A}^{1}} (E_{K_{B}^{1}} (1))$
1	0	$E_{K_{A}^{1}} (E_{K_{B}^{0}} (0))$
0	1	$E_{K_{A}^{0}} (E_{K_{B}^{1}} (0))$
0	0	$E_{K_{A}^{0}} (E_{K_{B}^{0}} (0))$

This list of encryptions (in a couple with a proof of valid encryption process) is shared between Alice and Bob ( elements of this list follows in arbitrary order).

Then, the third party runs an obvious transfer protocol separately for Alice and Bob, where they select a key that corresponds to their inputs.

After receiving the key, Alice decrypts all elements with her key, received on the previous stage, additionally shuffles them and submits to Bob. In turn, Bob decrypts all encryptions, receiving a binary result in only one of them and the garbage in others. This binary results corresponds to the circuit output. After that, Bob shares the result with Alice.

In case where the circuit contains more gates, the input gates output the keys to the next (intermediate) gates and only the last gates output the valid resulting values.

Note that this computation protocol requires an encryption scheme in which a valid decryption can be distinguished from an invalid decryption.

Blog

Explorer

Obvious transfer

Graph View