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

[Watson Ladd <[e-mail]>]

As someone who would like to use this draft but can't in a closely
related document, let me join in the conversation.

On Sun, Oct 20, 2024 at 8:30 AM Michele Orrù <[e-mail]> wrote:
>
> Following Julia's excellent points, I’d like to add a high-level review after discussing the topic with other researchers. The comments below address both the BBS specification and the blind BBS specification. I’m adding Jonathan Katz and Sam Schlesinger (both from Google) in CC, who support this specification, but note that they haven’t reviewed this email, and any mistakes are my own. Each paragraph is preceded by a one-liner that summarises the suggestion I am trying to argue for.
>
> As Julia mentioned, standardising this protocol is challenging, so I want to start by saying that I greatly appreciate the authors' efforts in making this happen.
>
>
> .Fast algorithms for scalar multiplication
> Suggestion 0: add mentions of Pippenger and fixed-basis algorithms.
>
> The specification should provide guidance on computing fast, generic algebraic operations. This was also evident in Jaromil's implementation shared earlier. Given the generators are fixed and the signature involves multi-scalar multiplication, pointers to fixed-basis scalar multiplication and Pippenger's algorithms would help improve efficiency.

Pippenger is a pain to actually write, and making it constant time is
tricky. But for verification constant time isn't really a problem, and
so go use Pippenger. I personally find Bos-Coster to offer a very good
performance improvement for very little extra coding, but it depends
on the number of points being included.

>
> .BBS tokens and keyed-verification
> Suggestion 1: make pairings optional and allow for keyed-verification.
> Suggestion 2: make the user proof optional for one-more unforgeability applications.
> Suggestion 3: bridge with rfc9576.
>
> By "tokens", I mean blind signatures and anonymous tokens in the way they are being used in rfc9576.
> Fact #1: Tessaro and Zhu [TZ23, Thm. 3] showed that Blind BBS without the user proof (commitment_with_proof without proof) is one-more unforgeable.

I find the above discussion a little
> Fact #2: Barki et al. [BBDT16] showed that it's possible to use trade off pairings in BBS+ signatures with 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.
>
> This provides a natural integration with rfc9576, enabling features like keyed-verification, public verifiability, pseudonyms, and rate-limiting, with only one-more unforgeability required. Could offering an option to remove pairings via a DH oracle in the API encourage adoption? Removing the user proof might also make this competitive with Privacy Pass extensions. @Watson Ladd has already put significant effort into implementing and describing the requirements for a rate-limiting BBS variant, so I’m not the only one seeing the potential.
>
> .Concrete security of the protocol
> Suggestion 4: understand the security and efficiency trade-offs with PS signatures
> Suggestion 5: better describe the security guarantees in the draft
>
> In the algebraic group model:
> (1) BBS signatures are tightly secure under the q-DL assumption where q is the number of signing queries.
> (2) PS [PS16, Orru24: Thm. 7] signatures are tightly secure under the 2-DL assumption (3-DL for keyed-verification)

I'm having trouble hunting down the references here.

> Given the differences in best-attacks for these schemes, why choose (1) if (2) offers stronger guarantees? This isn’t to discredit the authors' hard work; I support their efforts, but I want to challenge the reasoning. If the response is "BBS is more efficient," then what is the actual efficiency gain for 1-5 attributes with equivalent security levels? I’ve only seen comparisons that don’t align with the spec. Shouldn’t we inform implementers about best-attacks, like in [rfc9497, Sec. 7.2.3]?
>
> .Blind BBS multiplicative blinding
> Suggestion 6: add multiplicative blinding for Blind BBS.
>
> Currently, the spec defines a valid BBS signature as a pair (A, e).
> Instead, blindly issued BBS signatures are a triple (A, e, s) where s is called secret_prover_blindand is an extra element of the message array. It's part of the message, but also implementations MUST never reveal it, lest the user will lose anonymity.
> This is inconvenient because:
> A-1. It's part of the message but requires special handling
> A-2. requires a new group generator
> A-3. adds one extra element of which we must know upon every presentation, even if not needed
>
> It is possible to have "blind BBS" as a pair (A, e) consistent with the signature using multiplicative instead of additive blind. This has been already done by Durak, Marco, Talayhan, Vaudenay [DMTV24] and myself [Orru24].
> To do so,
> 1. the user selects a secret_prover_blinduniformly distributed in the scalar field as before,
> 2. the user computes B = (1/secret_prover_blind) * (P1 + Q_1 * domain + H_1 * msg_1 + ... + H_L * msg_L + J_1 * msg_1 + ... + J_M * msg_M)
> Note that here we're committing to the public and private messages, and then blinding them with 1/secret_prover_blind
> 3. the user computes the user proof proving that Q_1 * domain + H_1 * pub_msg_1 + ... + H_L * pub_msg_L = secret_prover_blind * B - (J_1 * msg_1 + ... + J_M * msg_M)
> 4. the server computes A' = B * (1 / (SK + e))
> 5. the user unblinds A'via A = secret_prover_blind * A'
>
> This has some disadvantages:
> M-1. requires the user to be aware of the server (signer) messages in order to issue a signing request.

