In this case we will convert:
\(e(X,a) \cdot {e(X,b)}^m \cdot {e(X,B)}^r =e(g_1,c)\)
into:
\(e(X,a) \cdot {e(X,b)}^m \cdot {e(X,B)}^r \cdot e(g_1,-c)=1\)
Camenisch-Lysyanskaya Signatures in Go
[Pairing 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 convert: \(e(X,a) \cdot {e(X,b)}^m \cdot {e(X,B)}^r =e(g_1,c)\) into: \(e(X,a) \cdot {e(X,b)}^m \cdot {e(X,B)}^r \cdot e(g_1,-c)=1\) |
The CL Signature was defined in [1] and the theory in the paper uses discrete log notations. So we will first outline the basics of this. First we have prime number \(q\) and a generator value \(g_1\). For message of \((m,r)\) we have a private key of three random numbers (\(x\), \(y\) and \(z\)):
\(sk = (x,y,z )\)
The public key is then created from:
\(X = g_1^x\)
\(Y = g_1^y\)
\(Z = g_1^z\)
The public key is then:
\(pk = (q,g_1,X,Y,Z)\)
To create a signature we select \(a\) (\(g_2\)) 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(g_1,A)\)
\(e(a,Y)=e(g_1,b)\)
\(e(A,Y)=e(g_1,B)\)
\(e(X,a) \cdot {e(X,b)}^m \cdot {e(X,B)}^r =e(g_1,c)\)
into:
\(e(X,a)\cdot {e(X,b)}^m \cdot {e(X,B)}^r \cdot e(g_1,-c)=1\)
The CL Signature was defined in [1], and an improved implementation uses elliptic curve methods. First we have prime number \(q\) and a generator point \(G_1\) on the G1 curve. For message of \((m,r)\) we have a private key of three random numbers (\(x\), \(y\) and \(z\)):
\(sk = (x,y,z )\)
The public key is then created from:
\(X = xG_1\)
\(Y = yG_1\)
\(Z = zG_1\)
The public key is then:
\(pk = (q,g_1,X,Y,Z)\)
To create a signature we select a point on the G2 curve \(G_2\) and calculate:
\(A=zG_2\)
\(b=yG_2\)
\(B=yA\)
\(c=(x+xym+xyrz) G_2 \)
The signature is then:
\((a,A,b,B,c)\)
To verify we check the following pairings:
1. \(e(a,Z)=e(A,G_1)\)
2. \(e(a,Y)=e(b,G_1)\)
3. \(e(A,Y)=e(B,G_1)\)
4. \(e(X,a) \cdot {e(X,b)}^m \cdot {e(X,B)}^r =e(G_1,c)\)
into:
\(e(X,a) \cdot {e(X,b)}^m \cdot {e(X,B)}^r \cdot e(G_1,-c)=1\)
The core properties are:
\(e(aU,bV)=e(abU,V)=e(U,abV)={e(U,V)}^{ab}\)
Thus 1. \(e(a,Z)=e(\alpha G_2,z G_1) = e(\alpha z G_2, G_1)= e(A,G_1)\)
Thus 2. \(e(a,Y)=e(\alpha G_2,y G_1) = e(\alpha y G_2, G_1)=e(b,G_1)\)
Thus 3. \(e(A,Y)=e(\alpha z G_2,y G_1) = e(\alpha yz G_2, G_1)=e(B,G_1)\)
The following is the code:
package main import "fmt" import "github.com/miracl/core/go/core" import "github.com/miracl/core/go/core/BN254" import "os" import "math/rand" import "time" func FP12toByte(F *BN254.FP12) []byte { const MFS int = int(BN254.MODBYTES) var t [12 * MFS]byte F.ToBytes(t[:]) return(t[:]) } func randval() *core.RAND { s1 := rand.NewSource(time.Now().UnixNano()) r1 := rand.New(s1) rng := core.NewRAND() var raw [100]byte for i := 0; i < 100; i++ { raw[i] = byte(r1.Intn(255)) } rng.Seed(100, raw[:]) return rng } 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:=BN254.FromBytes(sh.Hash()) // p := BN254.NewBIGints(BN254.Modulus) q := BN254.NewBIGints(BN254.CURVE_Order) x := BN254.Randomnum(q,randval()) y := BN254.Randomnum(q,randval()) z := BN254.Randomnum(q,randval()) r := BN254.Randomnum(q,randval()) alpha := BN254.Randomnum(q,randval()) G1:= BN254.ECP_generator() // Generator point in G1 X := BN254.G1mul(G1,x) Y := BN254.G1mul(G1,y) Z := BN254.G1mul(G1,z) G2:= BN254.ECP2_generator() // Generator point in G2 a := BN254.G2mul(G2,alpha) b := BN254.G2mul(a,y) A := BN254.G2mul(a,z) B := BN254.G2mul(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.G2mul(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(a,Z); LHS=BN254.Fexp(LHS) RHS:=BN254.Ate(A,G1); 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: e(a,Z)=e(A,G1)\n\n")} LHS=BN254.Ate(a,Y); LHS=BN254.Fexp(LHS) RHS=BN254.Ate(b,G1); 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: e(a,Y)=e(b,G1)\n\n")} LHS=BN254.Ate(A,Y); LHS=BN254.Fexp(LHS) RHS=BN254.Ate(B,G1); 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: e(A,Y)=e(B,G1)\n\n")} // e(a,X). e(b,X)^m . e(B,X)^r=e(g,c) // e(a,X). e(b,X)^m . e(B,X)^r . e(-c,g) = 1 c.Neg() RHS=BN254.Ate(c,G1); RHS=BN254.Fexp(RHS) RHS1:=BN254.Ate(a,X); RHS1=BN254.Fexp(RHS1) RHS2:=BN254.Ate(b,X); RHS2=BN254.Fexp(RHS2); RHS3:=BN254.Ate(B,X); RHS3=BN254.Fexp(RHS3); RHS2=RHS2.Pow(m); RHS3=RHS3.Pow(r); RHS.Mul(RHS2) RHS.Mul(RHS3) RHS.Mul(RHS1) fmt.Printf("Pair 2 - first 20 bytes:\t0x%x\n",FP12toByte(RHS)[:20]) if (RHS.Isunity()) { fmt.Printf("\nPairing match: e(X, a). e(X, b)^m . e(X, B)^r e(g, -c)=1\n\n")} }
A sample run is:
Message: hello Private key: x=2264e47650edc73fa6ce40b098823b542c5b594f2b4b6fd8731fd4fbd6b04432, y=1de9d79ab78eac666637e35369ae7310e44e2c96fffe6896d37ebe89412636ba, z=0eae82a0710a302dfd215c1a16314fe57bcd0918121b26f7eff5fa4a343cb0fd Pair 1 - first 20 bytes: 0x20c0b5943d4729d5ea03069a171f91fe60539293 Pair 2 - first 20 bytes: 0x20c0b5943d4729d5ea03069a171f91fe60539293 Pairing match: e(a,Z)=e(A,G1) Pair 1 - first 20 bytes: 0x21397cc083958170b46f06cf57455044af42d00a Pair 2 - first 20 bytes: 0x21397cc083958170b46f06cf57455044af42d00a Pairing match: e(a,Y)=e(b,G1) Pair 1 - first 20 bytes: 0x12ea7b40cfe08c5286df733a63c8299f64c5519e Pair 2 - first 20 bytes: 0x12ea7b40cfe08c5286df733a63c8299f64c5519e Pairing match: e(A,Y)=e(B,G1) Pair 2 - first 20 bytes: 0x0000000000000000000000000000000000000000 Pairing match: e(X, a). e(X, b)^m . e(X, B)^r e(g, -c)=1
[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]