CL MIRACL Magic!

CL MIRACL Magic!

Here is the demos related to this article [link] and here is the magic update that Michael Scott outlined to me [link].

One of the most privileged things in academia is being able to collaborate with some amazing researchers, and who are so helpful and open to sharing ideas. And so we are lucky to have meetings with the mighty Jan Camenisch:

and to collaborate with Dr Michael Scott (the “S” in BLS signatures). The collaboration with Michael has allowed us access to the MIRACL pairing library, and which has opened-up so many doors for us. Our end game is to develop attributes of credentials — such as your date of birth or your age — which can be verified. One of the core methods for this is the CL (Camenisch-Lysyanskaya) signature [here]:

So armed with Golang (“respect the Gopher”), and the paper, let’s implement the theory here:

This is defined in a discrete log manner, but these days we typically implement using elliptic curve methods (as it is so much more efficient).

The CL Signature was defined in [1]. First we have prime number q and a generator value g1. For message of (m,r) we have a private key of three random numbers (x, y and z) [here]:

sk=(x,y,z)

The public key is then created from:

X=g^x1

Y=g^y1

Z=g^z1

The public key is then:

pk=(q,g1,X,Y,Z)

To create a signature we select a (g2) and calculate:

A=a^z

b=a^y

B=A^y

c=a^{x+xym}A^{xyr}

The signature is then:

(a,A,b,B,c)

To verify we check the following pairings:

e(a,Z)=e(g1,A)

e(a,Y)=e(g1,b)

e(X,a)e(X,b)me(X,B)r=e(g1,c)

The following is the code [here]:

package main

import "fmt"

import "github.com/miracl/core/go/core"
import "github.com/miracl/core/go/core/BN254"
import "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() {
    rng := core.NewRAND()
    var raw [100]byte
    for i := 0; i < 100; i++ {
    raw[i] = byte(i + 1)
    }
    rng.Seed(100, raw[:])

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

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

    	x := BN254.Randomnum(q,rng)
    	y := BN254.Randomnum(q,rng)
    	z := BN254.Randomnum(q,rng)
    	r := BN254.Randomnum(q,rng)
   	alpha := BN254.Randomnum(q,rng)

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

    	X := BN254.G2mul(G2,x)
	Y := BN254.G2mul(G2,y)
	Z := BN254.G2mul(G2,z)

    	G1:= BN254.ECP_generator() // Generator point in G1

	a := BN254.G1mul(G1,alpha)
	b := BN254.G1mul(a,y)

	A := BN254.G1mul(a,z)
	B := BN254.G1mul(A,y)

	// c=a^{x+xym} A^{xyr} = a^{x+xym} a^{xyrz} = a^{x+xym+xyrz}
	e1 := BN254.Modmul(x,y,q); e1 = BN254.Modmul(e1,m,q);  e1 = BN254.Modadd(e1,x,q) // (x+xym) mod q
	e2 := BN254.Modmul(x,y,q); e2 = BN254.Modmul(e2,r,q);  e2 = BN254.Modmul(e2,z,q) // (xyrz) mod q

	e:= BN254.Modadd(e1,e2,q)

	c:= BN254.G1mul(a,e) 

	fmt.Printf("Message: %s\n",mymsg);

        fmt.Printf("Private key:\tx=%s, y=%s, z=%s\n\n",x.ToString(),y.ToString(),z.ToString())

	LHS:=BN254.Ate(Z,a);  LHS=BN254.Fexp(LHS)
	RHS:=BN254.Ate(G2,A); RHS=BN254.Fexp(RHS)

        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("\nPairing match\n")}

	LHS=BN254.Ate(Y,a);  LHS=BN254.Fexp(LHS)
	RHS=BN254.Ate(G2,b); RHS=BN254.Fexp(RHS)

        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("\nPairing match\n")}

	LHS=BN254.Ate(Y,A);  LHS=BN254.Fexp(LHS)
	RHS=BN254.Ate(G2,B); RHS=BN254.Fexp(RHS)

        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("\nPairing match\n")}

//	e(X, a). e(X, b)^m . e(X, B)^r=e(g, c)

	LHS=BN254.Ate(G2,c);  LHS=BN254.Fexp(LHS)
	RHS=BN254.Ate(X,a); RHS=BN254.Fexp(RHS)
	RHS2:=BN254.Ate(X,b); RHS2=BN254.Fexp(RHS2); 
	RHS3:=BN254.Ate(X,B); RHS3=BN254.Fexp(RHS3);  

 	RHS2=RHS2.Pow(m);
 	RHS3=RHS3.Pow(r);
	RHS.Mul(RHS2)
	RHS.Mul(RHS3)

        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("\nPairing match\n")}

}

A sample run is:

Message: hello
Private key:	x=04581ca925de0ac1755a9ecbbd2e3458e679f76e4fc95909dc64b49374a7e838, y=12789545bf0471f7ba7ac861c7d8faa7b602d14c7fb14090536c712be303603c, z=11da259f13db654528f4915a1eed0b88039fafce0ac81a5e98f0d82178d0bc00

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

Pairing match: e(Z,a)=e(G2,A)
Pair 1 - first 20 bytes:	0x1d78eb507d1cb352d57292b3eb9097380c0767c8
Pair 2 - first 20 bytes:	0x1d78eb507d1cb352d57292b3eb9097380c0767c8

Pairing match: e(Y,a)=e(G2,b)
Pair 1 - first 20 bytes:	0x242fd6748536bb36d6ffa45b77ee3f6c2ad10977
Pair 2 - first 20 bytes:	0x242fd6748536bb36d6ffa45b77ee3f6c2ad10977

Pairing match: e(Y,A)=e(G2,B)
Pair 1 - first 20 bytes:	0x0245a19c6b99575503bbc528f47d7f62915b3630
Pair 2 - first 20 bytes:	0x0245a19c6b99575503bbc528f47d7f62915b3630

Pairing match: e(X, a). e(X, b)^m . e(X, B)^r=e(g, c)

Conclusions

Our dream is to create signed versions of your attributes, such as for your date of birth or your age, and be able to verify these. CL signatures give us the power to do that.

References

[1] Camenisch, J., & Lysyanskaya, A. (2004, August). Signature schemes and anonymous credentials from bilinear maps. In Annual International Cryptology Conference (pp. 56–72). Springer, Berlin, Heidelberg. The code on this page implements Section 3.2: [here]