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

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

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.

*.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
<https://www.rfc-editor.org/rfc/rfc9576>.*

By "tokens", I mean blind signatures and anonymous tokens in the way they
are being used in rfc9576 <https://www.rfc-editor.org/rfc/rfc9576>.
Fact #1: Tessaro and Zhu [TZ23 <https://eprint.iacr.org/2023/275.pdf>, Thm.
3] showed that Blind BBS without the user proof (commitment_with_proof without
proof) is one-more unforgeable.
Fact #2: Barki et al. [BBDT16
<https://link.springer.com/chapter/10.1007/978-3-319-69453-5_20>] 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
<https://www.rfc-editor.org/rfc/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 <[e-mail]> 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 <https://eprint.iacr.org/2015/525>, Orru24
<https://eprint.iacr.org/2024/1552.pdf>: Thm. 7] signatures are tightly
secure under the 2-DL assumption (3-DL for keyed-verification)
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
<https://datatracker.ietf.org/doc/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
<https://eprint.iacr.org/2024/711>] and myself [Orru24
<https://eprint.iacr.org/2024/1552.pdf>].
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.
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.

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
<https://eprint.iacr.org/2024/1552.pdf>, 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.

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 <[e-mail]> 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 <https://datatracker.ietf.org/doc/html/rfc8235>Schnorr
Non-interactive Zero-Knowledge Proof
rfc9497, section-2.2
<https://datatracker.ietf.org/doc/html/rfc9497#section-2.2> Discrete
Logarithm Equivalence Proofs
draft-irtf-cfrg-bbs-signatures (this draft)
draft-ladd-privacypass-bbs
<https://datatracker.ietf.org/doc/draft-ladd-privacypass-bbs/>
MPTC <https://csrc.nist.gov/projects/threshold-cryptography>, 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?

Best,
--
Michele.