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

["Stanislav V. Smyshlyaev" <[e-mail]>]

Dear Julia,

Could you please take a look at the replies (sent by Vasilis on April
10th)? Are you happy with the updates and replies provided by the authors?

Regards,
Stanislav (for chairs)

On Thu, Apr 10, 2025 at 10:40 AM Vasilis Kalos <vasilis.kalos=
[e-mail]> wrote:

> Dear Julia and CFRG,
>
> I’m writing to inform you that our latest draft was published, with the
> hopes of addressing the comments from your revie: *https://www.ietf.org/archive/id/draft-irtf-cfrg-bbs-signatures-08.html
> <https://www.ietf.org/archive/id/draft-irtf-cfrg-bbs-signatures-08.html>*
>
> See below (as well as the previous, inline email) for a more detailed
> description of the changes made
>
> Are the changes satisfactory?? Is there anything we missed or should have
> added??
>
> Thank you very much,
> Vasilis Kalos
>
>
> ====
> In more detail, the updates we included are the following:
>
> > 3.1 demands subgroup_check algorithms, but they are already listed in
> 1.2 and hence are captured by "...plus associated functionality given in
> Section 1.2". So I'd suggest to drop them from the list in 3.1.
>
>     Done
>
> > 3.2 mentions utility procedures but does not further explain their role,
> as it does for core operations and Interfaces.
>
>     A more detailed description of the Utility procedures was added
>
> > Proof unlinkability …While Section 5 discusses potential threats to
> unlinkability, it does
> not mention headers…
>
>     We more precisely specified the unlikability term in *Section 3.3.7
> <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bbs-signatures-08#name-unlinkability>* as
> well as in *Section 5
> <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bbs-signatures-08#name-privacy-considerations>* (i.e.,
> that we use it as a synonym to zero-knowledge.). We also expanded on the
> differences between the header and the presentation header and how those
> values affect privacy in *Section 5.1
> <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bbs-signatures-08#name-header-and-presentation-head>*
> .
>
> > What is the motivation of computing e as hash of SK and the messages…
>
>     We better explained why the Signature algorithm is made deterministic
> in *Section 3.6.1
> <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bbs-signatures-08#name-coresign>*
> .
>
> > Regarding the functions from [RFC9380], why is expand_message not
> described in Section 1.2 but hash_to_curve is?
>
>     We defined the expand_message algorithm in *Section 1.2
> <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bbs-signatures-08#name-notation>*
> .
>
> > …is there any formal proof of unlinkability of the BBS proofs described
> in this draft
>
>     In general, we better specified which algorithm from the literature we
> use at the end of *Section 1
> <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-bbs-signatures-08#name-introduction>*.
> As we mentioned in the previous email (immediately bellow this one in the
> thread), we did not change the zk proof algorithm used, since we believe
> that the one utilized has gone under sufficient review by the academic
> community (also given the fact that is heavily based on the proof algorithm
> from [CDL16]). Please see the inline email for a more detailed answer.
>
> > Nits
>
>     Fixed
> ====
>
> ------------------------------
> *From:* Vasilis Kalos
> *Sent:* Thursday, October 24, 2024 8:58 PM
> *To:* [e-mail] <[e-mail]>; Julia Hesse <[e-mail]>
> *Subject:* Re: [CFRG] Review of BBS Signatures draft-07
>
>
> 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
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>