2
$\begingroup$

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$.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – DrLecter
    Aug 10, 2016 at 12:20
  • $\begingroup$ 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? $\endgroup$
    – Ihtesham Haider
    Aug 10, 2016 at 13:50
  • $\begingroup$ 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). $\endgroup$
    – DrLecter
    Aug 11, 2016 at 8:38
  • $\begingroup$ 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?) ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Sep 9, 2016 at 23:39

2 Answers 2

Reset to default
1
$\begingroup$

If you want to try a scheme that is already being used in the industry, you may try EPID.

A paper describing it is on IACR eprint 2009-095.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Note that "providing an additional utility of being able to revoke a private key given a signature created by that key, even if the key itself is still unknown" requires that a party which learns a private key can determine whether-or-not a given signature was by that private key. ​ ​ $\endgroup$
    – user991
    Sep 11, 2016 at 23:27
  • $\begingroup$ @RickyDemer Absolutely, and EPID algorithm does that. I.e. if you know the private member key, you can recognize all signatures created with that key. $\endgroup$
    – Kris
    Sep 14, 2016 at 15:32
0
$\begingroup$

There are 3 types of pairing: types I, II, and III. Many protocols are designed in Type I, because it is simpler, but the most efficient groups are Type III. However, there are automatic translators for a protocol in Type I to Type III setting.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.