Imagine Alice has $n$ values $m_i$, and she wants to share one of these values with Bob. Note that Bob does not want to reveal exactly which value he has selected. The solution to this problem is called “oblivious transfer.” There exists a well-known protocol that leverages an encryption scheme $E,D$ that has a commutative property:
\[\forall k_1,k_2\colon 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 as 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_j)$
- Bob decrypts the received message with his key and receives $m_j$
While working with malicious parties, proof of valid encryptions and decryptions can also be added at stages 1, 2, and 3.
Regarding the encryption protocol, we can leverage any symmetric encryption scheme in CTR mode because it uses an XOR operation, which has a commutative property.
Using an oblivious transfer protocol allows us to build a generalized secure multiparty computation of an arbitrary circuit. The following approach to circuits is called ‘garbled circuits,’ or simply GC.
Imagine Alice and Bob want 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 GC definition, let’s first define the case where Alice is the initiator. First, Alice generates two symmetric keys: $K_B^1, K_B^0$. Knowing her own 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 oblivious transfer protocol with Bob, where Bob selects the corresponding key for his input (Alice notifies Bob which value corresponds to each bit).
Finally, Bob decrypts the result and shares it with Alice.
Now, imagine we do not want to allow Alice to generate a circuit by herself. Then, the third party builds a circuit with the following parameters:
- for each participant (Alice and Bob), it generates 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}(\mathbb{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 (coupled with a proof of a valid encryption process) is shared between Alice and Bob ( elements of this list follow in arbitrary order).
Then, the third party runs an oblivious 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 at the previous stage, additionally shuffles them, and submits them to Bob. In turn, Bob decrypts all encryptions, receiving a binary result in only one of them and garbage in the others. This binary result corresponds to the circuit output. After that, Bob shares the result with Alice.
In cases 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.