[CFRG] Re: Review of BBS Signatures draft-07

[Vasilis Kalos <[e-mail]>]

Dear Julia,

Thank you very much for the review and invaluable insights! Please find some comments and questions we have inline. For anything not addressed in this email we agree with the review and are currently working to update the document accordingly.

> The draft seems to specify algorithms similar to those in [TesZho23].

We are using the one from Appendix B from the [TesZho23] paper. The only difference is that we use r_2 instead of 1/r_2 when calculating \bar{A} and D and reverse it later to calculate z (or as we call it in our document r_3^).

> Regardless of what version is specified here, I would like to note that (2) and (3) only have sketched security arguments in [TesZho23], and no  proofs of properties such as unlinkability that are claimed in the draft.

Regarding the formal proof of unlinkability, although I agree that it can be made clearer, it seems to me that it does not lack formality. The last paragraph of the paper (page 31) describes how to simulate the BBS proof. The step that is missing is the verification that the simulated BBS proof is valid. The verification equations using U_1 and U_2 (in the paper notation, we call them T_1 and T_2 in our document) hold trivially (by construction). The equation e(\bar{A}, X_2) = e(\bar{B}, g_2) holds given the fact that in the simulated case, \bar{B} = \bar{A} ^ x (again using the exponentiation notation from the paper). Do you think this will be enough to use that proof??

> is there any formal proof of unlinkability of the BBS proofs described in this draft, e.g., using empty headers? [TesZho23] does not mention unlinkability, that's why I'm asking.

We use the term unlinkability as a synonym of zero-knowledge (L-HVZK more specifically). Again, something to clarify in the document.

> What is the motivation behind signing an empty message?

Allowing an application to indicate “absence” of an attribute (note that an “empty” message will be mapped to a non-zero scalar by the hash_to_scalar operation).

> What is the motivation of computing e as hash of SK and the messages,  instead of drawing it uniformly?

To make testing easier by making signatures deterministic, while at the same time limiting the attack surface that can arise from bad entropy sources.

> "each BBS proof is indistinguishable from random" - by whom? Surely not by a verifier who has the header and the message.

The intent was to specify that the proof value itself (as outputted by the ProofGen operation, without the header or the messages) is unlinkable. If the Issuer elects to make use of the header, they should take into account the privacy guarantees the deployment tries to enforce (described briefly in Section 3.3.6). In any case we should make the above clearer in the document.

> For example, if one follows the recommendations of 6.4, the proofs become fully linkable.

Section 6.4., was not targeted to the “header” but the “presentation_header”, chosen by the Prover and “bound” only to the BBS proof. Given that a new one can be chosen each time a proof is generated, unlinkability should be preserved. We should further clarify that.

> Section 6.1 What can happen if the algorithms are run with an invalid serialized PK, i.e., if an implementor decides to skip the recommended PK validity check?

Passing an invalid PK to the pairing operation can have unexpected, implementation specific results (like returning an error or the zero point of the target group etc.).

> Section 6.9 "[CRQC] adversaries will not be able to compromise the data confidentiality property of a BBS signature - I don't understand how

The section refers to the BBS Proof. Although using a signature one could reveal the undisclosed messages as you indicated, doing the same with only a BBS proof should not work.

Kind regards,
Vasilis Kalos