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

[Michele Orrù <[e-mail]>]

Hi Vasilis,

Let me reiterate my suggestions, providing actionable comments, trying to
be more precise, and clarifying some parts of my previous email that might
have been misleading.

*Suggestion 0: add mentions of Pippenger and fixed-basis algorithms.*
*>>> Add in [draft-irtf-cfrg-bbs-signatures
<https://github.com/decentralized-identity/bbs-signature/blob/main/draft-irtf-cfrg-bbs-signatures.md?plain=1#L280>,
line
280] : *
  Fixed-basis scalar multiplication algorithms can improve computation time
(~4x) while maintaining constant-time operations.
  Pippenger's algorithm can improve asymptotic complexity to O(N/log N).
Common implementations are not constant-time.
*Add references for both. *

*Suggestion 1: make pairings optional and allow for keyed-verification.*
Roughly speaking, one only needs to compute xA and check it is equal to B -
eA, whether it's done in a target group or G1 doesn't matter.
Concretely, the minimal change to provide compatibility is:

*>>> Change [draft-irtf-cfrg-bbs-signatures
<https://github.com/decentralized-identity/bbs-signature/blob/main/draft-irtf-cfrg-bbs-signatures.md?plain=1#L706>,
line 706] in BBS: *
*- *3. if h(A, W + BP2 * e) * h(B, -BP2) != Identity_GT, return INVALID
Better:
+ 3. if h(A, W) != h(B - eA, BP2), return INVALID
By the way, this is going to improve performance as well (try to limit as many
operations as possible over G2) without changing the API and remove the
confusing multiplicative/additive group notation.
Best:
+ 3. if DH(W, A, B - eA) = 1, return INVALID
You can then describe DH as  a pairing as above. Other people will override
your implementation of DH without making too much of a mess around.
For the record, this may be useful for everybody:  it can be that the
issuer has to re-check some signatures and in that case you're allowing it
to do DH as they like.
The same can be done for CoreProofVerify. Let's discuss blind BBS, and the
server proof, later as it's not as immediately important.

