The Miracl(e) of Crypto Pairing

I love receiving a new crypto library, and diving in to discover its hidden secrets. The latest one is MIRACL, and where we are…

The Miracl(e) of Crypto Pairing

I love receiving a new crypto library, and diving in to discover its hidden secrets. The latest one is MIRACL [here], and where we are collaborating with Professor Michael Scott, and who is one of the founding fathers of crypto pairs. As we share a passion for crypto pairing too, it is an easy collaboration for us. If you are interested, here is one of Michael’s recent papers [here]:

For us, too, it is a great industry/academia collaboration, and is especially useful as the library comes with many different languages. While our reseachers are looking at Rust implementations, I am keen on Go, as it matches well to C code, and can be compiled into an executable form.

And so one of the most amazing things about crypo pairing is that you can merge public keys into a single public key (W), and can also merge all the generated signatures from a message into a single signature (SIG). For this you might have a hundred public keys used, and would then have 100 signatures, and where each signature was signed by one of the 100 signers. This becomes a significant overhead in storing and processing the signatures.

But with crypto pairing, we can merge the public keys of (W1…W100) with:

W = W1 + W2 + W3 + … W100

and then take the private keys of the signers (S1 … S100) and create 100 signtures (SIG1 … SIG100). The merged signature is then:

SIG= SIG1 + SIG2 + SIG100

We can then test the merged public key with the signature, and can verify that each of the public keys signed the message. Overall, a compressed public key and signature takes up just 33 bytes of space.

In crypto pairing we have two curves (G1 and G2), and where our signature adds points on the G1 curve, and the public key on the G2 curve. And so, I grabbed some crypto pairing code from Miracl, and wrote a small test program which merges two public keys and two signatures, and then proves them [here]. For the merging of the public keys we add points on the G2 curve:

func addW(W1 []byte, W2 []byte, W [] byte) (int)  {	
        P := BN254.ECP2_fromBytes(W1)
	Q := BN254.ECP2_fromBytes(W2)
	P.Add(Q)
	P.ToBytes(W[:],true)
	return 0}

For the merging of the signatures, we add the points on the G1 curve:

func addS(S1 []byte, S2 []byte, S [] byte) (int)  {	
        P := BN254.ECP_fromBytes(S1)
	Q := BN254.ECP_fromBytes(S2)
	P.Add(Q) 
	P.ToBytes(S[:],true)
	return 0}

The overall code is [here]:

package main

import "fmt"
import "os"
import "github.com/miracl/core/go/core"
import "github.com/miracl/core/go/core/BN254"

