Meet Comrade Bob and Comrade Alice: The Socialist Millionaire Who Don’t Trust Anyone!

Meet Comrade Bob and Comrade Alice: The Socialist Millionaires Who Don’t Trust Anyone!

A tale of two socialist millionaires

Two security socialists meet in a pub.

One is Comrade Bob and the other Comrade Alice.

Comrade Bob says:

“I have become wealthy due to all these data breaches, but I have the same fortune as you, Comrade Alice”.

“I, too, have become wealthy due to ransomware, but I believe that I have the same wealth as you, Comrade Bob”, says Comrade Alice.

“Then, how do we prove it?”, says Comrade Bob.

“Well, after working in security. I don’t trust anyone see to my wealth, and I especially do not trust you!”, says Comrade Alice.

“Well, I don’t trust you either, Comrade”, says Comrade Bob.

And so. Comrade Bob and Comrade Alice agree on a protocol to pass values, and in the end they can determine if they have the same value.

They agree on a prime number and a base for their discrete log method. Then Comrade Bob creates three random values, and so does Comrade Alice. In the end they pass two values to each other, and can compare.

“Yes, we have the same wealth”, say Comrade Alice.

“Yes, your are right!”, say Comrade Bob.

Social Millionaire Protocol

So, how did they do it? Well, they could use the Social Millionaire Protocol, and discrete logarithms to prove they either have the same wealth, or not, without any of them giving away their wealth. It is basically a zero knowledge proof, where we do not give anything away from the values passed.

With the socialist millionaire problem (SMP), we need to show that the two millionaire either have the same amount of money or not. First the two millionaires (Bob and Ailce), create public values of p,h and where p is a prime number and h is the base of the discrete logarithm operation. The prime number is used to create a finite field, and where each of the operations are done (mod p).

Alice then creates a message (x) and three random values: a,α,r.

Bob then creates a message (y) and three random values: b,β,s.

Bob and Alice now have to prove the x and y are the same, without revealing their values.

Alice sends Bob, h^a and Bob sends Alice h^b. They then use the Diffie-Hellman method to create a shared value of:

g=h^{ab}

Alice sends Bob, h^α and Bob sends Alice h^β. They then use the Diffie-Hellman method to create a shared value of:

γ=hαβ

Next Alice creates and sends Bob these values:

P_a=γ^r

and:

Q_a=h^r g^x

Bob creates and send Alices these values:

P_b=γ^s

and:

Q_b=h^s g^y

They then use the Diffie-Hellman method to come up with:

c=(Q_aQ_b^{-1})^{αβ}

and also:

c′=Pa Pb^{-1}

They then test if c=c′ . If they are, the values that Bob and Alice have are the same. This works because:

Here is the demo:

Conclusions

We give away too much of our data, and where we should just be proving things. For your password, why don’t we just store some form of random number on