Anonymity problem after voting with blind signatures

In a distributed voting system (all the messages are public, but signed and maybe encrypted/blinded), having:

• $d$, $e$, $N$ — registrar key params
• $m$ — msg
• $r$ — random blinding factor
• $m'$ — blinded msg
• $sm'$ — signed blinded msg
• $sm$ — signed msg

When person received $sm'$ from the registrar, and unblinds it — he receives $sm$. He then sends it to the system anonymously for counting.

So, at the end registrar will have $sm$, and can read $m$.

Finally the problem

Registrar can in cycle try to do $sm'_i \cdot sm_j^{-1} \pmod N$ to find some $r_k$.
Then compare $m \cdot r_k^e \pmod N$ with with every $m'$.
If values match — person which sent $m'$ can be deanonimized as it is not hard for registrar to keep information about all $m'$ and linked persons.

It will take some time to process all the combination and depends of number of voters, but it works (tested simplest scenario).

Is there any mistake, or is it possible to overcome this problem with some trick?

• Are you using the same $r$ for different messages? – CodesInChaos Mar 17 '16 at 17:19
• $r$ is random secret for every voter. Only one message per voter (vote). – Inversion Mar 17 '16 at 17:40
• "Registrar can in cycle try to do $sm'_i \cdot sm_j^{-1} \pmod N$ to find some $r_k$" -- Can you explain why you expect this to have a higher success probability than generating a random $r$? – CodesInChaos Mar 17 '16 at 18:24
• Number of combinations is limited. For country like my with about 20E6 voters it is 4E14 combinations. Matching $m′$ can be done quickly with some index. Let every combination calculation takes 0.1 sec: 4E13 sec = 1'268'391 years. If there are 4 candidates and we need only voters for some specific ($sm$ lets us to pick) — 317'097 y. If computing is faster, like 0.01 sec — 31'709 y. If we use parallelization, maybe on x10 GPU with 2000 cores (not sure if those units are capable) — 1.5 y. With every match number of combinations is reduced (matrix halved) — 9 months. – Inversion Mar 17 '16 at 20:43
• Anyway, if some group will start to compare combinations right after the election finished — they can start to publish deanonymized vote every few hours (depending of luck) — it can be enough to discredit a voting system and turn people against it. – Inversion Mar 17 '16 at 20:44

The problem is, that you are actually checking a tautology and this is no danger to deanonymization. Let me explain it to you with a simple example of 2 signatures:

Lets say we want to blindly sign distinct messages $m_1$ and $m_2$ with distinct randomness $r_1$ and $r_2$.

Now during the blind signing you produce the transcripts (I omit $\mod N$):

$m_1'=r_1^e m_1$, $sm_1=r_1 m_1^d$ and $m_2'=r_2^e m_2$, $sm_2=r_2 m_2^d$

and the final message signature pairs are $(m_1,sm_1=m_1^d)$ and $(m_2,sm_2=m_2^d)$.

lets look at one case where you start from one of the final signatures, say $(m_1,sm_1)$ and check it against both transcripts of the blind signing process (and the second case is analogous due to symmetry):

$sm_1' sm_1^{-1}= (m_1^d r_1) (m_1^d)^{-1} = r_1$ and

$sm_2' sm_1^{-1}= (m_2^d r_2) (m_1^d)^{-1} = r_1'$

now you have two candidates and lets check it with every $m_i'$:

$r_1^e m_1 = r_1^e m_1 = m_1'$ and $(r_1')^e m_1 = ((m_2^d r_2) (m_1^d)^{-1})^e m_1 = (m_2^d)^e r_2^e (m_1^{-1})^{ed} m_1 = r_2^e m_2 = m_2'$

So, now you have checked all transcripts of the blind signing process against the signature of the first message and with your candidates you have found out that the first message corresponds to both transcripts with exactly the same probability. So you have learned nothing. As said above, the same argument (due to symmetry) applies to the other case and you can easily generalise this to more messages.

• So this trick actually works only for a single blinded message… Also tested in my code with 2 messages — it is really so. Excellent explanation! Thank you. – Inversion Mar 19 '16 at 19:15