Named message generators

[andrewwhitehead]

I'm finding that it would be beneficial to define generators more generally, instead of just having H_0 for blind signatures and H_1 ... H_n for indexed messages. Extensions to the BBS signature scheme may want to reserve one or more message indexes for particular purposes (wallet binding, revocation, etc), but this leads to conflict when multiple extensions are used at once. You would likely need to define a new signature scheme for every supported combination in order to specify what message indexes are used for what purpose.

Instead, I believe we can define special-purpose message generators which have unique identifiers rather than indexes. You can also think of these as 'unordered' generators, with standard usage that is consistently defined across various credential schemas. A few potential uses that I've identified:

• a 'linked secret'/'wallet binding' generator for preventing use of credentials without the secret (Indy's use case)
• a 'device binding' generator (for a secret value that can be authenticated as generated by a trusted module)
• revocation entry and revocation group generators for linking to an accumulator or other revocation mechanism
• a schema identifier generator
• a credential ID generator
• a credential set ID generator (for a collection of credentials that can be presented in combination)
• a credential creation time generator
• a credential expiration time generator

We could also reformulate a couple things in these terms:

• H_0 becomes the 'blinded signature' or 'commitment' generator
• P1 could be replaced by a 'base point' generator - freeing it up to be used as a holder binding generator as in Holder Binding #37 (NB. in this case the associated message would always be 1)

These generators might be defined either specific to an issuer key or globally by adding a unique identifier to the hash-to-curve input. Some thought would be needed here to define the process exactly. For debugging purposes, messages tied to these generators might also be represented as a dictionary while numbered messages are represented as a list, for example:

{
  "revocation index": 1,
  "revocation group": "mydomain.com/users",
  "schema": "http://schema.org/Person"
}

[andrewwhitehead]

P1 could be replaced by a 'base point' generator - freeing it up to be used as a holder binding generator as in #37

In particular - this could be made into an issuer-specific (public key-specific) generator, potentially alleviating security concerns with the other generators being universal.

[tplooker]

@andrewwhitehead I really like the thinking here I agree there are many applications of generators within BBS signatures for special purposes. IMO in order to keep the core draft simple I think we leave operations that involve using generators with a contract like proposed in #64, put simply the core draft should not be aware of any specific application of a particular generator. Instead we can profile on top of the core draft a "bound" variant of the BBS signature scheme that defines the generator used for cryptographic holder binding and the likes

[BasileiosKal]

+1. This is definitely very usefully. An issue IMO is how we define those special purpose generators. Would the generators used for blind signatures be considered "special purpose" in that case?? If yes this would be more complicated than just defining specific use and identifiers for 5-10 generators. Finally, shouldn't we also try to define the "special" messages corresponding to those "special" generators??

One way could be:

1. define the core operations to act on any generator (as in PR Messages and generators notation update for readability #64 which as @tplooker mentioned leaves the core operations agnostic and hence simple). Since the operations will take as input a list of generators and not indexes or identifiers they will not know if the generator is special or not.
2. define the concept of messages "committed" using a generator (i.e., the concept of the mapping between the message and the generator, briefly touched again on PR Messages and generators notation update for readability #64).
3. define some special generators and the meaning of the messages "committed" with them (i.e., a message "committed" with special generator "special_generator_1" will represent the signatures expiration time etc.). This can be an extra section. No change will be needed in the core operations.

The generators used for blinding will not be considered "special", which avoids many complexities. @andrewwhitehead is this what you had in mind??

[tplooker]

The difficult complexity arises when we want to start tracking the allocation of ordinary message generators in certain contexts for special purposes, my inclination is to instead keep these seperate.

For instance we dont want a situation to arise where a prover tries to fool a verifier into saying here is a proof from a "bound" BBS signature where the first message is un-revealed but because that generator is used in the same way as "non bound" BBS signatures some other mechanism would have to be used by the verifier to disambiguate that they are truely looking at a proof generated from a "bound" BBS signature.

[tplooker]

The counter problem this creates is because the number of message generators is effectively un-bounded how do we ensure when we select "special generators" that they do not collide with message generators?

[tplooker]

This complexity gets even hard to solve for if we want to support arbitrary blind message signing but also maintain conceptually different generators (e.g a set of message generators and a set of blind message generators)

[andrewwhitehead]

+1. This is definitely very usefully. An issue IMO is how we define those special purpose generators. Would the generators used for blind signatures be considered "special purpose" in that case?? If yes this would be more complicated than just defining specific use and identifiers for 5-10 generators. Finally, shouldn't we also try to define the "special" messages corresponding to those "special" generators??

I probably shouldn't include the H_0 generator in this because it adds confusion, and that generator is used in the SPK (although I'm not sure at the moment why it isn't treated as a normal hidden message). It's fine to continue defining it as the zeroth indexed generator. And yes, the format of the messages committed with a particular "special" generator will need to be defined, but that can be specified in the same extension draft where the generator is named.

1. define the core operations to act on any generator (as in PR Messages and generators notation update for readability #64 which as @tplooker mentioned leaves the core operations agnostic and hence simple). Since the operations will take as input a list of generators and not indexes or identifiers they will not know if the generator is special or not.

I think I agree with this.

2. define the concept of messages "committed" using a generator (i.e., the concept of the mapping between the message and the generator, briefly touched again on PR Messages and generators notation update for readability #64).

Also makes sense.

3. define some special generators and the meaning of the messages "committed" with them (i.e., a message "committed" with special generator "special_generator_1" will represent the signatures expiration time etc.). This can be an extra section. No change will be needed in the core operations.

At the moment I think it would be best to define the general concept of 'extension generators' and how to create them independent of the curve being used (ie. hash a URI to a group element, perhaps), in the core draft. Then extensions to the BBS draft can simply say something like "define the credential index generator as an extension generator with URI http://...". Depending on uptake the implementations might cache certain generators that are frequently used. I don't think we need to add any specific instances of these generators to the core draft currently.

Naming-wise we could also distinguish between 'ordered' and 'unordered' generators.

[andrewwhitehead]

The counter problem this creates is because the number of message generators is effectively un-bounded how do we ensure when we select "special generators" that they do not collide with message generators?

We just need to select them randomly or based on a hash. The chance of collision is on the same order as with selecting a secret key, I believe.

This complexity gets even hard to solve for if we want to support arbitrary blind message signing but also maintain conceptually different generators (e.g a set of message generators and a set of blind message generators)

I'm not really sure what you're getting at here, the generators are the same in any case. It seems reasonable that the issuer will only accept commitments for certain known message generators depending on the protocol being executed.

Incidentally parties should never be sending message generators themselves, they should only be referred to or known implicitly.

[BasileiosKal]

At the moment I think it would be best to define the general concept of 'extension generators' and how to create them independent of the curve being used (ie. hash a URI to a group element, perhaps), in the core draft. Then extensions to the BBS draft can simply say something like "define the credential index generator as an extension generator with URI http://.../". Depending on uptake the implementations might cache certain generators that are frequently used. I don't think we need to add any specific instances of these generators to the core draft currently.

Ah ok, I think I understand better now. Thanks you! So the concept is to define an alternative way of creating generators, something like Hash2Curve(Hasher(GID), DST), where GID a special generator identifier??

Two things worry me though.

1. To @tplooker point, domain separation becomes very important for some of those use cases. We will not be able to define the necessary DSTs here though.
2. Applications should not be able to define their own generator identifiers (GID above). A URI could contain random or “random looking” elements. The prover could then try to convince the verifier that they supplied correct "special generator URIs". If those are not specified by some spec or profile, there is no way for the verifier to know that the random looking elements they contain are not maliciously formed (which will result to maliciously formed generators). the prover could perform "pre-image" attacks to create generators that would allow them to present proofs for messages they don’t have etc.

IMO if the definition of special generators does not raise complexity too much, it can be useful including it to the spec but only as a point that other profiles and specs can expand upon and we should make it clear that this is the case, i.e., that applications must not define their own special generators.

[BasileiosKal]

It seems reasonable that the issuer will only accept commitments for certain known message generators depending on the protocol being executed.

For blind signatures, I think there is benefit in allowing the use of any arbitrary generator, to support use cases like in issue #29 (and more specifically here) where a “message” generator for one signature could become a “commitment” generator for another.

Incidentally parties should never be sending message generators themselves, they should only be referred to or known implicitly.

Definitely. We must document that in the spec.

[andrewwhitehead]

For blind signatures, I think there is benefit in allowing the use of any arbitrary generator, to support use cases like in issue #29 (and more specifically #29 (comment)) where a “message” generator for one signature could become a “commitment” generator for another.

Technically any message generator can be used in a commitment. I'm just saying that from a business logic and security perspective the issuer should only be issuing blinded signatures in specific use cases, and the holder will basically be told what form the commitment should take. In fact all the cases I can think of work better with named generators than with positional ones, because they can better restrict the interpretation of the message – for example, as a linked secret, instead of just 'message 1'.

[BasileiosKal]

Right. So i guess the question i have (although this may be better discussed separately) is will the blind signatures extension define specific generator URIs to be used, i.e., only named generators, which may not allow the above use case but increase simplicity and security or will blind signatures be able to use any generator increasing flexibility, and leave the exact definition of the named generator URIs to another spec (like a profile or a registry)??

Regardless I think the concept of the "special" named generators is worth documenting in the spec. I do agree that many use cases will benefit from it. As i said applications should not define their own named generators but technically an Issuer could, as long as the verifier can validate that those named generators are as defined from the issuer. I would prefer to just say that only other specs can define URIs for named generators though (maybe even an IANA registry??). This also has the advantage that those specs can define the necessary DSTs.

[andrewwhitehead]

I don't think the blind signatures extension needs to refer to any specific generators except P1 and H0 or whatever fills that role. It could have a non-normative section about generator selection maybe. Another nice thing about the named generators is that you can compose multiple commitments more easily since they aren't sensitive to ordering, which might help in that particular use case. (I notice that the example of a separate attribute provider only hides the attribute value if it has a large range, otherwise the issuer could discover the value by testing.)

Agree that applications should not be defining their own named generators (or whatever we call them), I think it's more of an ecosystem-level concept, and it makes sense to me to have a registry for them. I'm not sure what kind of DST is required, maybe it should just be the BBS signature scheme identifier as with the current generators?

[andrewwhitehead]

Currently, I don't think any special mechanism for 'named' generator creation needs to be defined, as we can define everything in terms of CreateGenerators (see #71).

• The current generators (P1, H1, ... Hn) can be defined by CreateGenerators(PROTOCOL_DST, CORE_SEED, n+1)[0..n]. CORE_SEED would normally be a spec-defined global seed value, but could be the issuer public key for issuer-specific generators, or an application-specific value if desired.
• Extensions may define one or more seeds for their own generators, as well as usage details. For example a 'credential metadata' spec could define a seed which was a URI pointing at the specification. It would then outline that generator 0 for the given seed is used for the credential schema, generator 1 for the credential ID, and generator 2 for the issuance date in YYYYMMDD format.
• Using the same mechanism, the blind signature spec would define the s generator (currently H0) as CreateGenerators(PROTOCOL_DST, BLIND_SIGN_SEED, n)[0].

[andrewwhitehead]

As a further update following #70, it looks like there is no avoiding H0 so it would have to be defined in the core. In that case I think it should just be the 0th element of the CreateGenerators(PROTOCOL_DST, CORE_SEED, n+1) sequence (basically the same as now).

If we do decide to replace P1 (need to create a separate issue for this) then element 0 could be that base point, element 1 would be H0, and the message generators would be elements 2..n+1.

[BasileiosKal]

Even if we decide to change P1, It may be useful to define it in the core spec separately from the generators created from CreateGenerators (i.e., as its own "named" generator). That way, even if we move to issuer specific generators, P1 will not change (in all literature P1 is fixed).

[andrewwhitehead]

Closing as I believe this is allowed by the current spec, and the implementation becomes an application concern.