Socialist Millionaire Problem with Go (and ECC)With the socialist millionaire problem (SMP) - aka as the Off-the-Record Messaging protocol - we need to show that two millionaires either have the same amount of money or not, and without revealing their own value. In this case we will use the method defined by Boudot et al [1]. The implementation uses the Kryptology library and the secp256k1 curve (as used in Bitcoin and Ethereum). |
Theory
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) create public values of \(H\), and which is a point on an elliptic curve.
Alice has a wealth of (\(x\)) and three random values: \(a,\alpha ,r\).
Bob thas a wealth of (\(y\)) and three random values: \(b,\beta ,s\).
Bob and Alice now have to prove the \(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, \({\alpha}.H\) and Bob sends Alice \({\beta}.H\). They then use the Elliptic Curve Diffie-Hellman (ECDH) method to create a shared value of:
\(\gamma = {\alpha\beta}.H\)
Next Alice creates and sends Bob these values:
\(P_a=r.\gamma\)
and:
\(Q_a=r.H + x.G\)
Bob creates and sends Alice these values:
\(P_b=s.\gamma\)
and:
\(Q_b=s.H + y.G\)
They can pass \(Q_a\), \(Q_b\), \(P_a\) and \(P_b\), and then use the ECDH method to come up with:
\(c={\alpha \beta }.(Q_{a}-Q_{b})\)
The can then compute:
\(c'=P_a-P_b\)
They then test if \(c=c'\). If they are equal, the values that Bob and Alice have are the same.
This works because:
\(\begin{aligned} P_{a}-P_{b} &=r.\gamma - s.\gamma =(r-s).\gamma\\ &={\alpha \beta .(r-s)}.H \end{aligned}\)
Therefore:
\( \begin{aligned} c&={\alpha . \beta. } \left(Q_{a}-Q_{b}\right) \\ &={\alpha . \beta .}\left(r.H+x.G-s.H-y.G\right)\\ &={\alpha \beta .}\left((r-s).H+(x-y).G\right)\\ &={\alpha \beta .}\left((r-s).H+ab.(x-y).H\right)\\ &={\alpha \beta. (r-s)}.H+ {\alpha \beta . ab.(x-y)}.H\\ &=\left(P_{a}-P_{b} \right)+{\alpha \beta ab.(x-y).H} \end{aligned} \)
And thus if \(x=y\), we get:
\(P_a-P_b\)
Coding
The following provides the code:
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("Bob x=%d\n", xval) fmt.Printf("Alice y=%d\n", yval) fmt.Printf("\n=== Bob generates\n") fmt.Printf("a=%x\n", a.Bytes()) fmt.Printf("alpha=%x\n", alpha.Bytes()) fmt.Printf("r=%x\n", r.Bytes()) fmt.Printf("\n=== Alice generates\n") fmt.Printf("b=%x\n", b.Bytes()) fmt.Printf("beta=%x\n", beta.Bytes()) fmt.Printf("s=%x\n", s.Bytes()) fmt.Printf("\nc=%x\n", c.ToAffineCompressed()) fmt.Printf("c_=%x\n", c_.ToAffineCompressed()) if c.Equal(c_) { fmt.Printf("\nBob and Alice have the same money") } else { fmt.Printf("\nBob and Alice do not have same money") } }
And a sample run:
Bob x=9999999 Alice y=1000000 === Alice generates a=fdc3bc2ff790060ae1f3115eb0abe27650eaf815fe49fd77ad0bdd4f25021f0a alpha=3b37714c791b0f12ed0311d2ee98cd8b9404ef69c34cd6134c3cb0f0ee6d30cd r=8ab88fa3aa1034fdff1d6d64eba7244aea37b986e2f041ae68908966070855f6 === Bob generates b=90698416660298406ef2fcaed72f0fa7f84975f65a42b3ffd94800b95527942d beta=5a2b3fbd6890ace587fe6b69307514c40b1ec0d91d5e92cc65636491e5573aa9 s=0b8536b90e9f1183db49398fc80b6154a2cd6a2b68eed0bd82ffc1f677b3273c c=02396a21af775fc41f5f76e6b664f03c82443b69e28711bedbe727fe8a857e6bcc c_=0243caaada0493dae686e444aa672cc534ad9be1e6784773f16ada6f1e05c4588b Bob and Alice do not have same money
and:
Bob x=1000000 Alice y=1000000 === Alice generates a=6cc78bb2193962cab8d824a4372a9f3ea8accb6694cadbc169d8fc6cda51df97 alpha=372a4e9792e0fb6bebeeda2d6a7467701ff2de6f6324ed9c8c3e9b5d0c2bf60f r=4471eff89a7765722134d28f4fe908ef0a63f22b26024522a7420c1319305e85 === Bob generates b=17553ba22f924781ecaf325d9681e0c11a40dfae60c363ee860b87033eab60e3 beta=0d0022a408f30f45b36f9032153c53a29fa9823c25c2e61539485d3a1f82d558 s=5b22fbd1b59bd950fd0576616206a8fce8875e148585c9ea498e5b369e745bd6 c=021b74d3a9a8efc2a3a7d9a2a3056ceec80cd25972ba54bb47208f8dd86e4a455c c_=021b74d3a9a8efc2a3a7d9a2a3056ceec80cd25972ba54bb47208f8dd86e4a455c Bob and Alice have the same money
References
[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].