# Choice of bilinear group for implementation of BLS signature with NIWI proof?

I am trying to sign the multiple (millions of) different readings but the receiver should not be able to link multiple signed readings together (unlinkability) or with the identity of the signer (anonymity).

As a potential solution, the sender sends the reading $m$ along with non-interactive witness indistinguishable (NIWI) proof of knowledge (PoK) of signature on $m$. I am looking at certified signature scheme where CA certifies the public keys of legitimate signers. The signer signs the reading $m$, generate NIWI proof of knowledge of his/her signature on the reading $m$ and sends ($m$ and the NIWI proof) to the receiver. I want to use BLS signatures as the signature is one element in $G_1$ (and the signature size can be as short as 161 bits). BLS signature scheme uses gap Diffie-Hellman (co-GDH) groups $(G_1,G_2)$ of prime order $p$, where co-DDH is easy but co-CDH is hard.

Now, in order to construct proof of knowledge of BLS signature, I want to use the Groth and Sahai's NIWI proof in Efficient Noninteractive Proof Systems for Bilinear Groups which can be constructed based on one of the three assumptions:

1. sub-group assumption
2. SXDH assumption
3. DLIN assumption.

I am confused, which assumption can I make for generating NIWI PoK of BLS signature?

Q1. Can I use SXDH assumption based NIWI PoK i.e. is it valid to simultaneously make co-GDH and SXDH assumptions on the group pair $(G_1,G_2)$?

Q2. DLIN based NIWI proof will require me use symmetric pairings for BLS signatures. Is symmetric setting suitable for secure and short BLS signatures?

Q3. Can I use subgroup assumption for NIWI PoK of BLS signature? as $|G_1|=|G_2|= p$.

• co-CDH and SXDH do not contradict. Actually, co-CDH is a variant of CDH for asymmetric pairings and the SXDH only makes sense in the asymmetric setting (it esentially models type 3 pairings, i.e. pairings where DDH is hard in both source groups). – DrLecter Aug 10 '16 at 12:20
• BLS signature scheme uses co-GDH group pair G1, G2 of prime order p, where co-DDH is easy but co-CDH is hard and there exist a map ψ from G2 to G1 (Type 2 pairings). This means (G1, G2) cannot satisfy SXDH assumption? – Ihtesham Haider Aug 10 '16 at 13:50
• You can use the type-3 variant of BLS, then it works. There is a work by Chatterjee et al. that discusses BLS signatures in type 2 and type 3 settings, which may be of interest to you (eprint.iacr.org/2009/060). – DrLecter Aug 11 '16 at 8:38
• I cannot think of any application of that in which computational soundness would not be enough. ​ (i.e., it seems like you should be after NIWI arguments of knowledge.) ​ ​ ​ Independently of that, what exactly do you mean by "certifies the public keys of legitimate signers"? ​ (just that the party claims to have that as their private key? additionally that there exists a compatible private key? additionally that the party knows a compatible private key?) ​ ​ ​ ​ ​ ​ ​ ​ – user991 Sep 9 '16 at 23:39