\(e(aU,V) =e(U,aV)\)
In this case we will match \(e((X+M \times Y) V,h U) = e(V,(x+y \times m)h U) \), and where \(x\) and \(y\) are secret values.
Pointcheval-Sanders Signatures
[MIRACL Home][Home]
With pairing-based cryptography we have two cyclic groups (\(G_1\) and \(G_2\)), and which are of an order of a prime number (\(n\)). A pairing on \((G_1,G_2,G_T)\) defines the function \(e:G_1 \times G_2 \rightarrow G_T\), and where \(g_1\) is a generator for \(G_1\) and \(g_2\) is a generator for \(G_2\). If we have the points of \(U_1\) and \(U_2\) on \(G_1\) and \(V_1\) and \(V_2\) on \(G_2\), we get the bilinear mapping of:
\(e(aU,V) =e(U,aV)\) In this case we will match \(e((X+M \times Y) V,h U) = e(V,(x+y \times m)h U) \), and where \(x\) and \(y\) are secret values. |
The PS (Pointcheval Sanders) Short Randomizable Signature was defined in [1], and uses crypto pairs to produce a signature which can be randomized. Initially we have two pairing points (\(g_1\) on the G1 curve, and \(g_2\) on the G2 curve). The private key is created with two random numbers (\(\hat{x}\) and \(\hat{y}\)):
\(sk = (\hat{x},\hat{y})\)
and a public key with:
\( pk=(g_2,\hat{x} g_2,\hat{y} g_2)=(g_2,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:
\(sig_1 = h g_1\)
\(sig_2= (\hat{x}+\hat{y} \times m) \times sig_1\)
In this case \(sig_1\) and \(sig_2\) will be points on G1, and \(X\) and \(Y\) are points on G2. To check the signature, we have (\(sig_1\), \(pk\) and \(sig_2)\) and then equate this pairing:
\(e(sig_1,X+mY)=e(sig_2,g_2)\)
This works because of the magic of crypto pairing:
\(e(sig_1,X+mY) = e(h \times g_1 ,\hat{x} g_2+m \hat{y} g_2) = e(h g_1 ,(\hat{x} +m \hat{y}) g_2) =e(h ((\hat{x} +m \hat{y})) g_1 , g_2) = e(sig_2,g_1) \)
To randomize the signature, we just multiply \(sig_2\) and \(sig_1\) (and which are points on G1) by a random number (\(r\)) and can get a new signature, such as:
\(sig_3 = r \times sig_1\)
\(sig_4 = r \times sig_2\)
There is no need to reveal the random value (\(r\)), and the signature will still check-out.
The following is the code:
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(LHS) { fmt.Printf("\nSignatures match\n")} }
A sample run is:
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
[1] David Pointcheval, Olivier Sanders: Short Randomizable Signatures. CT-RSA 2016: 111-126. The code on this page implements Section 4.1: [here]