BBS — The Short And Anonymised Group Signature

BBS — The Short And Anonymised Group Signature

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]:

Bi-linear maps

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]:

In this case we 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: 4421373d72e5e8f10a89a3512f67334a8bd6bab4fac3ab1efbdbf87282195de1639d9d690bd47f7eb0d86d5aac62845c91003bcdf6f429e3479a2278e94b4b4c

Here is a demo:

Conclusions

BBS — and group signatures in general — address the problem of creating trust in our transactions, while preserving the rights to privacy.