Overall, with ECDSA, Alice signs the hash of a message (h(M)) with her private key (\(sk\)), and Bob checks it with her public key (\(Pk\)). With a blinded signature, Bob can sign for a message, without knowning what the message is. In this case Alice will create a blinded ECDSA signature, and where Bob can then sign it, and then Alice can unblind it. The method is based on one produced by Oleg Andreev [here] for blinding signatures in Bitcoin.
Blinding ECDSA signatures |
Theory
With ECDA, Alice produces a private key (\(sk\) and a public key (\(Pk\)):
\(Pk=sk.G\)
We then take a hash of a message:
\(h=H(M)\)
Alice then creates a random value of \(k\), and produces:
\(r=k.G \pmod n\)
and where \(r\) is the x co-ordinate value of \(k.G \pmod n\). The \(s\) value is then:
\(s=k^{−1}(h+r.Pk) \pmod n\)
When Bob checks the signature, he computes:
\(u_1=h.s^{-1} \pmod n\)
and:
\(u_2=r.s^{-1} \pmod n\)
Bob then computes a point at:
\(Z=u_1.G + u_2.Pk\)
If the value of x co-ordinate of \(Z\) is equal to \(r\), the signature checks out.
In this case, \(n\) is the order of the curve.
Blinded signature
Overall, with ECDSA, Alice signs the hash of a message (h(M)) with her private key (\(sk\)), and Bob checks it with her public key (\(Pk\)). With a blinded signature, Bob can sign for a message, without knowning what the message is. In this case Alice will create a blinded ECDSA signature, and where Bob can then sign it, and then Alice can unblind it. The method is based on one produced by Oleg Andreev for blinding signatures in Bitcoin. First Alice produces four random values of \(a\), \(b\), \(c\) and \(d\), and Bob produces two random values of \(p\) and \(q\) and then computes:
\(P = p^{-1}.G\)
and:
\(Q = q.p^{-1}.G\)
and where \(G\) is the base point on the curve. Bob sends these to Alice. Next, Alice computes:
\(K = (c.a)^{-1} .P\)
and public key of:
\(T = (a.K_x)^{-1} .(b.G + Q + d.c^{-1} .P)\)
Alice computes hash of message (\(M\)):
\(h=H(M)\)
Alice then blinds with:
\(h_2 = a.h + b \pmod n\)
and send this to Bob. Bob signs the blinded hash and returns with:
\(s_1 = p.h_2 + q \pmod n\)
Alice unblinds signature:
\(s_2 = c.s_1 + d \pmod n\)
The signature is now \(r=K_x\), \(s=s_2\). In this case, \(n\) is the order of the curve.
The proof is here:
Coding
The coding is here [here]:
package main import ( "crypto/ecdsa" "crypto/elliptic" "crypto/rand" "crypto/sha256" "fmt" "math/big" "os" "strconv" ) // Derived from Oleg Andreev // Blind signatures for Bitcoin transactions func main() { type Alice struct { m *big.Int a, b, c, d *big.Int } type Bob struct { p, q *big.Int } bits := 16 argCount := len(os.Args[1:]) if argCount > 0 { bits, _ = strconv.Atoi(os.Args[1]) } Curve := elliptic.P256() n := Curve.Params().N alice, bob := Alice{m: getRandom(n)}, Bob{} // Alice select random primes alice.a, alice.b, alice.c, alice.d = getRandomPrime(bits), getRandomPrime(bits), getRandomPrime(bits), getRandomPrime(bits) tmp, x, y := new(big.Int), new(big.Int), new(big.Int) // 2. Bob computes P = (p^-1 .G) and Q = (q.p^-1 .G) bob.p, bob.q = getRandomPrime(bits), getRandomPrime(bits) Px, Py := Curve.ScalarBaseMult(new(big.Int).ModInverse(bob.p, n).Bytes()) Qx, Qy := Curve.ScalarBaseMult(new(big.Int).Mul(bob.q, new(big.Int).ModInverse(bob.p, n)).Bytes()) // 3. Alice computes K = (c.a)^-1 .P and public key T = (a.Kx)^-1 .(b.G + Q + d.c^-1 .P). tmp = new(big.Int) Kx, _ := Curve.ScalarMult(Px, Py, tmp.Mul(alice.c, alice.a).ModInverse(tmp, n).Bytes()) Tx, Ty := Curve.ScalarBaseMult(alice.b.Bytes()) Tx, Ty = Curve.Add(Tx, Ty, Qx, Qy) x, y = Curve.ScalarMult(Px, Py, new(big.Int).Mul(alice.d, new(big.Int).ModInverse(alice.c, n)).Bytes()) Tx, Ty = Curve.Add(Tx, Ty, x, y) tmp = new(big.Int) Tx, Ty = Curve.ScalarMult(Tx, Ty, tmp.Mul(alice.a, Kx).ModInverse(tmp, n).Bytes()) // 4. Alice computes hash of message h := hashToInt(hash(alice.m.Bytes()), Curve) // 5. Alice blinds with h_2 = a.h + b (mod n) and sends to Bob tmp = new(big.Int) h2 := tmp.Mul(alice.a, h).Add(tmp, alice.b).Mod(tmp, n) // 6. Bob signs blinded hash and returns s_1 = p.h_2 + q (mod n). tmp = new(big.Int) s1 := tmp.Mul(bob.p, h2).Add(tmp, bob.q).Mod(tmp, n) // 7. Alice unblinds signature: s_2 = c.s_1 + d (mod n) tmp = new(big.Int) s2 := tmp.Mul(alice.c, s1).Add(tmp, alice.d).Mod(tmp, n) // 8. The signature is now r=Kx, s=s_2 fmt.Printf("m=%s\n\n", alice.m) fmt.Printf("a=%s\nb=%s\nc=%s\nd=%s\n", alice.a, alice.b, alice.c, alice.d) fmt.Printf("Public Key Tx=%s\nTy=%s\n", Tx, Ty) fmt.Printf("Hash h=%s\n\n", h) fmt.Printf("\nBlinded Signature r=%s, s=%s\n", Kx, s1) fmt.Printf("Signature r=%s, s=%s\n", Kx, s2) fmt.Println("Signature verified: ", ecdsa.Verify(&ecdsa.PublicKey{Curve: Curve, X: Tx, Y: Ty}, h.Bytes(), Kx, s2)) } func getRandom(n *big.Int) *big.Int { m, _ := rand.Int(rand.Reader, n) return m } func getRandomPrime(bits int) *big.Int { m, _ := rand.Prime(rand.Reader, bits) return m } func hash(msg []byte) []byte { hasher := sha256.New() hasher.Write(msg) return hasher.Sum(nil) } func hashToInt(hash []byte, c elliptic.Curve) *big.Int { orderBits := c.Params().N.BitLen() orderBytes := (orderBits + 7) / 8 if len(hash) > orderBytes { hash = hash[:orderBytes] } ret := new(big.Int).SetBytes(hash) excess := len(hash)*8 - orderBits if excess > 0 { ret.Rsh(ret, uint(excess)) } return ret }
A sample run is:
m=46398016479029616968153310998590589859317634753915956549813904092937392557159 a=3303670661 b=3226384361 c=3530828149 d=3607703383 Public Key Tx=75232732142229191477159812086310547165062017290843364912683578530970424703230 Ty=73950523097040244239776555774732425845079447152113985190585097252768983601069 Hash h=53060989786633559228535141356889483919385714906876242047763586659314070909566 Blinded Signature r=94046861866238546923597525972649788516701559058765278594626970725249113708126, s=103442503972324084972377390983720274585365710753545239530321864819095340728763 Signature r=94046861866238546923597525972649788516701559058765278594626970725249113708126, s=35825078730317479356116975137038450525621519055620748195720062041695485378112 Signature verified: true