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)\).
Camenisch-Lysyanskaya Signatures in Go |
Outline (Discrete Logs)
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\)
Outline (Elliptic Curve)
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 \(\alpha G_2\) and calculate:
\(a=\alpha G_2\)
\(A=za\)
\(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)\)
Proof
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)\)
Thus 4. \(e(a,X) \cdot {e(b,X)}^m \cdot {e(B,X)}^r =\)
\(e(\alpha G_2,x G_1) \cdot {e(y G_2,x G1)}^m \cdot {e(\alpha yz G_2,x G_1)}^r =\)
\(e(\alpha x G_2, G_1) \cdot e(\alpha ymx G_2, G1) \cdot e(\alpha ryzx G_2, G_1) =\)
\(e( x a, G_1) \cdot e(ymx a, G1) \cdot e(ryzx a, 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(c,g) LHS=BN254.Ate(c,G1); LHS=BN254.Fexp(LHS) RHS=BN254.Ate(a,X); RHS=BN254.Fexp(RHS) 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) 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,X). e(b,X)^m . e(B,X)^r=e(c,g)\n\n")} }
A sample run is:
Message: hello Private key: x=225b5cd6ed49008d68877bf81ff0024e8b301cd049c25ae00a027cc73fee8cd7, y=0b56d9dcb427a6ce95c3f6ea06c4712d3c096f5ad5a42a53b855ffb5cc93b1c6, z=1ae55bb979d630a6df96f7246ad7504b76729dbbd677d6ae4222742c99e79c35 Pair 1 - first 20 bytes: 0x178a3a7e20ba29ee84fb55f1794be3e1e141c6ad Pair 2 - first 20 bytes: 0x178a3a7e20ba29ee84fb55f1794be3e1e141c6ad Pairing match: e(a,Z)=e(A,G1) Pair 1 - first 20 bytes: 0x03ace8687a8753f09df2aef09a1848fc10bed528 Pair 2 - first 20 bytes: 0x03ace8687a8753f09df2aef09a1848fc10bed528 Pairing match: e(a,Y)=e(b,G1) Pair 1 - first 20 bytes: 0x1e6281db5bc4e900ecfb5bf453431c96f8bca087 Pair 2 - first 20 bytes: 0x1e6281db5bc4e900ecfb5bf453431c96f8bca087 Pairing match: e(A,Y)=e(B,G1) Pair 1 - first 20 bytes: 0x228a5e0aa905606f67b2351abacf8d8633a422ef Pair 2 - first 20 bytes: 0x228a5e0aa905606f67b2351abacf8d8633a422ef Pairing match: e(X, a). e(X, b)^m . e(X, B)^r=e(g, c)
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]