The Millionaire’s Problem In A World Where Bob and Alice Trust No-one

Circuits, bits and secret processing

Bob and Alice are now millionaires, and they want to find out who has more money, but don’t want to tell each other how much they are worth. This is defined as the Millionaire’s Problem, and we can solve it using encrypted cipher values and then feeding this into a circuit and getting a result for Greater than, Equal to, and Less than.

The problem can be achieved by zero-knowledge proof, but let’s look at homomorphic encryption to solve the problem. For this we will use the method defined by DGHV (Dijk, Gentry, Halevi and Vaikuntanathan) [paper] and which is a fully homomorphic encryption scheme [1].

First we get a random number (p) and two random numbers (q and r), and then encrypt a single bit (m) with:

c=p×q+2×r+m

In this case p will be our secret key.

If 2r is smaller than p/2, we cipher with mod p we get:

d=(c mod p)mod 2

We have basically added noise to the value with the q and r values.

Try example here.

Every logical function can be created with add (XOR) and multiply (AND). In this case we will take four values for the number of…