Linkable Ring Signatures with GoA ring signature is a digital signature that is created by a member of a group that each have their own keys. With this it will not be possible to determine the person in the group who has created the signature. They were initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001. We will generate a number of public keys, but only one key pair of the signer. The signer users the public keys of the others in the ring, but apply their private key, in order to sign for all the entities in the ring. No one will be able to tell which of the private keys has been used. We will also apply a linkage message, so that someone could pick up that it was our signature. |
Details
And so there has been a leak of information at the White House. Donald Trump calls in his Cyber Security leads, and tells them, "I know one of you leaked the information, but I can't tell which one". How can Donald tell that one of his chief leaked the information, but not know which one? Well this can be achieved with a ring signature, and which provides anonymity, unforgivably and collusion resistance.
A ring signature is a digital signature that is created by a member of a group which each have their own keys. It is then not be possible to determine the person in the group who has created the signature. The method was initially created by Ron Rivest, Adi Shamir, and Yael Tauman in 2001, and who proposed the White house leak dilemma.
In a ring signature we define a group of entities who each have public/private key pairs of (P1, S1), (P2, S2), …, (Pn, Sn). If we want entity \(i\) to sign a message (\(message\)), they use their own secret key (\(s_i\)) but the public keys of the others in the group (\(m,s_i,P_1 … P_n\)). It should then be possible to check the validity of the group by knowing the public key of the group, but not possible to determine a valid signature if there is no knowledge of the private keys within the group.
So let's say that Trent, Bob, Eve and Alice are in a group, and they each have their own public key and secret key. Bob now wants to sign a message from the group. He initially generates a random value \(v\), and then generates random values (\(s_i\)) for each of the other participants, but takes his own secret key (\(s_i\) and uses it to determine a different secret key, and which reverse of the encryption function. He next takes the message and takes a hash of it, and thus creates a key (\(k\)). This key will be used with symmetric encryption to encrypt each of the elements of the ring (\(E_k\), and each element of the ring uses an EX-OR function from the previous element (Figure 1). Each of the random values for the other participants are then encrypted with the public key of the given participant. Bob then computes the value of \(y_s\) in order to create the ring (the result of the ring must equal v). He will then inverse this value to produce the equivalent private key (xs). Bob now releases the overall signature, and the random x values, along with the computed secret key. To check the signature, the receive just computes the ring, and checks that the result matches the sent signature.
The basic method are:
1. Generate encryption with \(k=\text{Hash}(message)\).
2. Generate a random value (\(u\)).
3. Encrypt \(u\) to give \(v=E_k(u)\).
4. For each person (apart from the sender):
- 4.1 Calculate \(e=s_i^{P_i} \pmod{N_i}\) and where \(s_i\) is the random number generated for the secret key of the \(i\)th party, and \(P_i\) is the public key of the party.
- 4.2 Calculate \(v= v \oplus e\)
5. For the signed party (\(z\)), calculate \( s_z={(v \oplus u)}^d \pmod {N_z}\) and where \(d\) is the secret key of the signing party.
We will end up with the signature (\(v=E_k(u)\)), and which completes the ring.
A linkable ring signature allows one person in the group to sign on behalf of the group, but has the addition of a tag so that an external verifier can know that the signature has been produced by a defined signer, but where they cannot tell who the signer is. The linkable ring signature method is used within the Monero cryptocurrency and defined by the Ring Confidential Transaction (RingCT).
In the case below, Bob adds a tag to the signature, and where Victor, if he knew the tag could see that it was Bob who signed for it. Victor and Bob use a stealth address (more information is defined here), which allows Victor to determine the privacy key for the public key that Bob has used to sign onto the ring. The smart contract then just matches the signatures of this private key, and will sign from the ring to Victor’s new address.
Presentation
The following is an outline presentation [slides]:
Coding
The following defines some code [taken from here]:
package main import ( "strconv" "os" "fmt" "encoding/hex" "go.dedis.ch/kyber/v3" "go.dedis.ch/kyber/v3/group/edwards25519" "go.dedis.ch/kyber/v3/sign/anon" ) func main() { m:="Hello" scope :="My Link" n:=4 argCount := len(os.Args[1:]) if (argCount>0) {m= string(os.Args[1])} if (argCount>1) {n,_= strconv.Atoi(os.Args[2])} if (argCount>2) {scope= string(os.Args[3])} S := []byte(scope) // scope for linkage tags M := []byte(m) suite := edwards25519.NewBlakeSHA256Ed25519() rand := suite.RandomStream() // Create an anonymity set of random "public keys" X := make([]kyber.Point, n) for i := range X { // pick random points X[i] = suite.Point().Pick(rand) } fmt.Printf("Message: %s\nLinkable address: %s\n\n",M,S) fmt.Printf("Public keys: %s\n\n",X) // Make two actual public/private keypairs (X[mine],x) mine1 := 1 // only the signer knows this mine2 := 2 x1 := suite.Scalar().Pick(rand) // create a private key x x2 := suite.Scalar().Pick(rand) X[mine1] = suite.Point().Mul(x1, nil) // corresponding public key X X[mine2] = suite.Point().Mul(x2, nil) fmt.Printf("Private key of signer: %s\n\n",x1) fmt.Printf("Public key of signer: %s\n\n",X[1]) // Generate two signatures using x1 and two using x2 var sig [4][]byte sig[0] = anon.Sign(suite, M, anon.Set(X), S, mine1, x1) sig[1] = anon.Sign(suite, M, anon.Set(X), S, mine1, x1) sig[2] = anon.Sign(suite, M, anon.Set(X), S, mine2, x2) sig[3] = anon.Sign(suite, M, anon.Set(X), S, mine2, x2) for i := range sig { fmt.Printf("Signature %d:\n%s", i, hex.Dump(sig[i])) } // Verify the signatures against the correct message var tag [4][]byte for i := range sig { goodtag, err := anon.Verify(suite, M, anon.Set(X), S, sig[i]) if err != nil { panic(err.Error()) } tag[i] = goodtag if tag[i] == nil || len(tag[i]) != suite.PointLen() { panic("Verify returned invalid tag") } fmt.Printf("Sig%d tag: %s\n", i, hex.EncodeToString(tag[i])) } }
A sample run is give below. The first two signatures are signed by the main signer:
Message: Testing 123 Linkable address: Bill Link Public keys: [77b9dfd5c322dacb5f3dc1db7c36180082bf136c4bafb3e43be35f60c38f6706 771bc6f4e6746bc4717ded897f1f5400ab30a0e4747e8fd16c4ed5d22c117eba 3562643ee167258346412eaa4bfdfdeda21327dcf3301243bce3876d453f9ebd 49bdb0f94969988a7289f49fdaf39a1129fa3c3d0dc0f3cb7d958c9fb33155b1] Private key of signer: edc7878a45071d19559932b0ea9b495474f40bfa734dc451aaeffbc3c1260904 Public key of signer: 387b1d3a244c8842458b64fd7723c73e8db53e65028c3fea2a0467601a650170 Signature 0 (first 30 hex): 8373b73cc1cd72121d561c3b7c699f2eee615ae10d11bb6a56315e738389 Signature 1 (first 30 hex): 8f0357d38adfe3761f3cbe9ba0dc86f51d6ea671eba03856edc8e505f0fe Signature 2 (first 30 hex): 7199afa0b9115bfcc5ba729c6dfb8848c3678639f5b65a9780f4cd736948 Signature 3 (first 30 hex): c3901fbcb2fc92bceb0218f688df142ce14c73ecf69cfbe99d462a444ab3 Sig0 tag: 8fd2bee76761ed17515a3ad2311aeb5b6c183f7babb5cd3b2ce34a19e68174e1 Sig1 tag: 8fd2bee76761ed17515a3ad2311aeb5b6c183f7babb5cd3b2ce34a19e68174e1 Sig2 tag: 3551ad8a5cf20b5e1558eec57b6a8b326d5e139175b12e56dda2d035ba55edb7 Sig3 tag: 3551ad8a5cf20b5e1558eec57b6a8b326d5e139175b12e56dda2d035ba55edb7