Score:1

Crypto

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

Serbin

12/25/22, 11:32 AM

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)

1 + 0

rsa

blind-signature

Score:2

Crypto

poncho

12/25/22, 1:09 PM

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)

0 + 9

Serbin

12/25/22, 1:21 PM

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$?

poncho

12/25/22, 1:28 PM

@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.

Serbin

12/25/22, 1:41 PM

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$.

poncho

12/25/22, 2:10 PM

@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

Serbin

12/25/22, 9:03 PM

Here is the code that computes secret $r$ if Tallier and Signer are the same person: https://onecompiler.com/python/3x9hgtzyg It looks like the separation of Signer/Tallier systems is a prerequisite for blind signing.

poncho

12/25/22, 9:08 PM

@Serbin: does it compute a plausible-looking $r$ on a wrong guess (Alice did the blinded signature, but Bob submitted the vote you are looking at)? If it does, how does it indicate whether the guess is incorrect; that is, Alice wasn't the one who submitted the vote in question?

Manish Adhikari

12/26/22, 7:36 AM

Poncho already told you the details but start like this, the whole point of blind signatures is to prevent what you are asking. If I ask a signer to sign two blinded messages and later give the same signer unblinded message and signatures in any order (The signer has got the private /public keys and both the blinded and unblinded message and signatures), the signer should not be able to tell whether the order is switched or not. RSA blind signatures as Poncho told you already is information theoretically unlinkable.

Manish Adhikari

12/26/22, 7:38 AM

the signer should not be able to tell whether the order is switched or not* significantly better than random guess, I missed this part

Serbin

12/26/22, 7:30 PM

Yes, indeed, this is impossible.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: เป็นไปได้ไหมที่จะยกเลิกการระบุชื่อผู้ใช้ในการร้องเพลงตาบอด RSA โดยไม่ทราบปัจจัยที่ทำให้ไม่เห็นแบบสุ่มเท่านั้น

RO: Este posibil să dezanonimizați utilizatorul în cântatul orb RSA fără a cunoaște doar factorul de orbire aleatoare?

RU: Можно ли деанонимизировать пользователя в слепом пении RSA, не зная только случайного фактора ослепления?

VI: Có thể hủy ẩn danh người dùng khi hát mù RSA mà không chỉ biết yếu tố mù ngẫu nhiên không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.