Voting — But Private

Voting — But Private

Yesterday, the countries of the UK went to the polls.

It is the most basic of human rights and gives everyone a chance to give their say. Without it, the right to vote, we would have no ways to hold our governments to account. But, in the UK, we still use paper and a pen, and we still count our votes manually. We also put the votes into a van, and ship them off for counting. Surely, in the 21st Century, there’s a better way? And, so we might move in the future toward electronic voting, but how do we trust the votes, and also respect the privacy of the citizen? Well, it was David Chaum who investigated this problem, and who came up with blinded signatures.

Blind signatures

A blind signature allows Bob to hide the content of a message before it is signed by a trusted entity (the signer). This is typically used when the creator of a message is different to the entity which signs it. For example, Bob may blind the message (such as his vote), and then for Trent to sign it as being valid, but where Trent will not know the contents of the message (or his vote). This could thus be applied to voting systems, and where Bob registers his vote, and Trent then signs it as being a valid vote cast (using Trent’s signing key). Bob can then get this back, and unblind his message, and then cast the vote. The vote will thus contain Bob’s message but be signed by Trent.

For this, one of the simplest methods is a blinded RSA signature. In traditional RSA, we sign with:

and where N is the modulus (N=p.q), and d is the decryption exponent. In a blinded version, we generate a random value of r and which is relatively prime to N (gcd(r,N)=1)). We then compute:

The value of m′ is then sent to the signing authority (Trent). The signing authority then computes the blinded signature as:

This is then sent back to the creator of the message, and who can then sign with:

This will remove the blinding factor, and now be signed by the signing authority, but will not reveal the message to them. Overall this will work because:

Thus we have a signature which is signed by Trent’s decryption key (d), and with the message of Bob (m).

Coding

Here is some Golang code to implement this [here]:

and a sample run proves the signatures [here]:

Message: qwerty
Hash: 65e84be33532fb784c48129675f9eff3a682b27168c0ea744b2cf58ee02337c5

Unblinded signature verified
Blinded signature verified
Incorrect Blinded signature verified
Incorrect Unblinded signature verified


Blinded sig: bb5682db85412ca37439ecaa7476da3b356f59f0bdc757d29417a957106d6a5e07a4e27a93b0e2818ebca3553a16ba6d13966948dd1e3415c2c3187490559ee4
Unlinded sig: 119f93858c2544ead5cbe8ea76f1a29b5a05fe046653bb169785b04c72fb8d005cfdb5cbbcca6b80755819671280c822ea90ebbacce72ed95a8a1c4ae56ce9b5
Signature: 1b5f070ae4b018c8e3df90c215f933d8369927056afca19c833c12d4671cdb9eda110413aad45e728476b1e1bdd8713bee1a1a94f596af52a8a3530de2211cff

We can also create an attack on RSA signatures using this method:

Conclusions

So time, soon, we need to start to integrate digital trust into our voting systems.