[CFRG] Review of BBS Signatures draft-07

[Julia Hesse <[e-mail]>]

Hi all,

here is my review of draft-irtf-cfrg-bbs-signatures-07. I did not 
implement the draft, so this is only a "theorists" review.

***
I have been struggling with reviewing this draft and in particular 
verifying the security of the described protocol. BBS signatures have 
been continuously evolving in the cryptographic literature, and their 
selective disclosure proofs are relatively complex - certainly not the 
easiest protocol suite to write a specification for. So before diving 
into the detailed comments that always have a negative touch, I'd like 
to say kudos to the authors for tackling this complicated task.

The draft seems to specify algorithms similar to those in [TesZho23]. 
The signing algorithm is close to their Fig. 3. For the proof algorithm 
I was not able to match that to any of (1) the proof described in the 
main body of [TesZho23], (2) their appendix version proposed by Andrew 
Whitehead, or (3) their appendix version proposed by Vasilis Kalos. It 
certainly did not help me that the draft is using additive notation 
while the paper is, as probably most cryptographic papers, using 
multiplicative notation.

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.

Technical comments and questions
---
What is the motivation of computing e as hash of SK and the messages, 
instead of drawing it uniformly? The result is that a signer always 
produces the same signature for the same message set - I fail to see the 
application benefit here.

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

Regarding the functions from [RFC9380], why is expand_message not 
described in Section 1.2 but hash_to_curve is?

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.

3.2 mentions utility procedures but does not further explain their role, 
as it does for core operations and Interfaces.

Proof unlinkability: the draft claims that "a BBS proof is unlinkable 
against both the Verifiers and the Signer", meaning that it is not 
recognizable whether two proofs were generated from the same signature. 
But for verification, the header, which is tied to a signature and 
chosen by the signer, is required. This means unlinkability only holds 
modulo headers, i.e., one cannot link proofs generated from signatures 
*with the same header*. This is a very restricted form of unlinkability. 
While Section 5 discusses potential threats to unlinkability, it does 
not mention headers. And in any case, I don't think that one should make 
the statement that proofs from signatures with headers, as described in 
this draft, are unlinkable. For example, if one follows the 
recommendations of 6.4, the proofs become fully linkable.

Beyond the issue with headers breaking unlinkability: 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.

What is the motivation behind signing an empty message?

Section 3: there is a lot of forward referencing: interfaces are defined 
using so far unspecified core functions, and core functions are defined 
using so far undefined utility functions. I'd suggest to turn around the 
order: first describe the utility functions, then the core ones, and 
then the interfaces.

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?

Section 6.9 "[CRQC] adversaries will not be able to compromise the data 
confidentiality property of a BBS signature - I don't understand how 
this can be true. E.g., if I have a signature (A,e) over one message m_1 
generated from PK, I use my quantum computer to pull SK from PK, then 
compute a*(SK+e)-P1-Q1*domain. Computing the dlog of that to the base 
H_1 will then give me m_1.


Nits
---
zero-knowledge, proofs-of-knowledge of... -> zero-knowledge proofs of 
knowledge of... (twice)

revealing no-information -> revealing no information

Note, the... -> The

For sets I and J, denotes -> Denotes the difference of two sets I and J, 
i.e.,...

is not a valid output of -> is not in the image of

... 3.6), expect -> 3.6) expects

3.3.1:
In definition of this signature scheme -> For defining BBS signatures
based upon -> regarding
pairing cryptography based -> pairing-based
in the case of this scheme -> in case of BBS signatures
in-efficient -> inefficient
the scheme is limited... -> this draft limits to BBS signatures where...

sub-group vs subgroup, octet-string vs octet string - decide on one

BBS proofs, which was -> BBS proofs which were

ciphersuite and and -> ciphersuite and

"H2G_HM2S_"is -> " is (appears multiple times)

creates BBS proof -> creates a BBS proof

compine -> combine

confidenciality -> confidentiality
***