I don't understand what this means. What server messages? Why is this
different than additive blinding?

> This disadvantage seems to me "manageable", and in fact much better than the alternative of carrying around a value that will uniquely identify the user.

In some cases like PRF keys for rate limiting we have high entropy
credentials that mean the commitment opening is identifying anyway.

>
> Although it is not possible to have the server set attributes of the user, it is possible to have the server re-randomise user attributes, which is a desirable feature in many cases. See [Orru24, Figure 10] as
> blind_factor = secret_prover_blind * rnd_signer_msg_i + rnd_prover_msg_i
> where rnd_signer_msg_i is contributed by the signed and added to the commitment upon signing, and rnd_prover_msg_i is contributed by the user.
> I would argue that I'd never want the user to accept a signature without knowing what's up with the public attributes. What is the user supposed to do if, as a malicious issuer, I put your passport number as a public attribute? Are you going to just silently accept, complain and ask me once again?
> This is also part of a separate point that I will make later about the API.

I'm confused: the commitment doesn't have any private or public
messages. That's all done at proving one has the commitment.
>
> The Privacy Pass working group had to face a similar problem already: for VOPRFs we have a similar problem where additive and multiplicative blindings provide different features, and they do mention both options in the spec.
> I think this might be useful also for BBS signatures.
>
> .Blind BBS API design
> Suggestion 7: describe the behaviour of the user/prover with respect to attributes set by the server.
> Inconsistency: Commit is capitalised, verify_commitment is not.
> Suggestion 8: separate zero-knowledge proofs from the scheme.
>
> The functions Commit/verify_commitment are at the same time computing the message request and the representation proof for the server.
> I think it would be more helpful to have it separate for the following reasons:
> - readability. For me, it was hard to understand where the zero-knowledge proof is starting and the user commit ends.
> - 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
> - extensions built on top. If the user needs to prove that one of the attributes was authenticated from another credential this makes the thing more messy than it should.
> It would be instructive to have a description of what is being proven, possibly in Camenish-Stadler notation.
> It would be helpful to have ProofChallengeCalculate provide some information on what parts can be pre-processed (similarly to BIP340).
>
> The spec currently does not specify what the user should do when a "server" attribute (a public metadata attribute) is unexpectedly set by the server. This is potentially harmful to anonymity, the user shouldn't just accept everything that makes a signature verify.
> I tried to find also information there about public metadata, and how it's handled in this case, but haven't found anything under the keywords Token Challenge, Attestation information, Origin information. Maybe @Christopher Wood can help us understand? If we copy from what they do, you're not wrong I guess..
>
> .On the zero-knowledge proofs
> Suggestion 9: simplify Fiat-Shamir and have a generic framework for future proofs
> Suggestion 10: make proofs extensible with arbitrary statements
>
> This is a more general comment for the CFRG.
> We currently have the following RFCs, drafts, and external initiatives, all using Sigma protocols + Fiat-Shamir:
> rfc8235 Schnorr Non-interactive Zero-Knowledge Proof
> rfc9497, section-2.2 Discrete Logarithm Equivalence Proofs
> draft-irtf-cfrg-bbs-signatures (this draft)
> draft-ladd-privacypass-bbs
> MPTC, C2.7: ZKPoK: ZKPoK of private key
>
> If I think about what a standard should provide I think about (1) interoperability, (2) security, (3) quality.
> Currently, we have all these instantiations of Schnorr proofs that implement the same proof system, but implemented slightly differently for a specific statement. Unfortunately, they are at best not interoperable, and at worst exposing implementers to weird reuse attacks.
> Specifically for this RFC draft, we're weighing whether the authors properly handled Schnorr and Fiat-Shamir, which they shouldn't have had to do in the first place.
> A potential example is that BBS in the keyed-verification setting requires a server proof. The server proof is a DLEQ proof, just like in rfc9497, sec. 2.2.
> I am persuaded that the BBS specification should only describe the representation proof to be shown, and have them handled by a separate specification.
> BBS extensions should be able to add "rows" to those statements to be proven.
>
> In the actual state, because BBS can't be a spec about everything, we're limiting the scope of what BBS signatures can do to selective disclosure of messages, which is woefully insufficient for concrete applications (for instance, it is for rate-limiting and pseudonyms).
> Is the CFRG of the same view? Would you be open to helping an effort on Fiat-Shamir (useful also for post-quantum primitives) and Sigma Protocols?

I strongly agree with this statement. I'd like to be able to reuse
this draft in the privacy pass one via composition with a sigma
protocol / Camenish-Stadler to prove equations about attributes and
link to range proofs, but I can't because of the absence of this
structuring. However, I do think we need to get something out here,
and waiting for another document might not be wise. Perhaps we can
understand that this doc is it for BBS, and let Privacy Pass go forth
and build its own thing vs. needing to come back for every little
crypto change.

Sincerely,
Watson
>
> Best,
> --
> Michele.
>
>


-- 
Astra mortemque praestare gradatim