How secure is a blind signature?

Question

From Wikipedia:

Blind signatures can also be used to provide unlinkability, which prevents the signer from linking the blinded message it signs to a later un-blinded version that it may be called upon to verify. In this case, the signer's response is first "un-blinded" prior to verification in such a way that the signature remains valid for the un-blinded message.

This is a useful feature, no doubt. Continuing on the Wikipedia article, it considers message $m$ and blinded message $m'$, and states that:

$$m' \equiv mr^{e} \pmod N$$

Which means that the $r^e \pmod N$ part is what keeps the message a secret from the signing party.

How hard would it be for a signing party to link blind messages to later revealed un-blinded versions, by keeping a log of blinded messages that they sign. The Wikipedia article states that this is hard but does not specify why. It does however specify that an attacker could possibly use a blinded signature to get signatures for something different than what was signed, but that this could be mitigated by signing a hash instead. Wouldn't that break the unlinkability, as explained in this accepted answer?

Answer 1

How hard would it be for a signing party to link blind messages to later revealed un-blinded versions, by keeping a log of blinded messages that they sign.

Assuming that the $r$ values are chosen uniformly from the values $[1, N-1]$ relatively prime to $N$ (and kept secret, for example, zeroized after use), and none of the $m$ values are relatively prime to $N$, then it's impossible to link them later (and this does not rely on a computational assumption, but an informational one).

For any such array of possible messages $m_1, m_2, ... m_n$ in any order, and blinded messages $m'_1, m'_2, ..., m'_n$, there is a unique set of values $r_1, r_2, ..., r_n$ with $m'_i \equiv m_ir_i^e$. No set of values $r_1, r_2, ..., r_n$ are any more probably than any other, hence the server gets no information whether $m_1$ corresponds to $m'_1$ or $m'_2$ (or, for that matter, whether it was one of the values signed at all)

It does however specify that an attacker could possibly use a blinded signature to get signatures for something different than what was signed

What the Wikipedia article is worrying about is that the attacker can do other things with the 'blinded signature' facility other than signing messages. For example, if the RSA key is also used to encrypt messages, then the attacker could ask for a 'blinded signature', but instead decrypt a message. This blinded signature method really is an oracle to the RSA private operation, and there is no easy way to limit it to only generating signatures.

Wouldn't (signing a hash) break the unlinkability?

Yes (unless you do a lot of work with zero knowledge proofs). This simple blinded signature scheme relies on the idea that the server gets no information on the message being signed; once you give it some, things start being linkable. This could be worked around, however it's probably be easiest to use this RSA key for nothing other than signatures (and so there's nothing an attacker can do with the RSA oracle, other than generating signatures).