What happened after the Boneh, Boyen, Shacham 2004 paper?

Clare Nelson from the Dencentralised Identity Forum [here] put me onto a great event at the Crypto Reading Club of NIST. If you are not used to a research reading club, you consider it, as those attending get a chance to read a paper and discuss it. The next event is on 18 October 2023, and details are here:

https://csrc.nist.gov/Projects/crypto-reading-club

and you can subscribe here: crypto-club-questions@nist.gov.

The abstract is:

BBS is a digital signature scheme categorized as a form of short group signature that supports several unique properties. Notably, the scheme supports signing multiple messages whilst producing a single output digital signature. Through this capability, the possessor of a signature is able to generate proofs that selectively disclose subsets of the originally signed set of messages, whilst preserving the verifiable authenticity and integrity of the messages. Furthermore, these proofs are said to be zero-knowledge in nature as they do not reveal the underlying signature; instead, what they reveal is a proof of knowledge of the undisclosed signature.

The great thing about the event is that there is now a new draft of a standard [here]:

BBS

Can we produce a digital signature for a group of members, and then for it not to be possible to know who has signed within the group? This problem was solved in 2004 with BBS signatures and where Boneh, Boyen and Shacham defined this in this classic paper [here]:

The method uses a group signature approach with bi-linear maps. This produces a signature that is around the same size of the RSA signature (around 200 bytes). Within elliptic curve methods, we have two curves: G1 and G2. If we have the points of U1 and U2 on G1 and V1 and V2 on G2, we get the bi-linear mapping of:

e(U1+U2,V1)=e(U1,V1)×e(U2,V1)

e(U1,V1+V2)=e(U1,V1)×e(U1,V2)

If U is a point on G1, and V is a point on G2, we get:

e(aU,bV)=e(U,V)^{ab}

Within BBS, using elliptic curve pairs, we have G1 and G2 which are BN256 curves, and these map to GT, and which is also on a BN256 curve. This is the pairing function.

Group signatures

With a group signature we create a membership of a group with defined private keys. These are defined as members, and the signature of any member cannot be seen from the signature, in terms of the public key of the signature.

With group signatures use a group manager and which responsible for signing things on behalf of the members. The key features of group signatures are:

• Soundness and completeness. This means that it is always possible to check valid signatures, and that invalid ones will always fail.
• Unforgeable. This means that we can only create a signature when the members of the group are involved.
• Anonymity. This means that it will not be possible to reveal any of the signers of a message. This can only be revealed with the group manager’s secret key.
• Traceability. This means that the group manager can reveal the signer with its secret key.
• Unlinkability. This means that given two or more signed messages, it is not possible to trace that they are signed by the same member.
• Coalition resistance. This means that it is not possible to create a signature without the consent of one of the members.

With group signatures, we create a group private key, and which differs from each of the private keys of members. Then the group private key can produce private keys, and can also be used to reveal the signer of a message. With this we must also revoke the private key of a member, and this is done with a public announcement of the revocation. This can then also create a new group private address, and which revokes the private key of a member.

Sample code

In this case we will take a SHA-256 hash of a message, and then sign this with the group private key. The code involved is [here]:

package main
 
import (
	"github.com/agl/pond/bbssig"
	"crypto/rand"
	"crypto/sha256"
	"fmt"
	"os"
)



func main(){
	m:="Hello"

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


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



	priv, _ := bbssig.GenerateGroup(rand.Reader)

	group := priv.Group
	member,_ := priv.NewMember(rand.Reader)


	msg := []byte(m)
	h := sha256.New()
	h.Write(msg)
	hashmsg := h.Sum(nil)


	fmt.Printf("Message: %s\n", msg)

	sig, err := member.Sign(rand.Reader, hashmsg, h)
	if err == nil {
		fmt.Printf("Message signed okay: %x\n", sig)
	}

	if group.Verify(hashmsg, h, sig) {
		fmt.Printf("Signature verified okay\n")	
	}

	hashmsg[1] ^= 0x01
	if !group.Verify(hashmsg, h, sig) {
		fmt.Printf("Signature failed okay\n")
	}
	hashmsg[1] ^= 0x01

	tag, ok := priv.Open(sig)
	if ok {
		fmt.Printf("Signature opened okay.\n\nTag: %x\n",tag)
	}
}

In this case we will flip the least significant bit of the hash of the message, and check the signature (and which should fail). Next, we flip it back and check again (and which should be successful).

A sample run is [here]:

Message: Hello
Message signed okay: 17caba412ca379549bfaa777cbd8e6c7cc2782ce3b5e2df98839a57874d588b05544591e80e1aac58b05b4091f42d43a397d8ec31dec6b06bc8926d374ea6b7d5ef3e97d30d46c4c514d01319a724d4556ebf252222722fc0ff5303bf82b860a595b67f65e46808ec7fa085a4a3a4d8564df7c6c22253feed92d8ada0a4192f832451acc1827807f60e90c9ab5719ddc123e017f1544ae2bbdbae12ad2ace31370822b5a0a6d6f5b37b4da6ddb87b4b2e0db69936e8b91107eabfad49005429e07ffd56971d953d38f86cc7902c2087892b9f9da9731dd1006299cdde1605b590b4cb6f8b77f48001b025dd6d10a83a78bcc6e5fbe6a5cda24c94a1b4b8444f44436e10728ec17fa1085322b071fdd28cb3e6d109af9cec3a3423eb3f978fa3067ccabbcd0b41d9074f9f4da07516932cd8c5564d16dd39ea52a35799a1d8844136238035d60f5b22096404782ad1e0e7ad067ecd53046cd17525501adca0ca169320a84cf9e4f174a19ff20fcaacc4aab8ba2efd1b0e925c2bfc12bf44318fc
Signature verified okay
Signature failed okay
Signature opened okay.
Tag: 4421373d72e5e8f10a89a3512f67334a8bd6bab4fac3ab1efbdbf87282195de1639d9d690bd47f7eb0d86d5aac62845c91003bcdf6f429e3479a2278e94b4b4chttps://csrc.nist.gov/Projects/crypto-reading-club

Conclusions

BBS — and group signatures in general — address the problem of creating trust in our transactions, while preserving the rights to privacy. Please consider registering with the Reading Club:

Crypto Reading Club | CSRC | CSRC

and join the email list here:

crypto-club-questions (at) nist (dot) gov.