Abe, Okhubo and Suzki (AOS) ring signatures are used in confidental transactions, and where we can hide the signer of a transaction. The method has been used to integrate into the Borromean Ring Signature method, and was published as "1-out-of-n signatures from a variety of keys" [1]. It has since been expanded by Maxwell [2] with multiple rings and which creates the Borromean ring signature methods, and which has then been used by Monero to create a privacy-preserving cryptrocurrency [3].
Abe, Okhubo and Suzki (AOS) ring signatures |
Theory
It was Ron Rivest who first defined a method for creating a ring signature, 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:
We initially have a number of public keys for n partipants: [\(P_0, P_1, ... P_{n-1}\)]. With this there is an associated private key of \(x_i\) for a public key of:
\(P_i = x_i.G\)
and where \(G\) is the base point on the curve. We then have a message of \(M\) and have a participant \(j\), initially select a random value of \(\alpha\) to get:
\(Q=\alpha.G\)
and then:
\(e_{j+1}=H(Q || M)\)
and where "||" is a concatenation of the byte values. At \(j+1\), we select a random value of \(s_i\) and then let:
\(e_{i+1}=H(s_i.G+s_i.P_i || M)\)
Finally, we complete the ring with:
\(s_j=\alpha - e_jx_j\)
This is achieved using the Schnorr signature approach. The signature is then:
\( \sigma = (e_0, s_0, s_1 ... s_{n_1})\)
This is illustrated in Figure 1 [4].
Figure 1: [4]
Practical example
The theory section may have been a little difficult to follow, so let's break it down into steps for three participants (\(N=3\)). First, we create the key pairs of {\(P_0, P_1, P_2\)} and where we will sign with \(x_2\) and where:
\(P_2 = x_2.G\)
The code for this is then:
// 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() }
So let \( \alpha \) equal to a random value, and:
\(e_0 = H(\alpha.G || M) \)
The code to compute \(Q=\alpha.G\) is then:
alpha, _ := rand.Int(rand.Reader, curve.N) Qx, Qy := curve.ScalarBaseMult(alpha.Bytes())
Next we can hash the message (and all of the public keys) with:
Parr := []*btcec.PublicKey{} for i := range pub { Parr = append(Parr, pub[i]) } M := HashMsgVerificationKey([]byte(msg), Parr)
The value of \(e_1\) is then created with:
\(e_1 = H(\alpha.G || M)\)
This can be coded with:
e := make([]*big.Int, N) e[1] = HashBigInt( []*big.Int{ M, Qx, Qy, }, )
Now we select a random value \(s_0\) and compute:
\(e_1=H(s_0.G + e_0.P_0 || M) \)
This can be achieved with [5]:
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[0] = HashBigInt( []*big.Int{ M, sumx, sumy, }, )
Next we select a random value \(s_1\) and compute:
\(e_2=H(s_1.G + e_1.P_1 || M) \)
This can be achieved with [5]:
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[1] = HashBigInt( []*big.Int{ M, sumx, sumy, }, )
Finally, to complete the ring, we compute with the private key of participant 1 (\(x_1\)):
\(s_2=\alpha- e_2.x_2\)
This is implemented as:
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)
and we should have completed the ring.
Verification
The signature is then:
\( \sigma = (e_0, s_0, s_1 ... s_{n_1})\)
The verifier now computes:
\(e_1 = H(s_0.G + e_0.P_0|| M) \)
\(e_2 = H(s_1.G + e_1.P_1 || M) \)
\(e'_0 = H(s_2.G + e_2.P_2 || M) \)
and then checks:
\(e'_0 = e_0 \)
Proof
This works because:
\(e_0=H(s_2.G+e_2.P_2 || M)\)
and where:
\(s_2=\alpha - e_2.x_2\)
And so:
\(e_0=H( (\alpha-e_2.x).G + e_2.P || M) \)
Thus:
\(e_0= H(\alpha.G - e_2.x_2.G + e_2.P_2 || M) = H(\alpha.G - e_2.P_2+ e_2.P_2 || M) = H(\alpha.G || M)\)
This is illustrated as:
Coding
The coding is [5]:
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!!!") } }
A sample run is:
Message=Hello e[2]=63654016903249411012303649920469463006138687211019865082155716856050232921888 e[0]=26302213551057003222608573543787744695110919031953547029702649636253204670271 e[1]=68997527827376829165644562694489787475916230339423968316646679158127858638263 s[0]=114648186897421511854486873774394865580491178505478529924136211954212449292567 s[1]=91895294096620934283941049881346625911739049453005969823054756922952285688798 s[2]=18883104233748514607788066489644147200962604662396668107588378604112601386008 === Now let's check by computing e[2] === e'=63654016903249411012303649920469463006138687211019865082155716856050232921888 We have completed the ring!!!
The method is defined with:
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] Maxwell, G., and Poelstra, A. (2015). Borromean ring signatures. Accessed: Jun, 8, 2019.
[3] Ren, Y., Zhao, Q., Guan, H., & Lin, Z. (2020). On design of single-layer and multilayer code-based linkable ring signatures. IEEE Access, 8, 17854–17862.
[4] https://ventral.digital/posts/2023/10/17/cryptocurrency-privacy-technologies-borromean-ring-signatures/
[5] https://github.com/blockchain-research/crypto/tree/master/brs