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