*Suggestion 2: make the user proof optional for one-more unforgeability
applications.*
I think there might have been a misunderstanding here. My proposal
(coherent with your response) is:
*>>> Change ProofInit [draft-irtf-cfrg-bbs-signatures
<https://github.com/decentralized-identity/bbs-signature/blob/main/draft-irtf-cfrg-bbs-signatures.md?plain=1#L869-L931>,
line 869-931
<https://github.com/decentralized-identity/bbs-signature/blob/main/draft-irtf-cfrg-bbs-signatures.md?plain=1#L869-L931>]
in BBS*
*Move 6-7 (and the relative randomness) into a separate proving function. *
*>>> Change CoreCommit [draft-kalos-bbs-blind-signatures
<https://github.com/BasileiosKal/blind-bbs-signatures/blob/main/draft-kalos-bbs-blind-signatures.md?plain=1#L582-L590>,
line 582-590
<https://github.com/BasileiosKal/blind-bbs-signatures/blob/main/draft-kalos-bbs-blind-signatures.md?plain=1#L582-L590>]
in blind BBS*
*Move 3-7 into a separate proving function, just like you do for the
standard BBS signature.*

Reason:
If one wants to prove one of the attributes is well-formed (e.g. is binary,
or 128-bits, etc), they will be able to do so without overwriting this core
function.
If you want to support many attributes, it won't make any sense to hardcode
Σ-protocols in the spec rather than compressed Σ-protocols ("bulletproofs").
If one wants to remove the CoreCommit proof for one-more unforgeability,
they will be able to set proof to the empty string in a separate spec.

*Suggestion 5: better describe the security guarantees in the draft.*
*>>> Add in [draft-irtf-cfrg-bbs-signatures
<https://github.com/decentralized-identity/bbs-signature/blob/main/draft-irtf-cfrg-bbs-signatures.md?plain=1#L1737>,
line 1737]:*
*A paragraph similar to* [rfc9497
<https://datatracker.ietf.org/doc/html/rfc9497#section-7.2.3>, 7.2.3].

*Suggestion 6: add multiplicative blinding for Blind BBS.*
*>>> Add a paragraph similar to [draft-irtf-cfrg-voprf-07
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-voprf-07#name-blinding-considerations>,
6.6]*
*>>> Add a paragraph similar to [draft-irtf-cfrg-voprf-06
<https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-voprf-06#name-additive-blinding>,
7]*

*Suggestion 7: describe the behaviour of the user/prover concerning
**attributes
set by the server.*
*>>> Change the function signatures to match [rfc9474
<https://www.rfc-editor.org/rfc/rfc9474.html#name-blind-signature-protocol>,
4] *
*The API is similar to the one of VOPRF in rfc9497, which should also be
checked for consistency.*
In particular, *add a function Finalise, which MAY reject the signature if
the user so wishes.*

You can leave the function empty (trivially accept everything for now). Let
other extensions (and future schemes) do the work but give them an entry
point.


*Suggestion 10: make proofs extensible with arbitrary statements**>> Add
after [draft-irtf-cfrg-bbs-signatures
<https://github.com/decentralized-identity/bbs-signature/blob/main/draft-irtf-cfrg-bbs-signatures.md?plain=1#L710>,
line 710] the following paragraph:*

+ We prove the following statement, expressed in Camenish-Stadler notation:
+
+ ```
+ ZkPoK{
+   "BBS-foobar" + ph,                               // Label for the proof
statement, whatever needs to be added to the challenge
+   (e, r1, r3, msg_j1, ..., msg_jU),                // Secret variables
+   (Abar, Bbar, D, Bv, H_j1, ..., H_jU),            // Public variables
unique to each proof
+   Bbar = D * r1 - Abar * e,                        // Statements to prove
+   Bv = D * r3 + H_j1 * msg_j1 + ... + H_jU * msg_jU
+ }
+ ```

*>> Add after [draft-kalos-bbs-blind-signatures
<https://github.com/BasileiosKal/blind-bbs-signatures/blob/main/draft-kalos-bbs-blind-signatures.md?plain=1#L582-L590>,
line
590] the following paragraph*
+ We prove the following statement, expressed in Camenish-Stadler notation:
+
+ ```
+ ZkPoK{
+   "blind-BBS-foobar" + api_id,                                       //
Label for the proof statement, whatever needs to be added to the challenge
+   (secret_prover_blind, msg_1, ..., msg_M),                          //
Secret variables
+   (Q_2, J_1, ..., J_M),                                              //
Public variables unique to each proof
+   C = Q_2 * secret_prover_blind + J_1 * msg_1 + ... + J_M * msg_M,   //
Statements to prove
+ }
+ ```

Reason:
More clarity on the statement to be proven.
It will allow people to adopt their own proof system: for L >= 8 it won't
make much sense to use Σ-protocols in the spec rather than compressed
Σ-protocols ("bulletproofs") whose proof size is going to be about
2log_2(L) + 2.
Extra features such as pseudonyms, rate limiting etc are just additional
"statements to prove".

Here are suggestions that I am putting on the side for now.

*Suggestion 3: bridge with rfc9576 <https://www.rfc-editor.org/rfc/rfc9576
<https://www.rfc-editor.org/rfc/rfc9576>>.*
*Suggestion 4: understand the security and efficiency trade-offs with PS.*
*Suggestion 9: simplify Fiat-Shamir and have a generic framework for future*
 *proofs.*
In particular, I'll follow up as soon as I can on the latter.

Julia also rightfully pointed out the limits in the description of your
proofs and in the claims of unlinkability.
I haven't had time to look properly into it yet, however I am persuaded
this is fine in the keyed-verification case [Orru24
<https://eprint.iacr.org/2024/1552.pdf>, Theorem 21]. However, in
keyed-verification, the server also gives an extractable proof of knowledge
of the secret key.

Ciao,
--
Michele.

On Fri, Oct 25, 2024 at 12:21 PM Vasilis Kalos <[e-mail]>
wrote:

> Dear Michele and all,
>
>
>
> Thank you for the review! I do agree with the suggestions. See some
> comments inline.
>
>
>
> > *.BBS tokens and keyed-verification*
>
> > … the issuer and redeemer are the same person just like in Privacy Pass
> (this is called "algebraic MAC" in cryptography). In fact, if the
> verifier has x, then we don't need a pairing map to check signatures: a
> BBS signature (A, e) for a message commitment C is valid if xA = C - eA.
>
> That’s true, but I don’t think the User (Client in pp) will have access to
> the Issuer's sk. In the algebraic MAC case, it will be the Verifier (Origin
> I think in pp) that will have the Issuer’s sk. For the Client to verify the
> signature without pairings, the Issuer will have to generate a ZKP of
> knowledge for an x so that pk = G * x and A * x = C - A * e. That to say,
> although I do really like the idea of a DH oracle, making the pairings
> optional may not be that simple.
>
>
>
> (We do have a draft on the above here
> <https://basileioskal.github.io/pairing-free-bbs/draft-vasilis-pairing-free-bbs.html>.
> Would be open to merging the documents if there is a need)
>
> > *.Concrete security of the protocol *
>
> > *Suggestion 4: understand the security and efficiency trade-offs with PS
> signatures*
>
>
>
> The main advantage of BBS Signatures IMHO is the decoupling of the PK from
> the number of messages. TMU, in PS each “type” of credentials (with a
> different number of attributes) will need a different PK. For that reason,
> BBS Signatures are more suitable for “generic use cases”, providing more
> flexibility (like hiding the Issuer use cases).
>
> > *.Blind BBS multiplicative blinding*
> > It is possible to have "blind BBS" as a pair (A, e) consistent with the signature
> using *multiplicative* instead of additive blind.
>
>
>
> Note that in the last version of blind signatures
> <https://www.ietf.org/archive/id/draft-kalos-bbs-blind-signatures-03.html>
> we removed the “signer_blind” and re-introduced it in pseudonyms
> <https://www.ietf.org/archive/id/draft-kalos-bbs-per-verifier-linkability-00.html>
> only. So, the blind signature currently is (A, e).
>
>
> > *.Blind BBS API design*
> > one-more unforgeable tokens. If the user proof can be optional, it's
> easy
>
> to just have another specification say that that function is just a nop
>
> We also added `FinalizeBlind
> <https://www.ietf.org/archive/id/draft-kalos-bbs-blind-signatures-03.html#name-finalize-blind-sign>`
> (Section 4.3.3 on the blind BBS signatures draft
> <https://www.ietf.org/archive/id/draft-kalos-bbs-blind-signatures-03.html>)
> which will sign any point B, without checking any user provided proof.
>
> In any case, the documents are far from final. Any proposal and
> contribution will be extremely appreciated.
>
> > *.On the zero-knowledge proofs*
>
> > *Suggestion 9: simplify Fiat-Shamir and have a generic framework for
> future proofs*
>
>
>
> For a generic ZKP I expressed my thoughts here
> <https://mailarchive.ietf.org/arch/msg/cfrg/d58lWLAOLN5UgGSvu3VmwsJtG2E/>.
> I’m still not convinced that the core BBS draft is the best place for such
> a description.
>
>
>
> Nevertheless, I will be happy to help with that, no matter where it lands,
> since I do find it really useful.
>
>
> Kind regards,
> Vasilis Kalos
>