Bob and Alice Become Socialists

Bob and Alice Become Socialists

And, so, Bob and Alice have made millions in cybersecurity, but have decided that they now want to be equal in their wealth — they have become millionaire socialists. But, one thing that Bob and Alice have learned in their time in cybersecurity, is that they can’t trust anyone. So, how can Bob and Alice check that they have the same money, without actually telling each other what their wealth is?

Well, this is based Yao’s Millionaire’s Problem, and where we can determine which of two millionaires has the most money, without them actually giving away the amount of money they have. But, in a socialist millionaire problem, we want to show that they have the same wealth.

Previously, I implemented this with discrete logs [1]:

https://asecuritysite.com/zero/go_smp

So, now let’s try this with elliptic curve methods. With the socialist millionaire problem (SMP), we need to show that the two millionaires either have the same amount of money or not. First, the two millionaires (Bob and Alice) agree on a base point H.

Alice has a wealth of x and creates three random values: a, α, and r.

Bob has a wealth of y and creates three random values: b, β, and s.

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

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

g=ab.H

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:

Pa=r.γ

and:

Qa=r.H+x.G

Bob creates and sends Alice these values:

Pb=s.γ

and:

Qb=s.H+y.G

They can pass Qa, Qb, Pa and Pb, and then use the Diffie-Hellman method to come up with:

c=αβ.(Qa−Qb)

They can then compute:

c′=Pa−Pb

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

Pa−Pb=r.γ−s.γ=(r−s).γ=αβ.(r−s).H

Therefore:

c=α.β(Qa−Qb)=α.β(r.H+x.G−s.H−y.G)=αβ((r−s).H+(x−y).G)=α.β((r−s).H+ab(x−y).H)=αβ(r−s).H+αβab(x−y).H=(Pa−Pb)+αβab(x−y).H

And thus if x=y, we get:

Pa−Pb

Coding

The following provides the code [here]:

package main
import (
 "crypto/rand"
 "fmt"
 "os"
 "strconv"
 "github.com/coinbase/kryptology/pkg/core/curves"
)
func main() {
 xval := 5
 yval := 5
 curve := curves.K256()
 H := curve.Point.Generator()
 argCount := len(os.Args[1:])
 if argCount > 0 {
  xval, _ = strconv.Atoi(os.Args[1])
 }
 if argCount > 1 {
  yval, _ = strconv.Atoi(os.Args[2])
 }
 x := curve.Scalar.New(xval)
 y := curve.Scalar.New(yval)
 r := curve.Scalar.Random(rand.Reader)
 s := curve.Scalar.Random(rand.Reader)
 a := curve.Scalar.Random(rand.Reader)
 b := curve.Scalar.Random(rand.Reader)
 alpha := curve.Scalar.Random(rand.Reader)
 beta := curve.Scalar.Random(rand.Reader)
 G := H.Mul(a.Mul(b))
 Gamma := H.Mul(alpha.Mul(beta))
 Pa := Gamma.Mul(r)
 Pb := Gamma.Mul(s)
 Qa := H.Mul(r).Add(G.Mul(x))
 Qb := H.Mul(s).Add(G.Mul(y))
 c := Qa.Sub(Qb).Mul(alpha.Mul(beta))
 c_ := Pa.Sub(Pb)
 fmt.Printf("c=%x\n", c.ToAffineCompressed())
 fmt.Printf("c_=%x\n", c_.ToAffineCompressed())
 if c.Equal(c_) {
  fmt.Printf("Bob and Alice have the same money")
 } else {
  fmt.Printf("Bob and Alice do not have same money")
 }
}

And a sample run [here]:

Bob x=1000000
Alice y=1000000
c=02376df93f9359cf77fae0f09c00a61c3989abe91a01c02b3efd7f36819b4212e3
c_=02376df93f9359cf77fae0f09c00a61c3989abe91a01c02b3efd7f36819b4212e3
Bob and Alice have the same money

and [here]:

Bob x=1000001
Alice y=1000000
c=0223d6cb339e2ddbb59a3f08a211fc3ba76695b36010372be2c884cee3a454d626
c_=021659f52a449eebc139e09c2e59124659d7021a9d4ba360d17f1be410a353b19b
Bob and Alice do not have same money

Here’s the code:

https://asecuritysite.com/zero/go_smp2

Conclusions

There are many areas in computing where we need to determine if two things are the same — such as your previous and current location — with revealing something that is private. This brings in whole area of zero-knowledge proofs:

https://asecuritysite.com/zero

Reference

[1] Boudot, Fabrice, Berry Schoenmakers, and Jacques Traore. “A fair and efficient solution to the socialist millionaires’ problem.” Discrete Applied Mathematics 111.1–2 (2001): 23–36 [here]