Bilinear pairing + q-SDH + DLIN ⇒ CPA-anonymous group signatures (Boneh–Boyen–Shacham)

Random oracle model · via Fiat–Shamir · BBS04

Statement

Let be a bilinear group pair of prime order , with pairing , generators of and for an efficiently computable isomorphism , and let be a random oracle. In the BBS group signature, the opener holds with for in , and member holds a pair with , where is in , and samples and then uniformly among pairwise distinct elements of , which makes every defined and the pairwise distinct. A signature on is a Linear Encryption of under , for , together with a Fiat–Shamir proof of knowledge, with in the hash input, of a pair with and encrypted in ; decrypts and outputs the member holding it. In the random-oracle model the scheme is CPA-fully anonymous if the decision linear assumption holds in , and fully traceable if -SDH is hard in for every polynomial — BBS04.

A key generation that samples the independently and uniformly from gives exactly this key distribution when conditioned on the being pairwise distinct and different from , and the condition fails with probability at most . This bounds the statistical distance between the two key distributions and is negligible for polynomial , because hardness of DLIN, and likewise of -SDH, forces to be superpolynomial; so both security statements hold for this key generation. Linear Encryption decrypts exactly and the proof of knowledge is perfectly complete. With pairwise distinct , every honest signature therefore verifies and opens to its signer, and the scheme is perfectly correct — standard.

Notes

  • A signature is three elements of and six elements of , approximately the size of an RSA signature at the same security level — BBS04.
  • The -SDH problem is the form of BB04a: given , output — BBS04.
  • A member key is a weak Boneh–Boyen signature on under the key — standard.