Definition of anonymity in blind signatures: does the attacker control the input messages?

The recent #2023-077 paper proposes a lattice-based blind signature. In Sec. 2, they propose the following definition of anonymity for blind signatures:

The paper they refer, #2021-1565, also proposes a lattice-based blind signature, but it relies on a different definition of anonymity for blind signatures:

Another lattice-based blind signature protocol, #2022-834, uses a similar definition with attacker-controlled messages.

Crucially, the two definitions differ in the source of the messages to be signed: in #2021-1565, the messages are chosen by the attacker, while in #2023-077 the definition holds “for every two messages”, which suggest that the attacker does not know the messages.

The two definition seem to be quite different, as it is easy to imagine a protocol that is apparently secure wrt one definition but not the other. Indeed, with the #2023-077 definition, it’s sufficient for the signer not to extract the original messages, while with the #2021-1565 definition, the signer should not be able to link the final signature to any protocol execution.

So, have I misunderstood something and the two definitions are actually equivalent? Or if not, are there consequences in terms of blind signature applications, and is one definition more commonly used?

The first definition says “for any adversary and any pair of messages, …”
So, in particular, it holds for any adversary that has the messages baked in. I.e., one can assume that the adversary knows the messages.

It doesn’t make a difference whether the messages are chosen by the adversary or if the definition holds for any pair of messages, because if there exists an adversary that is allowed to pick the messages and wins, then there is also an adversary that wins for some fixed messages (obtained by fixing the random bits). And then we would break the second definition.

However, there is a difference between the definitions: the second definition is weaker because it assumes the public key is generated honestly. In the first definition, the public key is generated by the adversary.

1 Like