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 mainimport "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!

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store