Domain separation of generated signatures

[tplooker]

At the moment within the scope of this specification there are several points of extension, such as

• How messages are mapped to their appropriate scalar values
• How the generators used to commit each message are created (e.g from a global, issuer specific or signature specific seed)

Many of these above decisions will be limited or at least formally defined in a concrete ciphersuite to promote interoperability. However with multiple possible cipher suites overtime that make different choices, how do we ensure that a signature generated under one cipher suite is not confused with one generated under another cipher suite.

One proposal to limit the possibility of this occurring is to define that the first message in a BBS signature MUST always be revealed further more this message could contain a range of information OR something more limited like a cipher suite identifier. As raised by @BasileiosKal on the call, putting too much information in this revealed message is likely to create a correlation risk that would erode some of the benefit that BBS signatures provide, so perhaps a better middle ground would be to instead encode the cipher suite identifier (e.g for the current BLS12381 cipher suite in the spec this could be the hash scalar produced from the string BBS_BLS12381G1_XOF:SHAKE-256)

[mikelodder7]

If you do this approach you can no longer link messages across signatures anymore. The better approach which the original paper says is to use unique generators per signer or as we've started calling it local create generators based on the signers public key.

[tplooker]

@mikelodder7 can you please elaborate on how this is the case, the preferred proposal is merely to have the first message be a protocol identifier? I dont see how this would prevent cross signature?

[tplooker]

Local generators would still not fully address the security concern described above, for example as a holder or verifier I would not know which message mapping methods are being used in the cipher suite so a malicious party could use this to attack in certain scenarios

[mikelodder7]

If each message is mapped differently to a scalar per issuer then that means my name will not map to the same value in two different signatures and therefore I can't prove they are equal.

[mikelodder7]

If you want a correlating identifier then why even use BBS+?!?

[mikelodder7]

It solves the problem because local generators are unique per signer therefore the commitments are different and serve the same purpose as the cipher suite.

[tplooker]

Mike I think you are miss reading the actual proposal here e.g the first message is simply just the scalar mapped representation of the cipher suite id BBS_BLS12381G1_XOF:SHAKE-256, this is not correlating nor negates the ability to prevent cross signature linking.

[tplooker]

Further more as I said above signer specific generators alone would not address the security concern about how different cipher suites may elect to support different message mapping procedures

[mikelodder7]

I understand it better now. Thanks. That helps to clarify it.

[tplooker]

@mikelodder7 great, would you support such a proposal?

[BasileiosKal]

+1 from me. I do like the proposal.

I may prefer the domain separation string to be an optional parameter of the sign, verify etc functions, so we would avoid saying that the first message MUST always be revealed, which may be confusing (for clarity, i would prefer the input list of messages to be just the attributes the issuer wants to sign). This way, if the prover and the holder have already agreed on what cyber suite to use, it will not be necessary for the prover to actually "reveal" that message since the verifier will already "know it".

[tplooker]

Agree, in a practical sense I would expect the sign and verify APIs would take the cipher suite id as a seperate parameter rather than as the first message, that way it is clear it wouldn't actually have to be communicated to another party as the expectation is that this is communicated at a higher level similar to the DST.

[tplooker]

To me the proposal is clear, so I will submit a PR to further the conversation

[andrewwhitehead]

I think it would be better to calculate this domain separation message in the same way as the challenge, using all the parameters that need to be enforced to avoid malleability which aren't going to vary at the time of presentation. This value would likely be cached by the prover. It may or may not be provided by the issuer at the time of issuance, I think generally it would be unless trying to save a minuscule amount of bandwidth. The inputs should include at least:

• the cipher suite (and by extension the hash function and curve details)
• the issuer's public key (to avoid issues such as Correspondence between proof and public key #85)
• the number of signed messages
• the generator points used, in a standard order

NB that the last two are necessary if the generators are not always deterministically generated from the issuer's public key and the number of messages, as they were in the earlier text. This leaves only a few things to hash into the presentation challenge:

