In this method we can perform a logical function, such as X OR Y, and where Bob provides X and Alice provides Y, and she can determine the output, without knowing what Bob has supplied:
Scrambled Circuits - SFE With Oblivious Transfer |
Method
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.
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.
To illustrate, let's say that Bob and Alice say "No", so there 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 outine code is:
from cryptography.fernet import Fernet import sys import binascii operator = "a & b" x=0 y=0 operator=operator.replace('or','|') operator=operator.replace('and','&') operator=operator.replace('xor','^') operator=operator.replace('not','~') print("---Input parameters---") print("Operation:",operator) print("Input:",x,y) 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)) print("Outputs of function:",data) print("\n---Keys generated---") print("KeyX_0 (first 20 characters):",binascii.hexlify(bytearray(keyX_0))[:20]) print("KeyX_1 (first 20 characters):",binascii.hexlify(bytearray(keyX_1))[:20]) print("KeyY_0 (first 20 characters):",binascii.hexlify(bytearray(keyY_0))[:20]) print("KeyY_1 (first 20 characters):",binascii.hexlify(bytearray(keyY_1))[:20]) print("\n---Cipers send from Bob to Alice---") cipher_text00 = Fernet(keyY_0).encrypt(Fernet(keyX_0).encrypt(data[0].encode())) cipher_text01 = Fernet(keyY_0).encrypt(Fernet(keyX_1).encrypt(data[1].encode())) cipher_text10 = Fernet(keyY_1).encrypt(Fernet(keyX_0).encrypt(data[2].encode())) cipher_text11 = Fernet(keyY_1).encrypt(Fernet(keyX_1).encrypt(data[3].encode())) print("Cipher (first 20 chars): ",binascii.hexlify(bytearray(cipher_text00))[:40]) print("Cipher (first 20 chars): ",binascii.hexlify(bytearray(cipher_text01))[:40]) print("Cipher (first 20 chars): ",binascii.hexlify(bytearray(cipher_text10))[:40]) print("Cipher (first 20 chars): ",binascii.hexlify(bytearray(cipher_text11))[:40]) if (x==0): keyB = keyX_0 if (x==1): keyB = keyX_1 if (y==0): keyA = keyY_0 if (y==1): keyA = keyY_1 print("\n---Bob and Alice's key---") print("Bob's key: ",binascii.hexlify(bytearray(keyB))[:20]) print("Alice's key: ",binascii.hexlify(bytearray(keyA))[:20]) print("\n---Decrypt with keys (where '.' is an exception):") try: print(Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text00)), end=' ') except: print(".", end=' ') try: print(Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text01)), end=' ') except: print(".", end=' ') try: print(Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text10)), end=' ') except: print(".", end=' ') try: print(Fernet(keyB).decrypt(Fernet(keyA).decrypt(cipher_text11)), end=' ') except: print(".", end=' ')