Cybersecurity Magic! (t,n) Threshold Signatures with BLS

Cybersecurity Magic! (t,n) Threshold Signatures with BLS

Over the past year or so, I’ve been working on BLS (Bonheh-Lynn-Sacham) cryptography. The core advantage of BLS is that it is aggregatable, including for secret keys, public keys and signatures. For this we could take three symmetric keys and then aggregate them together, and still end up with a valid key. We can do the same with signatures, and where we might have 10 signers of a Bitcoin transaction, but where we can merge all of their signatures into a single signature, and where we could also merge their public keys together into a single public key for all the signers. With signatures, we can take a number of signatures and merge them together, and then end up with a unique signature. It is basically cybersecurity magic!

If you want to find out about the maths behind BLS, try here:

And here is how we can use it to verify votes in an election:

For a (t,n)-threshold Boneh-Lynn-Shacham signature , we can create a trustless infrastructure, and where we have a single public key for all of the signers. They will then receive a signing share, and a given number of them can come together and verify the signature. This is defined as a t-from-n sharing system, and where we have n shares and t defines the threshold number that we need to verify the signature. For this we use the classic Shamir Secret Sharing system, and where we can split any secret into n shares and create a threshold of t. We rebuild the shares using Lagrange interpolation.

Here is the code example:

The following is the code [taken from here]:

package main

import (
    "fmt"
    "os"
    "encoding/hex"

    "go.dedis.ch/kyber/share"
    "go.dedis.ch/kyber/pairing/bn256"
    "go.dedis.ch/kyber/sign/tbls"
    "go.dedis.ch/kyber/sign/bls"

)
func main() {

    
    M:="test"

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

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

    msg := []byte(M)

    fmt.Printf("Input: %s\n\n",M)

    suite := bn256.NewSuite()
    n := 6
    t := n/2 + 1
    secret := suite.G1().Scalar().Pick(suite.RandomStream())
    priPoly := share.NewPriPoly(suite.G2(), t, secret, suite.RandomStream())
    pubPoly := priPoly.Commit(suite.G2().Point().Base())
    sigShares := make([][]byte, 0)

    for _, x := range priPoly.Shares(n) {
        sig, _ := tbls.Sign(suite, x, msg)
        fmt.Printf("Share %d: %x\n",x,sig)
        sigShares = append(sigShares, sig)
    }

    sig, _ := tbls.Recover(suite, pubPoly, msg, sigShares, t, n)

    err := bls.Verify(suite, pubPoly.Commit(), msg, sig)

    if (err==nil) {
        fmt.Printf("\n\nSignature recovered:  %s",hex.EncodeToString(sig))
    }   

}

A sample run is:

Input: Testing 1234

Share &{0 824634049856}: 0000640eddc5387fc77e1eda5cc5fd0240e42fd47c4769ec1dbb2b4b6fbbd517e329333618872d0f05e7dbb3242d8162a7e4f5a71dfa1aeced50d122b1c33a27cdf6
Share &{1 824634049952}: 0001380a18b70ab392caa04c7e8f65b240862bcfb158ddf45a27d6e56d25426e9b10054af5543579aa5c53fd5315b214beb8a860f32a08ec89bb56b6b40113433bd8
Share &{2 824634050048}: 00023edb511e3a617e1c14aecb60b3fd3c2ea381689f88953e0f0b6ea9910aaef22d5050f06080cef0539c9fd0bfaae0570bf515d9b441f233ef25a156902b61c403
Share &{3 824634050144}: 0003857dc4bec52f5bd755a65f8e4c07896048dcd427be17b17997545bf045c569b873595c777689bbe94dcad31cb00ea13104f526ed9e1c85c967152a3e420a36a5
Share &{4 824634050240}: 0004856a88de04d8d391989678fe78672e01fc8c94d80caeb35f84b3f9c7d0898d17268c6671a2acc88b5b42dd48339e07f80aabeacf3022439dac6e993997f9d32d
Share &{5 824634050336}: 00052f5166b418ff7af421eab2284a80a21d7b5ceaad4db81b448f700219c81da908553943a73ca054a3445478cb127daf5732a23daac729de03bf658a1479f2c3e5

Signature recovered:  45e13b96504182b6e6289258dc93df64e03e66f85b4ffd44547085b7393f9bf03d2d77026f0cbfa0baf2657a1b1c4c5f9e821f392aeb81ba4c92e5071f510ad1

BLS uses two curves (G1 and G2). Basically the signatures are defined by points on the G1 curve and public keys map onto the G2 curve.

Conclusions

We need to dump our paper based signatures and move towards proper digital ones. If you are interested in the Shamir Secret Share method, see this:

This blog has been verified by Rise: Rcf68fc8ed48b71b26fb8e908460f6b1e