BLS Signatures: Fast, Efficient and Short: Checked With The Magic of Crypto Pairing

One of the most interesting topics that I have investigated is pairing-based cryptography, and they have so many applications, such as in…
Photo by Signature Pro on Unsplash

BLS Signatures: Fast, Efficient and Short: Checked With The Magic of Crypto Pairing

One of the most interesting topics that I have investigated is pairing-based cryptography, and they have so many applications, such as in Zero-knowledge proofs, authenticated key exchange, and in creating aggregated signatures. So, let’s look at the BLS (Boneh–Lynn–Shacham) signature method [1], and which produces one of the smallest digital signatures around.

Pairing based cryptography

With pairing-based cryptography we have two cyclic groups (G1 and G2), and which are of an order of a prime number (n). A pairing on (G1,G2,GT) defines the function e:G1×G2→GT, and where g1 is a generator for G1 and g2 is a generator for G2. If we have the points of U1 and U2 on G1 and V1 and V2 on G2, we get a bilinear mapping of:

e(aU,V)=e(U,aV)

and where U is a point on G2, and V on G1.

BLS Signature

With BLS signatures [1], we create a private key (sk) and then generate a public key on the G2 group as pk=sk.G and where G is the base point on the G2 group. The message (Msg) is then hashed to the G1 group, and the signature (S) is S=sk.HashToCurve(M). We can check the signature using pairings. Overall, we hash data and add the public key to the G1 group and the public key to the G2 group.

We have migrated the ECDSA method of signing Bitcoin transactions as the method has been shown to be only as strong as the randomness of the random numbers used. It also requires all the public keys to be checked where there are multiple signers. This was causing Bitcoin to slow down, so the signature scheme was changed to the Schnorr scheme. With this, we can merge the signing process, and aggregate the public keys together into a single signature.

But the BLS signature method is seen to be even stronger for signing. It uses a bi-linear pairing with an elliptic curve group and provides some protection against index calculus attacks. BLS also produces short signatures and has been shown to be secure. While Schnorr requires random numbers to generate multiple signers, BLS does not rely on these.

If Alice wants to create a BLS signature, she first generates her private key (sk) and then takes a point on the elliptic curve (G) and computes her public key (pk):

P=sk.G

and where G is the base point on G2. She takes a hash of the message, and then map the hash value to a point on an elliptic curve. If we use SHA-256 we can convert the message into a 256-bit x-point. If we do not manage to get a point on the curve, we add an incremental value to find the first time that we reach the point. The signature of a message (Msg) and then computed with:

S=sk×H(Msg)

and where H(M) is the 256-bit hash of the message (M). Her private key is sk and her public key (P) and which is equal to aG. The test for the signature is then:

e(G,S)=e(P,H(Msg))

This can be proven as:

e(G,S)=e(G,sk×H(Msg))=e(sk×G,H(Msg))=e(P,H(M))

and where G is the generator point within the (G_2) group, and P is a point within the G_1 group.

Coding

In this case, we will use the Kryptology library, and take a SHA-256 hash of the message and hash it to the G2 group. We then sign this with the private key, and then check the signature using pairings [here]:

package main
import (
	"crypto/rand"
	"fmt"
	"os"
	"github.com/coinbase/kryptology/pkg/signatures/bls/bls_sig"
)
func main() {
	msg := "Hello"
	argCount := len(os.Args[1:])
	if argCount > 0 {
		msg = os.Args[1]
	}
	r := make([]byte, 32)
	rand.Read(r)
	bls := bls_sig.NewSigBasicVt()
	pk, sk, _ := bls.KeygenWithSeed(r) // pk= sk*G2
	msg1 := []byte(msg)
	bls1 := bls_sig.NewSigBasicVt()
	sig, _ := bls1.Sign(sk, msg1)
	s, _ := sig.MarshalBinary()
	sk1, _ := sk.MarshalBinary()
	pk1, _ := pk.MarshalBinary()
	fmt.Printf("Message: %s\n", msg)
	fmt.Printf("Random value: %x\n", r)
	fmt.Printf("Private key: %x\n", sk1)
	fmt.Printf("Public key: %x\n", pk1)
	fmt.Printf("\nBLS Signature: %x\n", s)
	if res, _ := bls.Verify(pk, msg1, sig); res {
		fmt.Printf("Signature verified")
	} else {
		fmt.Printf("Signature NOT verified")
	}
	// Signature
	// M=HashToCurve(msg) on G1
	// R = sk.M on G1
	// Verify
	// R = signature_to_point(signature)
	// sk.P = pubkey_to_point(PK)
	// Q = hash_to_point(message)
	// C1 = pairing(Q, xP)
	// C2 = pairing(R, P)
	// Check C1 == C2 = (M,sk.G) = (sk.M,G) = (R,G)
}

A sample run [here]:

Message: hello
Random value: f5464c56ecad9a20079a7fbfcbdb27c2030295fe578d11b7ec0c34db4e307baa
Private key: 1f9b67d160c9dc211cf6fe229aed5f4d4dec7c9b2b45a97d1bc96f26d4aee50a
Public key: 8279d71026e4c6e278355f1e9f1a4f094a17a3059fb241023c5f656da526b50c68e18f3cf3bc0d9012ddc87caa0466c411278ad17b2308e5dfd08a35ac559680f8f3ddce7ef9e67bc244e289ad63b440cfbf9f4b4fd5659b3d2abdf9fa2feeaa
BLS Signature: b39687aebac313ecb49463473aa3c12adf8d4f86aa8ed81c28f4bfeacf937aa22db9e62fd12f6bbdaf5b44bb1b4285cf
Signature verified

Conclusions

If you want to find out more about Kryptology:

https://asecuritysite.com/kryptology

and for pairing-based cryptography:

https://asecuritysite.com/pairing/

References

[1] Boneh, D., Lynn, B., & Shacham, H. (2001, December). Short signatures from the Weil pairing. In International conference on the theory and application of cryptology and information security (pp. 514–532). Springer, Berlin, Heidelberg.