Cryptography Is Beautiful — and Powerful in Protecting Privacy

Cryptography Is Beautiful — and Powerful in Protecting Privacy

I’ve been working on the theory of ring signatures, and I think the way that they work with elliptic curves is just beautiful. It was Ron Rivest who first defined a method for creating a ring signature [2], and where we could use the public keys of Bob, Alice and Wendy were involved in a signature, but Trent could not determine which one of them had signed a message:

In this case, Alice has used the public keys of herself, Wendy and Bob, and then her own private key to sign the message to Trent, but Trent cannot tell if it was Alice, Wendy or Bob who signed the message. Trent, too, will know that one of them did sign it, though. This is a ring signature, and where we can still define the trust level on the signature, but preserve the anonymity of the signer.

Overall, the method defined by Ron Rivest uses the RSA public key method and is a bit cumbersome. But, the rise of elliptic curve methods saw a beautifully crafted method from Abe, Okhubo and Suzki (AOS), and which produced an elegant solution for elliptic curve methods [1]:

This method allowed Alice to collect public keys from the others in the ring, and then add her own private key to the signature. The technique has since advanced into the Moreno cryptocurrency, and which preserves the privacy of the sender and receiver of a transaction.

So, let me explain the method, and let’s say that Alice is the signer, and has a public key of P_2 and a private key of x_2:

In ECC:

P_2= x_2.G

and where G is the base point of the curve. Initially Alice generates a random number (α), and computes:

e_0 = Hash (α.G || M)

and where M is the message to sign. Next, she generates another random value (s_0) and takes Bob’s public key (P_0) to create:

e_1 = Hash (s_0.G+e_0.P_0 || M)

Next, she generates another random value (s_0) and takes Wendy’s public key (P_1) to create:

e_2 = Hash (s_1.G+e_1.P_1 || M)

Finally, she needs to close the ring. She does this by computing:

s_2 = α — e_2.x_2

The value of e_0 will then be the same as the original e_0, as:

e_0 = Hash (s_2.G+e_2.P_2 || M) = Hash ((α — e_2.x_2).G+e_2.P_2 || M) = Hash ((α .G— e_2.P_2+e_2.P_2 || M) = Hash ((α .G || M)

Isn’t the just magical?

The coding for this is here:

package main

import (
 "crypto/rand"
 "crypto/sha256"
 "fmt"
 "math/big"
 "os"

 "github.com/btcsuite/btcd/btcec"
)

func HashBigInt(a []*big.Int) *big.Int {
 digest := sha256.New()
 for i := range a {
  digest.Write(a[i].Bytes())
 }

 output := digest.Sum(nil)
 tmp := output[0:len(output)]
 return new(big.Int).SetBytes(tmp)
}
func HashMsgVerificationKey(msg []byte, keys []*btcec.PublicKey) *big.Int {
 a := []*big.Int{}
 for i := range keys {
  a = append(a, keys[i].X)
  a = append(a, keys[i].Y)
 }
 return HashMsg(msg, a)
}
func HashMsg(msg []byte, a []*big.Int) *big.Int {
 digest := sha256.New()
 digest.Write(msg)
 for i := range a {
  digest.Write(a[i].Bytes())
 }

 output := digest.Sum(nil)
 tmp := output[0:len(output)]
 return new(big.Int).SetBytes(tmp)
}
func main() {
 curve := btcec.S256()

 msg := "Hello"
 argCount := len(os.Args[1:])
 if argCount > 0 {
  msg = os.Args[1]
 }

 N := 3 /// Three participants
 fmt.Printf("Message=%s\n\n", msg)

 // Make key pairs
 priv := make([]*btcec.PrivateKey, N)
 pub := make([]*btcec.PublicKey, N)

 for i := 0; i < N; i++ {
  priv[i], _ = btcec.NewPrivateKey(curve)

  pub[i] = priv[i].PubKey()
 }

 alpha, _ := rand.Int(rand.Reader, curve.N)
 Qx, Qy := curve.ScalarBaseMult(alpha.Bytes())

 Parr := []*btcec.PublicKey{}
 for i := range pub {

  Parr = append(Parr, pub[i])

 }

 M := HashMsgVerificationKey([]byte(msg), Parr)

 e := make([]*big.Int, N)

 e[0] = HashBigInt(
  []*big.Int{
   M,
   Qx,
   Qy,
  },
 )
 fmt.Printf("e[%d]=%s\n", 0, e[0])

 s := make([]*big.Int, N)

 s[0], _ = rand.Int(rand.Reader, curve.N)

 sGx, sGy := curve.ScalarBaseMult(s[0].Bytes())
 ePx, ePy := curve.ScalarMult(pub[0].X, pub[0].Y, e[0].Bytes())
 sumx, sumy := curve.Add(sGx, sGy, ePx, ePy)

 e[1] = HashBigInt(
  []*big.Int{
   M,
   sumx,
   sumy,
  },
 )
 fmt.Printf("e[%d]=%s\n", 1, e[1])

 s[1], _ = rand.Int(rand.Reader, curve.N)

 sGx, sGy = curve.ScalarBaseMult(s[1].Bytes())
 ePx, ePy = curve.ScalarMult(pub[1].X, pub[1].Y, e[1].Bytes())
 sumx, sumy = curve.Add(sGx, sGy, ePx, ePy)

 e[2] = HashBigInt(
  []*big.Int{
   M,
   sumx,
   sumy,
  },
 )
 fmt.Printf("e[%d]=%s\n", 2, e[2])

 s[2] = new(big.Int).Sub(alpha, new(big.Int).Mul(e[2], priv[2].D))
 s[2] = new(big.Int).Mod(s[2], curve.N)

 fmt.Printf("\ns[%d]=%s\n", 0, s[0])
 fmt.Printf("s[%d]=%s\n", 1, s[1])
 fmt.Printf("s[%d]=%s\n", 2, s[2])

 fmt.Printf("\n=== Now let's check by computing e[0] ===\n")
 sGx, sGy = curve.ScalarBaseMult(s[2].Bytes())
 ePx, ePy = curve.ScalarMult(pub[2].X, pub[2].Y, e[2].Bytes())
 sumx, sumy = curve.Add(sGx, sGy, ePx, ePy)

 edash := HashBigInt(
  []*big.Int{
   M,
   sumx,
   sumy,
  },
 )

 fmt.Printf("e'=%s\n", edash)
 if edash.Cmp(e[0]) == 0 {
  fmt.Printf("We have completed the ring!!!")
 }

}

and you can try it here:

https://asecuritysite.com/bulletproof/aos

Reference

[1] Abe, M., Ohkubo, M., & Suzuki, K. (2002, November). 1-out-of-n signatures from a variety of keys. In International conference on the theory and application of cryptology and information security (pp. 415–432). Berlin, Heidelberg: Springer Berlin Heidelberg.

[2] Rivest, R. L., Shamir, A., & Tauman, Y. (2001, December). How to leak a secret. In International conference on the theory and application of cryptology and information security (pp. 552–565). Springer, Berlin, Heidelberg.