Differentiation or Not Between Prover and Signer Messages

[Wind4Greg]

Blind BBS signatures support what are called "partially blind signatures" where the signature issued by the signer covers "blinded messages" from the Prover as well as "non-blinded" messages from the Signer. Since BBS provides for selective disclosure the Prover selects a subset (including none) of all these messages to reveal to the Verifier.

Two mutually exclusive features related to privacy/security of the resulting BBS proof are possible: (a) the Verifier knows which of the signed disclosed messages that it receives comes from the Prover and which come from the Signer, or (b) the Verifier cannot determine which messages are attributable to the Prover or the Signer, i.e., they only know that the messages are signed and come from either source.

For two prime applications of Blind BBS signatures (in a credential context) (1) "anonymous holder binding", (2) BBS pseudonyms, the verifier needs to be assured of which messages came from the Prover and which from the Signer. However, this may not be the case in all applications and this issue opens a discussion on how both "differentiation" and "non-differentiation" of message source could be achieved.

Technical Background

BBS signatures and related BBS blind commitment are based on combining "messages" with generators. For Blind BBS this involves generators for the Prover and the Signer to use with their respective messages. Two fundamental approaches:

1. A "single set of generators" used by both Prover and Signer, i.e., generated with a call to BBS.create_generators(generators_number, api_id) using one api_id and having this list of generators divided between the Prover and the Signer.
   1. Simple if the number of messages and committed messages is well know and fixed for an application.
   2. More complicated for the Signer if the number of prover messages can be very large and variable (per Prover).
   3. No Differentiation between Prover messages and Signer messages. Feature or Bug depending on application needs. Verifier will not know which came from Prover versus Signer.
2. Two "sets of generators" one for use by the Prover in committing messages and one for use by Signer for "signer messages". These are generated with calls to BBS.create_generators(generators_number, api_id) with two different api_ids.
   1. Signer and Prover "generator spaces" are kept separate, i.e., Prover cannot influence generators used by Signer for signer messages.
   2. Signer will know number of prover messages if receives and verifiers "commitment with proof" so the number of Prover messages is not hidden.
   3. Verifier must know the number of Prover (committed) messages to create both sets of generators (it gets the total number from the proof).
   4. Prover committed messages and Signer messages clearly differentiated, i.e., the Verifier knows which disclosed messages came from the Prover compared to Signer. This is a Feature or a Bug depending on application.
   5. Current Blind BBS Applications (a) Anonymous Holder Binding, and (b) Pseudonyms are based on this differentiation. These are based on non-disclosed secrets known to the Prover and not the Signer. In addition for Pseudonyms the list of secrets can be of variable size per signature.

Current API

BBS Core operations and Blind BBS core operations are agnostic this approach since they take "generators" as parameters. The following summarizes the current API with key function calls.

Prover

Prover knows how many committed messages but may not know how many messages, i.e., signer provided messages. prior to receiving blind signature from Signer.

• Commit(committed_messages, api_id)
  • CoreCommit(committed_message_scalars,blind_generators, api_id)
• VerifyBlindSign(PK, signature, header, messages, committed_messages, secret_prover_blind)
• BlindProofGen(PK,signature,header, ph,messages, committed_messages,disclosed_indexes, disclosed_commitment_indexes, secret_prover_blind)

Signer

May or may not know ahead of time how many committed messages from prover. Gets number of committed messages from the commitment_with_proof data. Uses this to create blind generators in validation of commitment. All generators are used in the domain computation (BBS core).

• BlindSign(SK, PK, commitment_with_proof, header, messages),
  • generators = BBS.create_generators(L + 1, api_id)
  • blind_generators = BBS.create_generators(M + 1, "BLIND_" || api_id)
  • deserialize_and_validate_commit(commitment_with_proof, blind_generators, api_id)
  • B_calculate(generators, commit, message_scalars)
  • FinalizeBlindSign(SK, PK, B, generators, blind_generators, header, api_id)
    • BBS.calculate_domain(PK, Q_1, (H_1, ..., H_L, J_1, ..., J_M), header, api_id) where Q_1, H_1 to H_L are from the generators, and J_1 to J_M are from the blind generators.

Verifier

The total number of messages comes "encoded" in the proof. To verify the proof a full set of generators (generators used by signer, and blind generators) is needed by the verifier. When using "separate" generator sets the number, L, of blind generators must be furnished as in the API below.

• BlindProofVerify(PK, proof, header, ph, L, disclosed_messages, disclosed_committed_messages, disclosed_indexes, disclosed_committed_indexes)

[wbl]

I don't understand why the Verifier knowing what the Signer as opposed to the Prover picked in the signed message matters. Surely the Signer does some zero knowledge proof verification to determine whats where.

This doesn't really compose with the direction we've been going in the AntifraudCG or PrivacyPass, which is unfortunate.

[Wind4Greg]

Hi @wbl I'm coming from the verifiable credential use case where we are using Prover (Holder) secrets for "binding" and "pseudonyms". We wouldn't want the Prover to be able to misrepresent/substitute part of the "credential" (messages from the Signer) with their own messages.

Yes, the Signer would verify via ZKP what the Prover committed.

As cryptographic primitive we can have Blind BBS work in either or both of the ways mentioned above. I don't, however, have an application for the case where the "messages" from Prover and Signer are not "differentiable". If you have such an application please describe it here and we can use it to motivate changing/generalizing the API. If you can explain how this relates to the AntifraudCG or PrivacyPass that would be great. Are those full three party models? I though they were two party models and not requiring full BBS functionality.

[wbl]

Let me make this more concrete:

We have a commitment $C=g^s{h_1}^{m_1}{h_2}^{m_2}\ldots{h_n}^{m_n}$. Some of the $m_i$ are "from" the Signer, some "from" the Prover. But there is no reason to use different $h_i$: the signer could always require the Prover to demonstrate that any subset of the $m_i$ has whatever desired values the Signer wants to give during the process of validating the ZKP required for the signature to be secure.

I don't understand what I think is in your proposal: the desire to separate the $h_i$ into two sets, one for some kinds of message and one for others. It feels to me to be unnecessary complexity that ends up infecting the rest of the system when you just need to worry about issuance.

As for Privacypass the problem is that the approach in these docs of have an explicit algorithmic description for each extension vs.use a more generic ZK thing forces writing a lot of text each time, and we're going to be behind in readiness, so only the more generic approach would preserve ability to use these.

[Wind4Greg]

Hi @wbl, hopefully we can get @BasileiosKal to comment since the current approach with two separate sets of generators was developed quite a while ago. As you say the BBS core and the commitments just works with generators regardless of whether they are created as two sets or a single set. The core functions of BBS can work with either. My application requires knowing which generators and messages go together and this can be achieved in either approach.

It my recollection that the current approach was taken to ease the burden of the Signer but @BasileiosKal will have to remind us of this.