func printBinary(array []byte)(s string)  {
        s= "" 
	for i := 0; i < len(array); i++ {
	s = s+ fmt.Sprintf("%02x", array[i])
		
	}
	
	return
}
func addW(W1 []byte, W2 []byte, W [] byte) (int)  {

	P := BN254.ECP2_fromBytes(W1)
	Q := BN254.ECP2_fromBytes(W2)
	P.Add(Q)
	P.ToBytes(W[:],true)
	return 0

}
func addS(S1 []byte, S2 []byte, S [] byte) (int)  {

	P := BN254.ECP_fromBytes(S1)
	Q := BN254.ECP_fromBytes(S2)
	P.Add(Q) 
	P.ToBytes(S[:],true)
	return 0

func salt(rng *core.RAND)(IKM [32]byte) {

	for i:=0;i&li;32;i++ {

	        IKM[i]=byte(rng.GetByte())
	}
	return
	
}

func Core_Verify1(SIG []byte, M []byte, W []byte) int {
	HM := BN254.Bls_hash_to_point(M)
	
	D := BN254.ECP_fromBytes(SIG)
	if !BN254.G1member(D) {return BN254.BLS_FAIL}
	D.Neg()

	PK := BN254.ECP2_fromBytes(W)

	// Use new multi-pairing mechanism

	r :=  BN254.Initmp()
	 BN254.Another_pc(r, BN254.G2_TAB, D)
	 BN254.Another(r, PK, HM)
	v :=  BN254.Miller(r)

	v = BN254.Fexp(v)

	if v.Isunity() {
		return BN254.BLS_OK
	} else {
		return BN254.BLS_FAIL
	}
}

func main() {

	const BGS = BN254.BGS
	const BFS = BN254.BFS
	const G1S = BFS + 1 /* Group 1 Size */
	const G2S = 2 * BFS + 1 /* Group 2 Size */

        var S1 [G1S]byte
        var W1 [G2S]byte
        var S2 [G1S]byte
        var W2 [G2S]byte

        var W [G2S]byte
        var SIG [G1S]byte
        var SIG1 [G1S]byte
        var SIG2 [G1S]byte
	var IKM [32]byte

	rng := core.NewRAND()
	var raw [100]byte
	for i := 0; i < 100; i++ {
		raw[i] = byte(i + 1)
	}
	rng.Seed(100, raw[:])

    	IKM = salt(rng)

	mess := "This is a test message"

	argCount := len(os.Args[1:])

	if (argCount>0) {mess = string(os.Args[1])}

	res1 := BN254.Init()
	if res1 != 0 {
		fmt.Printf("Failed to Initialize\n")
		return
	}

	res1 = BN254.KeyPairGenerate(IKM[:], S1[:], W1[:])

	if res1 != 0 {
		fmt.Printf("Failed to generate keys\n")
		return
	}

	IKM = salt(rng)

	res2 := BN254.Init()
	if res2 != 0 {
		fmt.Printf("Failed to Initialize\n")
		return
	}

	res2 = BN254.KeyPairGenerate(IKM[:], S2[:], W2[:])
	if res2 != 0 {
		fmt.Printf("Failed to generate keys\n")
		return
	}

	BN254.Core_Sign(SIG1[:], []byte(mess), S1[:])
	BN254.Core_Sign(SIG2[:], []byte(mess), S2[:])

	addW(W1[:],W2[:],W[:])

	addS(SIG1[:],SIG2[:],SIG[:])

	fmt.Printf("\nBoneh-Lynn-Shacham BLS signature with aggregation\n")
	
	fmt.Printf("Message: %s\n", mess)
	fmt.Printf("Private key 1: 0x%s\n", printBinary(S1[:]))
	fmt.Printf("Private key 2: 0x%s\n", printBinary(S2[:]))
	fmt.Printf("\nPublic key 1: 0x%s\n", printBinary(W1[:]))
	fmt.Printf("Public key 2: 0x%s\n", printBinary(W2[:]))
	fmt.Printf("\nSignature  1: 0x%s\n", printBinary(SIG1[:]))
	fmt.Printf("Signature 2: 0x%s\n", printBinary(SIG2[:]))

	fmt.Printf("\nMerged public key: 0x%s\n", printBinary(W[:]))
	fmt.Printf("Merged signarture: 0x%s\n\n", printBinary(SIG[:]))

	res1 = Core_Verify1(SIG[:], []byte(mess),W[:])

	if res1 == 0 {
		fmt.Printf("Signature is OK\n")
	} else {
		fmt.Printf("Signature is *NOT* OK\n")
	}

And a sample run [here]:

Boneh-Lynn-Shacham BLS signature with aggregation
Message: Hello
Private key 1: 0x070e2c5972ccd123d226e4154af268ffe991547770bad5851f8504fe5c8321c300
Private key 2: 0x15eeee5e0798df883c3061e3d5d43ba6058ea2260fdff6b85f06ef500e64e7e900

Public key 1: 0x020f0df48aba4e7b11d8afbf6a2805d79ca9604c8940ab0ff24d092899074ecd641215e6ea01f97405ad6f285c332c6a13496bd456ef41a23278995e2b8aaf0c23
Public key 2: 0x020d58567bf38c4a28477f05caac740211ff9cefe6ad731ffc0331766751d1f8e31bdbf8084cf839fdd91d07e4744bd70c4c11dffd0e1e1d1e0692844c4e19e90a

Signature  1: 0x0218106169bd8fbb3b064caf9c0451deece2b5efdf690e5e2d3a6a241645a3e83a
Signature 2: 0x020c803ea9279cdda2883bdf5e1eee0d984fcb55ff8fb6f26ac9fc2bfba49a6230

Merged public key: 0x0309d39b921ff8cadee540eaf445292ec771e49933ad7ccb4d19aa17fe25464e3c031e9578c891c7e44590f446c1a6c87da14b4e342dd98f5ecdf9180410afe527
Merged signarture: 0x021972f3b104d6ff59d89a3969a453acbc0ab66bb75b16dd2354035255bbbaf631

Signature is OK

And, that’s magic!