Tag: e-voting

Last time I have talked about some of the factors that influenced the evolution of privacy-preserving technologies.

I wanted to touch base with some of the technologies emerging from the impact of these factors and talk about some of the challenges that they come with.

After a discussion about e-differential privacy, I promised you a little discussion about homomorphic encryption.

There is a small detour that I find myself obligated to take. This is due to the latest circumstances of the SARS-CoV-2 outbreak: I want to split this discussion in two parts, and start with a little discussion about homomorphic secret sharing before I go into sharing my experience about adopting the homomorphic encryption.

What?! Why?

In the last article, I argued that one of the drivers for adopting new privacy mechanisms is: “The digitalization of the citizen facing services of nation-states. (stuff like e-voting, that I really advocate against)”

Well, sometime after the SARS-CoV-2 will be gone (a long time from today) I foresee a future where this kind of services will be more and more adopted. One of the areas where citizen facing services of nation-states will be digitalized is e-voting – e-voting within the parliament, for democratic elections, etc. I briefly mentioned last time that I am really against this. At least for now, given the status quo of the research in this area.

Let me explain a little bit the trouble with e-voting

Starting with a question: Why do you trust the people counting your vote?

[…annoying pause…]

A good answer here, could be:

• Because all the parties having a stake in the elections have people counting. The counting is not done by a single ‘neutral’ authority.
• Because, given the above statement, I can see my vote from the moment that I printed it, to the moment I cast it
• Because your vote must be a secret, so that you cannot be blackmailed or paid to vote in a certain way – and there are some mechanisms for that
• Because there is no – or little corruption in your country, and you don’t have a Dragnea (convicted for election fraud) pushing any buttons

You can see that in an electronic environment, this is hardly the case. Here, in an electronic environment, if you have a Dragnea, you are shot and buried. Here, in an electronic environment you:

• Cannot see your vote since the moment you have printed (or pushed the button) to the moment of casting – anyone could see it
• Cannot easily make sure that your vote is a secret. Once you act upon your vote and it is encrypted somehow, you have no way of knowing what you voted – it became a secret. So there is the trouble with that.
  Further more, assuming conventional encryption, there are master keys that can be easily compromised by an evil Dragnea.
• Auditing such a system involves an extremely high and particular level ofexpertise, and any of the parties having a stake in the election would really have trouble finding people willing to take the risk of doing that for them. This is an extreme sensitive matter.

There is a research area concerned with tackling these issues. It is called “End-To-End Verifiable Voting Systems”.

End-To-End Verifiable Voting Systems

Basically, tackling these problems for e-voting systems means transforming an electronic environment for voting in such a manner that it can, at least handle the standards of non e-voting systems, and then add some specific electronic mumbo-jumbo to it, and make it available in a ‘pandemic environment’. [Oh my God, I’ve just said that, pandemic environment…]

The main transformation is: I, as a voter, must be able to act a secret vote up to casting it, and make sure my vote is accounted for, properly.

Homomorphic secret sharing

It would be wonderful if, while addressing the trust in the counting of the votes problem we would have a way of casting an encrypted vote, but still be able to count it even if it is encrypted. Well this can be done.

To my knowledge today, the most effective and advanced technology that can be used here is homomorphic encryption, and, more precise, a small subset of HE, called homomorphic secret sharing.

Homomorphic secret sharing is a secret sharing algorithm where the secret is encrypted using homomorphic encryption. In a nutshell homomorphic encryption is a type of encryption where you can do computations on the ciphertext – that is compute stuff directly on encrypted data, with no prior decryption. For example: in some HE schemes an encryption of a 5 plus an encryption of a 2 is an encryption of a 7. Hooray.

Bear in mind, the mathematics behind all this is pretty complex. I would not call it scary, but close enough.  However, there are smart people that are working on, and providing some, out-of-the-box libraries that software developers can use so that they can embed HE in their product. I would like to mention jus two here: Microsoft SEAL and PALISADE (backed by DARPA). Don’t get me wrong, today, you still have to know some mathematical tricks if you want to embed, HE in your software, but the really heavy part is done by these heroes that are providing these libraries.

Decentralized voting protocols using homomorphic secret sharing

In the next article I will talk about the challenges that you will face if you are trying to embed HE in your product, but until then, if you want to get a glimpse about the complexity, I will just go ahead and detail a decentralized voting protocol that uses homomorphic secret sharing.

• Assume you have a simple vote (yes/no) – no overkill for now
• Assume you have some authorities that will ‘count’ the votes. – number of authorities noted as A
• Assume you have N voters

1. Each authority will generate a public key. Anumber. Xa
2. Each voter encodes his vote in a polynomial Pn, with the degree A-1 (number of authorities -1) and the constant term an encoding of the vote (for this case +1 for yes and -1 for no) all other coefs are random.
3. Each voter computes the value of his polynomial  (Pn) – and thus his vote – at each authority public key Pn(Xa).
   1. K points are produced, they are pieces of the vote.
   1. Only if you know all the points you can figure out the Pn, and thus the vote. This is the decentralization part.
4. Voter sends each authority the value computed using its key only
5. Thus, each authority finds itself impossible to find how each user voted, as it does not have enough computed values – only has one.
6. After all votes have been casted, each authority computes and publishes a sum (Sa) of the received values.
7. Thus, a new polynomial is born (coefs are the Sa sums) with the constant term being the sum of all votes. If it is negative the result is yes, and vice versa.

If you had troubles following the secret sharing algorithm, don’t worry, you’re not alone. Here’s a helper illustration:

However, there are still problems:

• Still, the voter cannot be sure that his/hers vote is properly casted
• The authorities cannot be sure that a malicious voter did not computed his polynomial with a -100 constant, such that a single cast would count for 100 negative votes.
• The homomorphic secret sharing does not even touch the other problems of voting systems, only the secrecy and the trust are tackled.

The challenges

See, you still have to know a little bit about polynomials and interpolation to be able to use this in your software.

The crazy part is that, in homomorphic encryption terms, homomorphic secret sharing is one of the simplest challenges.

Don’t worry though, in my next article I will show you some neat library (Microsoft SEAL), share my experience with you, and give you some tips and tricks for the moment when you will try to adopt this.

Until next time, remember: don’t take anything for granted.