• A', Abar, D, C1, C2
• the revealed message indices and values (see Adding the revealed messages to the chalenge to avoid forgery #74), including the value of the domain separation message – and by extension the values above
• the presentation nonce

The domain separation message could optionally include a byte string containing application-specific scope information. This would probably be the place for things like a schema identifier or revocation registry identifier (required-revealed attributes), and could be used to discriminate signatures that are meant to be bound to a specific session (adding a signature nonce).

[BasileiosKal]

Regarding the generators, couldn't the Verifier "validate" them using the global seed?? Other than that its a +1 from me.

Also I think we must update the blindSignatures extension to accommodate these changes. I imagine that in the extension the number of signed messages etc., will also have to take into consideration the blinded messages and so on.

[tplooker]

Regarding the generators, couldn't the Verifier "validate" them using the global seed?? Other than that its a +1 from me.

This is a good question to me, if the cipher suite always fully defines the generators then I can see how perhaps this inclusion could be redundant, however if someone were to define a BBS signature cipher suite that uses signature specific, random or issuer specific generators then maybe it becomes useful to have these protected through the integrity of the signature?

Also I think we must update the blindSignatures extension to accommodate these changes. I imagine that in the extension the number of signed messages etc., will also have to take into consideration the blinded messages and so on.

+1 to this too I will open an issue to track more generally that we will need to revise the blind signature extension draft to be consistent with the core draft.

[andrewwhitehead]

It's possible that the generator values could be left out, for now at least I'm erring on the side of caution and adding them.

[tplooker]

It's possible that the generator values could be left out, for now at least I'm erring on the side of caution and adding them.

Could you elaborate on the potential concern here?

[tplooker]

This is a good question to me, if the cipher suite always fully defines the generators then I can see how perhaps this inclusion could be redundant, however if someone were to define a BBS signature cipher suite that uses signature specific, random or issuer specific generators then maybe it becomes useful to have these protected through the integrity of the signature?

Just another thought here, maybe what is actually featured in this message is the cipher suite id + an additional data structure, where the structure and contents of which is dictated by the cipher suite itself? So for ciphersuites like the current one in the spec we dont have to include all the generators because they are fixed (e.g derived from a global seed) whereas another ciphersuite would be free to include them in the additional data structure if they saw benefit?

[tplooker]

So for example for the current ciphersuite we could define that the additional data structure just contains the public key and number of signed messages.

[BasileiosKal]

It may be a little confusing as to why we allow generators to be included in the additional data structure (if we document the possibility somehow) since we don't allow ciphersuits to define their own generators. This is also related with the discussion in #68, but even if we allow ciphersuits to define the generators seed, it will be no different from the situation with the current ciphersuits (i.e., the validity of the generators could be derived from that seed).

Also it may be hard to define in the ciphersuits which generators to add to the "signature domain separation" since their exact number will most likely not be known. In contrast, at signing time, the issuer will know exactly which generators they will use. As an alternative we could perhaps add the seed value.

It's possible that the generator values could be left out, for now at least I'm erring on the side of caution and adding them.

I imagine It is more secure since the verifier will be "forced" to "check" the correctness of the generators every time, otherwise it will be left on the verifier to do the check if they want to. I'm not opposed to that, since i don't imaging it will raise complexity, though i don't see the requirement changing if the generators are derived from the issuers pk, or a specific requirement to do so now.

[andrewwhitehead]

If the generators depend only on the seed value, then yes we can hash that instead and be more efficient. Maybe we should add security guidelines for ciphersuites to ensure agreement over the generators in the event that they do use a custom setup procedure.

[BasileiosKal]

Agreed. IMO we should make the generators only depend on a seed (which could also be the signers pk). Ciphersuites could define their own seeds if they want to. I don't really see a requirement to allow ciphersuites to define their own generators all together, which is also less secure. That said we should also define the security requirements of the generators, even if we only allow ciphersuit specific seeds.

[mikelodder7]

Yes it should be part of the common reference string (CRS). That way if they do define their own generators (like just picking them at random) we allow for it. The seed should be the safest and most compatible approach

[tplooker]

Addressed in #95, closing.