Randomizing Your Signatures

Randomizing Your Signatures

Wouldn’t it be great if you could randomize your wet signature, so that every time you signed, or whenever anyone looked at your signature, it would change? Well, let’s implement a method that allows us to do this.

Let’s say that I sign a message that you receive. You check the signature of the message and store it, and the signature. But, I want to preserve your privacy by storing the signature, so that no-one can trace it back to the original message? Well for this we can used a randomized method of creating signatures.

One of the best methods around is the PS (Pointcheval Sanders) Short Randomizable Signature and was defined in [1][here]:

It uses crypto pairs to produce a signature which can be randomized. Initially we have two pairing points (g1 on the G1 curve, and g2 on the G2 curve. The private key is created with two random numbers (x and y):

sk=(x ,y)

and a public key with:

pk=(g2,x g2,y g2)=(g2,X,Y)

To create the signature we take a message (m) and create a random value for the signature (h) and then determine two signature elements:

sig1=h g1

sig2=(x+y×m)×sig1

In this case sig1 and sig2 will be points on G1, and X and Y are points on G2. To check the signature, we have (sig1, pk and sig2) and then equate this pairing:

e(sig1,X+m×Y)=e(sig2,g2)

This works because of the magic of crypto pairing:

e(sig1,X+m×Y)=e(h×g1,x×g2+m×yg2)=

e(h×g1,(x+m×y)×g2)=e(h×((x+m×y))×g1,g2)=

e(sig2,g1)

To randomize the signature, we just multiply sig2 and sig1 (and which are points on G1) by a random number and can get a new signature, such as:

sig3 = r sig1

sig4 = r sig2

There is no need to reveal the random value (r), and the signature will still check-out. In this case, we create a random value (r) and multiple each of the signature points (sig1 and sig2) and then check that the signatures check out [here]:

package main
package main

import "fmt"

import "github.com/miracl/core/go/core"
import "github.com/miracl/core/go/core/BN254"

func FP12toByte(F *BN254.FP12) []byte {

	const MFS int = int(BN254.MODBYTES)
	var t [12 * MFS]byte

	F.ToBytes(t[:])
	return(t[:])
}

func main() {
    rng := core.NewRAND()
    var raw [100]byte
    for i := 0; i < 100; i++ {
    raw[i] = byte(i + 1)
    }
    rng.Seed(100, raw[:])


	mymsg:="hello"
	msg:=[]byte(mymsg)

	sh:=core.NewHASH256()
	for i:=0;i<len(msg);i++ {
		sh.Process(msg[i])
	}
	m:=BN254.FromBytes(sh.Hash())


    	p := BN254.NewBIGints(BN254.Modulus)
    	q := BN254.NewBIGints(BN254.CURVE_Order)

    	x := BN254.Randomnum(q,rng) // Generate a random number less than q
    	y := BN254.Randomnum(q,rng)

    	G2:= BN254.ECP2_generator() // Generator point in G2

    	h := BN254.Randomnum(p,rng) // Create random point on curve
    	H := BN254.ECP_hashit(h) 


    	X := BN254.G2mul(G2,x)
	Y := BN254.G2mul(G2,y)
	e := BN254.Modmul(y,m,q); e = BN254.Modadd(e,x,q) // (x+y.m) mod q

	sig1 := BN254.NewECP(); sig1.Copy(H)
	sig2 := BN254.G1mul(H,e)

	X.Add(BN254.G2mul(Y,m))

	LHS:=BN254.Ate(X,sig1);  LHS=BN254.Fexp(LHS)
	RHS:=BN254.Ate(G2,sig2); RHS=BN254.Fexp(RHS)
	fmt.Printf("Message: %s\n",mymsg);

        fmt.Printf("Private key:\tx=%s, y=%s\n",x.ToString(),y.ToString())
        fmt.Printf("Random value (h):\th=%s\n\n",h.ToString())

        fmt.Printf("Public key:\ng2=%s\nX=%s\nY=%s\n\n",G2.ToString(),X.ToString(),Y.ToString())

        fmt.Printf("Sig1=%s\nSig2=%s\n\n",sig1.ToString(),sig2.ToString())
        fmt.Printf("Pair 1 - first 20 bytes:\t0x%x\n",FP12toByte(LHS)[:20])
        fmt.Printf("Pair 2 - first 20 bytes:\t0x%x\n",FP12toByte(RHS)[:20])

	if RHS.Equals(RHS) { fmt.Printf("\nSignatures match\n")}


	r := BN254.Randomnum(q,rng)


	sig1=BN254.G1mul(sig1,r) 
	sig2=BN254.G1mul(sig2,r)

	LHS=BN254.Ate(X,sig1);  LHS=BN254.Fexp(LHS)
	RHS=BN254.Ate(G2,sig2); RHS=BN254.Fexp(RHS)

	fmt.Printf("\nRandom value: %s\n\n",r.ToString());

        fmt.Printf("Pair 1 - first 20 bytes:\t0x%x\n",FP12toByte(LHS)[:20])
        fmt.Printf("Pair 2 - first 20 bytes:\t0x%x\n",FP12toByte(RHS)[:20])

        if RHS.Equals(LHS) { fmt.Printf("\nSignatures match\n")}
}

A sample run with simple values is [here]:

Message: hello
Private key:	x=04581ca925de0ac1755a9ecbbd2e3458e679f76e4fc95909dc64b49374a7e838, y=12789545bf0471f7ba7ac861c7d8faa7b602d14c7fb14090536c712be303603c
Random value (h):	h=080f0b6dd08ea3f6bbf8a591214522addc6350403b1a02e8706d9832d54cda5c

Public key:
g2=([061a10bb519eb62feb8d8c7e8c61edb6a4648bbb4898bf0d91ee4224c803fb2b,0516aaf9ba737833310aa78c5982aa5b1f4d746bae3784b70d8c34c1e7d54cf3],[021897a06baf93439a90e096698c822329bd0ae6bdbe09bd19f0e07891cd2b9a,0ebb2b0e7c8b15268f6d4456f5f38d37b09006ffd739c9578a2d1aec6b3ace9b])
X=([17dd7736cd104a27546f6c8a6194a017c7ccca01ce332abeed8379399f756399,1d731bb3418a3b78ce6455f3b63aeff3bf81890e05d58122a0415135713f0b43],[0f1fd9e19f9d1aade3fb69f3c27e7965e7a7f4e651f2a706510991adb1ffaa3c,1547615f173f2c3827beaec4ebfd41e87cc839e13fa5742dbb836926238f1843])
Y=([1c1c97cdf2dc0b6e4c055b352582accb105363d3d4913940fbe2663ffdf848f3,0b4d0aa6afcdab183feea20baf783b1eded566b1e3bc1c53e639d5064aca99c6],[1924f2a4966837b91c94dd420b475b29469b01bd675881e3e3373d8fda081f64,13beb94a2b49386c64188c782ea76b4b593ab1f0e4ad496ae65a4f888d5ae817])

Sig1=(0d6d3b74ef97ac9c479097f6ef340aebe716d28010dd99808509117f26bfe69c,242644573e1369f9efa2aa170378fabcf4a2801c45ac1ddafa2a66fdba65099c)
Sig2=(2296b2fd99de4e48d19c0b2401dd2d29e1dcdeca0b9d7b0ad60068e453d84128,1e9e3caf77418992bb74f40a6e0d8833bf8d8e9c3a880fb29f7b578405bd654a)

Pair 1 - first 20 bytes:	0x0622c23255e2a4a414ede134387926ef0ac4e3a7
Pair 2 - first 20 bytes:	0x0622c23255e2a4a414ede134387926ef0ac4e3a7

Signatures match

Random value: 233d93f587b9de94d94284295260d5c4f1c6815dbf9f7a3d42fa3d0afa37ade9

Pair 1 - first 20 bytes:	0x034bfce0427547136332876b396e5f3fd1f93fb9
Pair 2 - first 20 bytes:	0x034bfce0427547136332876b396e5f3fd1f93fb9
Signatures match

Conclusions

PS signatures are a great step forward, and can be randomized by any entity. While we put a random value into the creation of the signature, as you can see, we can also randomize it and still produce a valid signature. If you are interested, here is the maths behind the code above:

References

[1] David Pointcheval, Olivier Sanders: Short Randomizable Signatures. CT-RSA 2016: 111–126