Is it possible to de-anonymize user in RSA blind singing without knowing the random blinding factor only?

For example, in case of using RSA blind signing in E-Voting protocol: Is it possible to trace (Sx, x) to (Sb, b) if Signer and Tallier is the same person?

In this case, attacker has access to: blinded message b, signing of blinded message Sb, private and public key that allows to sign and verify messages, original message x and signing of the original message Sx. The only thing attacker don't know is the random number r that used by Bob to blind original message b=blind(x,r)

Is it possible to trace (Sx, x) to (Sb, b) if Signer and Tallier is the same person?

No (assuming that the blinding factor was chosen uniformly at random).

Here's how RSA blinding works: to sign a padding message $$m$$, Bob selects a random value $$r$$, and sends $$r^e \cdot m \bmod n$$ (where $$e, n$$ are from the public key). Then, the signer computes $$(r^e \cdot m)^d = r \cdot m^d \bmod n$$ (and then Bob completes the process by computing $$r^{-1} \cdot (r \cdot m^d) = m^d$$)

The point is that, (ignoring the trivial probability that either $$m$$ or $$r$$ is not relatively prime to $$n$$) then $$r^e$$ can also be any value, and so for any possible message $$m'$$, there exists an $$r'$$ such that $$r'^e \cdot m'$$ is consistent with the values the signer gets from Bob. That is, the value Bob passes to the signer gives no information at all (from an informational standpoint) about the message being signed, and this is true even if the signer has arbitrarily large amount of computational resources capability.

This includes any information that Tallier could use to link a vote with a signer.

Note that I started this off with 'the blinding factor was chosen uniformly'; if not, for example, there are values $$r$$ that Bob will never choose, then the signer might be able to learn something (possibly what values Bob is not signing)

• If signer knows $S' = r \cdot m^d \bmod N$, can he also calculate $m^d \bmod N$ (because signer knows $m$ and $d$) to find $r$? Aug 25 '21 at 13:21
• @Serbin: if the signer/tallier already knew that Bob cast that vote (and hence knows $m$), then yes, he could compute $r$ (not that that's important for the argument; it'd hold even if that were difficult). This is not an attack on anonymity, as this assumes that the signer/Tallier already broke that. And, if they were wrong (if Alice actually cast that vote), then they could recover an $r$ that would have been what Bob used had he cast the vote, and they get no indication that Bob did not actually cast that. Aug 25 '21 at 13:28
• Tallier receive $m$ and $S$ from anonym user. Tallier can calculate $x = m^d \bmod N$ for received request. On the Signer side, they secretly store all incoming $m'$ and outcoming $S'$ pairs. If we will iterate over all signed $S'$, can we find $r$ (for example as $r = S' \cdot x^{-1}$)? As verification we can use $m' = r^e m \bmod N$. Aug 25 '21 at 13:41
• @Serbin: they certainly can - however the verification step will always say 'it's consistent' (whether that's Alice's vote or it's Bob's); if we have an arbitrary $x, m$ (Bob's vote with $x^e = m$) and $m', S'$ (Alice's blinded vote with $S'^e = m'$), we can still compute a value $r = S' \cdot x^{-1}$ and find that $r^e m = S'^e x^{-e} m = m' m^{-1} m = m'$. and so the equation holds, even though Bob didn't cast that vote Aug 25 '21 at 14:10
• Here is the code that computes secret $r$ if Tallier and Signer are the same person: onecompiler.com/python/3x9hgtzyg It looks like the separation of Signer/Tallier systems is a prerequisite for blind signing. Aug 25 '21 at 21:03