Group Pointcheval-Sanders Signatures

Outline

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). Let's try an example with the signing two messages, and which are created with (\(\hat{x}\) and two random numbers for each of the messages (\(\hat{y_1}\) and \(\hat{y_2}\)):

\(sk = (\hat{x},\hat{y_1},\hat{y_2})\)

The public key is:

\(pk=(g_2,\hat{x} g_2,\hat{y_1} g_2,\hat{y_2} g_2))=(g_2,X,Y_1,Y_2) \)

To create the signature we take messages (\(m_1\) and \(m_2\)) 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_1} \times m_1+\hat{y_2} \times m_2 ) \times sig_1\)

In this case \(sig_1\) and \(sig_2\) will be points on G1, and \(X\), \(Y_1\) and \(Y_2\) are points on G2. To check the signature, we have (\(sig_1\), \(pk1\), \(pk2\) and \(sig_2)\) and then equate this pairing:

\(e(sig_1,X+m_1 Y_1 + m_2 Y_2)=e(sig_2,g_2)\)

Coding

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])
	}
	m1:=BN254.FromBytes(sh.Hash())

	msg=[]byte("Hello")

	sh=core.NewHASH256()
	for i:=0;i<len(msg);i++ {
		sh.Process(msg[i])
	}
	m2:=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
    	y1 := BN254.Randomnum(q,rng)
    	y2 := 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)
	Y1 := BN254.G2mul(G2,y1)
	Y2 := BN254.G2mul(G2,y2)
	e1 := BN254.Modmul(y1,m1,q); 
	e2 := BN254.Modmul(y2,m2,q);
	e := BN254.Modadd(e1,e2,q);
	e = BN254.Modadd(e,x,q) // (x+y1.m2 + y2.m2) mod q

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

	X.Add(BN254.G2mul(Y1,m1))
	X.Add(BN254.G2mul(Y2,m2))

	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(),y1.ToString())
        fmt.Printf("Random value (h):\th=%s\n\n",h.ToString())

        fmt.Printf("Public key:\ng2=%s\nX=%s\nY1=%s\nY2=%s\n\n",G2.ToString(),X.ToString(),Y1.ToString(),Y2.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 LHS.Equals(RHS) { fmt.Printf("\nSignatures match\n")}
}

A sample run is:

Message 1: hello
Message 2: hello123
Private key:	x=04581ca925de0ac1755a9ecbbd2e3458e679f76e4fc95909dc64b49374a7e838, y1=12789545bf0471f7ba7ac861c7d8faa7b602d14c7fb14090536c712be303603c, y2=11da259f13db654528f4915a1eed0b88039fafce0ac81a5e98f0d82178d0bc00
Random value (h):	h=1643f5d74597525a2fcab34c239ca418682778b3a4a7e1695894189bba71a7af

Public key:
g2=([061a10bb519eb62feb8d8c7e8c61edb6a4648bbb4898bf0d91ee4224c803fb2b,0516aaf9ba737833310aa78c5982aa5b1f4d746bae3784b70d8c34c1e7d54cf3],[021897a06baf93439a90e096698c822329bd0ae6bdbe09bd19f0e07891cd2b9a,0ebb2b0e7c8b15268f6d4456f5f38d37b09006ffd739c9578a2d1aec6b3ace9b])
X=([226822281f34acfaadb4d372925bb560773855562f01b44fca5193537d268120,2350ad555b4aa4c52a1d90e7c23155b9df6b79d9f81dd8d171cece922f732929],[0ba169763c19f2460e587d5f74870ceb82a30226a309203731041697a3da1991,150ad95aecb9d70592f76e54232205ef6c238a0c0623dec0da0ff5912d64a665])
Y1=([1c1c97cdf2dc0b6e4c055b352582accb105363d3d4913940fbe2663ffdf848f3,0b4d0aa6afcdab183feea20baf783b1eded566b1e3bc1c53e639d5064aca99c6],[1924f2a4966837b91c94dd420b475b29469b01bd675881e3e3373d8fda081f64,13beb94a2b49386c64188c782ea76b4b593ab1f0e4ad496ae65a4f888d5ae817])
Y2=([076ceaea2d6632f8437f2a7941f87130fb5d1663352de345935bef0b4646042b,077eb18e6d1ee331dcd31000549641300843a3eb49985691a543b0b00f91085a],[13cf1831a1dfd36b62b85be8d575c1f5046d39b56db8a8fd297f202f23c57005,0e3ec805da8998bd2636c05aaaa7032f9c445b97f4ceecbf0da39f7e17a664c7])

Sig1=(05e46ce11e438b45e04cdf743187f4300384b687a9a368c363c501e8165e8b84,08cc15c95a6937590aadb61cf860ebbefb53ce76132c858b35f660f58c7d883b)
Sig2=(1aedfd7aca817f6a0a55c41ab970a25d87df737b2d9ce381a23f35a5c7c735f4,24aebfa6426595718fd6dd62aa0d7785129ec7992e1c1f1d0d1bcfa2a7e974d8)

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

Signatures match

References

[1] David Pointcheval, Olivier Sanders: Short Randomizable Signatures. CT-RSA 2016: 111-126. The code on this page implements Section 4.1: [here]