Secure Computation with Oblivious Transfer

The Internet is an untrusted place that lots of hackers and eves-droppers looking into your precious information. Saving your data is not that easy thing to do unless cryptography was invented. In this blog post, we will look into one of the interesting parts in cryptography, which called Secure Multi-party Computation(MPC). Here, multiple parties participate to perform a computation without revealing their inputs.

Oblivious Transfer

Alice has two messages for Bob. But Alice allows reading only one message to Bob. Also, Bob does not like let know Alice, which message he read. Oblivious Transfer allows you to solve this kind of problems.

Lets M0 and M1 are the values that Alice keep and Bob needs to read only M0 without telling Alice M0 was read. Both parties agreed on the generator “g”. Alice and Bob generate random number “a” and “b” which are private for themselves. Alice calculates “A” by A = g^a and sends it to Bob. Bob calculate value “B” by either B = g^b if Bob needs to read “M0” or B = A*(g^b) if “M1” needs to read. Now Bob sends value B to the Alice and she calculates value “K0” and “K1” by K0 = Hash(B^a) and K1 = Hash( (B/A)^a). Then Alice encrypts the message “M0” and “M1” to “E1” and “E2” by using “K0” and “K1” as the key. Alice sends both “E0” and “E1” to the Bob. Now Bob calculates decryption key “K” by K = Hash(A^b) and tries to decrypt both messages. But only one message will be able to decrypt, and others not.

Image from https://asecuritysite.com/encryption/ot

Oblivious transfer is the base concept behind the zero-knowledge proof. We can extend this method such that we can create a circuit so that one person generate a function and another person evaluate and get the result.

Yao’s Garble Circuit

Let’s think Alice and Bob need to evaluate some logic circuit. Alice gives her input and circuit encrypted to Bob. Then bob uses his input and evaluates the solution.

For example, let’s take Alice and Bob need to evaluate AND gate. Alice needs input one to the circuit and Bob need to input zero to the circuit. The result should zero according to the truth table as follows.

╔═══╦═══╦═══════╗
║ A ║ B ║ C=A.B ║
╠═══╬═══╬═══════╣
║ 0 ║ 0 ║     0 ║
║ 0 ║ 1 ║     0 ║
║ 1 ║ 0 ║     0 ║
║ 1 ║ 1 ║     1 ║
╚═══╩═══╩═══════╝

Now Alice creates an encrypted circuit as follows such that Bob can evaluate it and get the result. First Alice selects four random keys to encrypt each input A and B in AND table.

Key_A_0 = Random key to encrypt Alice’s input zero
Key_A_1 = Random key to encrypt Alice’s input one
Key_B_0 = Random key to encrypt Bob’s input zero
Key_B_1 = Random key to encrypt Bob’s input one

Then we can use these key to encrypt the result of the AND gate truth table as follows. Here, C[x] stands for x th row value in column C and Encrypt(key, value) is an encryption function to encrypt value with a given key.

Cipher_00 = Encrypt(Key_B_0,  Encrypt(Key_A_0,C[0]))
Cipher_01 = Encrypt(Key_B_1,  Encrypt(Key_A_0,C[1]))
Cipher_10 = Encrypt(Key_B_0,  Encrypt(Key_A_1,C[2]))
Cipher_11 = Encrypt(Key_B_1,  Encrypt(Key_A_1,C[3]))

Now Alice sends this encrypted circuit(Cipher_00, Cipher_01, Cipher_10, and Cipher_11) to the Bob to evaluate. Since Alice input to the circuit is one, she also sends Key_A_1 to the Bob. Now Bob needs to give his input to the circuit. Since keys defined by Alice, Bob needs to take Key_B_0 from the Alice without revealing that Bob requested Key_B_0. For that, we can use Oblivious transfer to get the key without revealing Alice which key accessed. Once Bob takes the relevant key for his input from Alice by using Oblivious transfer, Bob tries to decrypt Cipher_00, Cipher_01, Cipher_10 and Cipher_11 with Alice given key and Bob’s key. Here, only one cipher able to decrypt and it would be the solution for the given inputs and the circuit.

In this system, Alice only provides her input as the key to decrypt the result. Since it is just a key, Bob unable to find out whether it one or zero. Since Bob used the oblivious transfer to get his key from the Alice, Alice does not know what is Bob’s input for the circuit.

Practical implementations of Oblivious Transfer

There are multiple Oblivious Transfer implementation available as libraries for a different programming language. You can find out a list of libraries at the end of this document. We will look into OblivC library that use Oblivious Transfer to perform a secure multiparty computation.

OblivC was written to use with C language. Example program to solve Yao’s millionaire problem will be as follows.

void millionaire (void ∗args) { ProtocolIO ∗io = args; obliv int a, b;
   obliv bool res = false;
   a = feedOblivInt (io−>myinput, 1);
   b = feedOblivInt (io−>myinput, 2); 
   obliv if (a < b) 
        res = true; 
   revealOblivBool (&io−>result, res, 0);
}

You can define variable that need to hide by adding “obliv” keyword in front of variable declaration. Then load the input with “feedOblivInt” function. Comparison done by special if command that defined by adding “obliv” keyword in front if condition. Final result resolve by using “revealOblivBool()” function.

There are multiple other implementation available over the internet and I have listed down some of it.

1. Share Mind
2. ABY
3. JIFF
4. Geppetri

Conclusion

Secure Multiparty Computation is ongoing research area that solve computation problems without revealing their inputs. Oblivious Transfer provide base concept for Zero knowledge proof. Garble Circuit implemented on top of Oblivious Transfer protocol to perform computation without revealing information of each others. Multiple open source applications and libraries are also freely available for Secure Multiparty Computation.

Hope this article would be helpful for you and see you in next article. Follow me on twitter to know more about technical stuff. Cheers !