PS Signatures with MIRACL

PS Signatures with MIRACL: Randomizable and Short

We just love the magic of crypto pairing, and the opportunity to produce short and randomizable signatures. A signature can then be change in order to hide the original signature.

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

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.

And, as if by magic we can easily prove the signature. We are currently working with the MIRACL library, so here is an implement of this [here]:

package main

import (
 "fmt"
     "math/rand"
 "time"
 "github.com/miracl/core/go/core/BN254"
 "github.com/miracl/core/go/core"
 "os"

)

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

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

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

func main() {

 mymsg:="Hello"

 argCount := len(os.Args[1:])

       if (argCount>0) {mymsg= (os.Args[1])}

 msg:=[]byte(mymsg)

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

 rand.Seed(time.Now().UnixNano())

 x:= rand.Intn(4294967296)
 y:= rand.Intn(4294967296)
 h:= rand.Intn(4294967296)

 g1 := BN254.ECP_generator()
 g2:= BN254.ECP2_generator()

 
 g:=g2
 X:=BN254.G2mul(g2,BN254.NewBIGint(x)) 
 Y:=BN254.G2mul(g2,BN254.NewBIGint(y)) 

 sig1:=BN254.G1mul(g1,BN254.NewBIGint(h))

 // (x+y*m)*h
 z1:=BN254.G1mul(sig1,BN254.NewBIGint(x)) // xh
 z2:=BN254.G1mul(sig1,BN254.FromBytes(m)) // m*h
 z2=BN254.G1mul(z2,BN254.NewBIGint(y)) // y*m*h
 z1.Add(z2) // (x+y*m)*h
 sig2:=z1

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

 k1 := BN254.Ate(X,sig1) 
 k1 = BN254.Fexp(k1)

 // e(X+M*Y g2,h g1) = e(g2,(x+y*m)h g1) 
 k2 := BN254.Ate(g,sig2) 
 k2 = BN254.Fexp(k2)

 fmt.Printf("m=%s\nHash=%x\n\n",mymsg,m)

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

 fmt.Printf("Public key:\tX=%s\nY=%s\n\n",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(k1)[:20])
 fmt.Printf("Pair 2 - first 20 bytes:\t0x%x\n",FP12toByte(k2)[:20])
 
 if k1.Equals(k2) { fmt.Printf("\nSignatures match")}
}

A sample run with simple values is [here]:

m=hello
Hash=2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
Private key: x=920104504, y=782500753
Random value (h): h=3803832919
Public key: X=([02bc018d7d2f089761d4a9dec8555a941d64b3455289fedd8c20076da6933124,15f0e9cc0182f19eab5b2fd251a92efd4938405d213909741d1aaabaca940ee4],[163c0de0de255e41489e00f4d3cfc781ea68711483d840cc652760a4b99a8cb3,251c48924c0ec9f51a325e5c8300b9664dbf25fde9a964f9621d1794ebccdb83])
Y=([006d423287934b915fec94c31c0fb46f3c422093d351de7b223090d8200b8573,114854ff6b92106023b3980fd0dfe4158b2f19b57b0ed00ba2716f683a16f55c],[0fb4ea51caab7d7cb96d479aaf949aa333bcc95fd5e2d0f27e5833778b719354,1b009b9762a3d7e923b7e0c5484ccc4a1ac1ddd37d855549d11b19329e30068c])
Sig1=(0a157521fd28646277799ad7040694bdca687f207a5ad5d17ee1f8c30dd3e5ec,19fcf52dcabe62d45e3b408a44f91fa5469b547e4da2e75975987ea4ce1e3195)
Sig2=(00c502c089a65ea3a418da468aafd8fa263e81fea90bf60163d0e4718029e0f2,063b457e1b09cfad47b413b16136f0d159d4d72fa254a46acdb6c2388fe08edd)
Pair 1 - first 20 bytes: 0x237de26551d7a283a37a7f4653b0664d48c18a3d
Pair 2 - first 20 bytes: 0x237de26551d7a283a37a7f4653b0664d48c18a3d
Signatures match

Conclusions

The PS signatures are a great step forward, and can be randomized by any entity.

References

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