Garbled Circuits — SFE With Oblivious Transfer

The demonstration of the method used in this article is here.

Garbled Circuits — SFE With Oblivious Transfer

The demonstration of the method used in this article is here.

Introduction

Who can you really trust on the Internet? Basically… no-one!

So why do we give away so much of our data in order to answer simple questions? To prove that we own a bank account, we must give away our CVS number, so that anyone listening can then determine it. In order to prove our age, we must give away our date-of-birth, and where someone can then use it to spoof your ID. In this article we will use a garbled (or scrambled) circuit with SFE (Secure Function Evaluation) to hide our choices.

Bob meets Alice

So let’s say that Bob and Alice just don’t trust each other. They have had a bad time, but they still want to make some decisions, and that they don’t even trust their lawyer anymore.

So they agree a secure protocol, where they must either both agree to something (A & B) or one of them just has to agree (A or B), or when just one agrees and the other does not agree (A xor B). This is a simple logic function.

Let’s say they agree to both agree on something, so we have an AND function (A & B). We now create a scrambled AND gate. For this we get:

A B Z
0 0 0
0 1 0
1 0 0
1 1 1

Now Bob created four encryption keys K(a=0), K(a=1), K(b=0) and K(b=1). Now he will go ahead and encrypt the four possible outputs (in this case “0”, “0”, “0”, and “1”), using the two encryption keys associated with the bits. For example the output:

A=0, B=0, Z=0

will encrypt the output (“0), with the keys of K(a=0) and K(b=0).

In Python here is the code:

keyX_0 = Fernet.generate_key()
keyX_1 = Fernet.generate_key()
keyY_0 = Fernet.generate_key()
keyY_1 = Fernet.generate_key()
data =[]
for a in range(0,2):
    for b in range(0,2):
        data.append(str(eval(operator) & 0x01))
cipher_text00 = Fernet(keyY_0).encrypt(Fernet(keyX_0).encrypt(data[0]))
cipher_text01 = Fernet(keyY_0).encrypt(Fernet(keyX_1).encrypt(data[1]))
cipher_text10 = Fernet(keyY_1).encrypt(Fernet(keyX_0).encrypt(data[2]))
cipher_text11 = Fernet(keyY_1).encrypt(Fernet(keyX_1).encrypt(data[3]))

Bob then passes the cipher_text values (cipher_text00 … cipher_text11) to Alice, and provides the key for his input. If he says YES, then he passes keyX_1, otherwise he will pass keyX_0.

Now Alice receives the four values, and Bob’s key. Now she uses obviously transfer to gain the key for her answer. If she says YES, we obtain the key for keyY_1, without Bob actually knowing that he says YES. If she says NO, she gets keyY_0.

In the end she will have two keys and she tries all the ciphers:

try:
    print Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text00))    
except:
    print ".",
try:
    print Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text01))    
except:
    print ".",
try:
    print Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text10))    
except:
    print ".",
try:
    print Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text11))    
except:
    print ".",

and the only one she can open is the one that matches Bob and Alice’s decision.

An example

To illustrate, let’s say that Bob and Alice say “No”, so their inputs to the AND function will be 0 and 0. Now Bob encrypts the four outputs with the four keys, but the only one which will open up the outputs will be the keys for a zero input for A and for B. Bob passes his key, without revealing his input as K(a=0), and Alice receives her key through an oblivious transfer:

Coding

The outline code is:

Conclusions

In the future we need to scramble data more, and those we trust can unscramble it, and those we don’t, only see noise.