Transparent and verifiable choices
Today I want to tell you about how you can make the voting process better and more reliable. First, I advise you to watch the speech of David Bismarck on TED or here in my voice acting (translated by Andrey Novik):
How it works?
')
I will talk about the e-voting system using the example of Ben Adid’s system, which differs from David Bismarck’s system, but ultimately possesses all the same important properties for people. Both options are just examples; you can come up with a huge number of such systems.
The problem of modern voting systems (both classical and computerized): a person cannot be sure that his vote has been taken into account. This is usually explained by the principle of anonymity of voting, but this is a purely technical reason. If you think carefully, you can find a way to check your own voice without violating accepted norms. A good comparison is ATMs. We all use and trust them, while our money remains safe, and, most importantly, we can always check every transaction (on the website or in a bank). A good electronic election system must be verifiable at all stages.
For such a system, the following requirements were defined:
We will talk about the last point a bit later.
In such a system, you can use any encryption algorithm similar to RSA, which is based on the use of a public-private key pair. In this example, we will use the El-Gamal scheme .
Here is a simple example:
1. p = 13, a = 2, y b = 7, x b = 11 (7 = 2 11 mod p).
2. m = 7, (c1, c2) = (2 6 , 7 * (2 11 ) 6 ) mod 13 = (12, 6)
3. (7 * 2 66 * 2 -66 ) mod 13 = 7 = m.
Now a little about the last item in the list of requirements: a homomorphism (in our case, a group homomorphism). If you are familiar with the theory of groups from mathematics, then you should remember this property. In short: a group is a mathematical object, "closed" with respect to some operation. For example, integers with respect to addition are a group, since taking any two elements from this group (two integers) and applying the addition operation (adding these numbers) we will get another integer - another element of the same group. This is “isolation”. Such a group would be designated as (Z, +).
Suppose we have two such groups: (G, *) and (H, ·). A homomorphism is a function h: G → H if h (u * v) = h (u) · h (v). In our case, the function is encryption:
enc (u · v) = enc (u) · enc (v).
This feature of the system is necessary to enable the public to count the votes without violating the anonymity of the vote. In our case, the homomorphism is:
enc (m1) · enc (m2) = (y x 1 , m1 · SK1) · (y x 2 , m · SK2) mod p = (y x 1 , · (m1 · m2) (SK1 · SK2)) mod p = enc (m1 · m2).
How is the vote?
Scanned newsletters are published on the website. The voter can check if his voice was taken into account, and if it was, whether everything went without errors.
Tests
This system was tested in elections to local governments in universities of MIT, Harvard, Unversite Catholique de Louvain (25,000 voters), University of Ottawa. On November 3, 2009, this system was applied in elections in Takoma Park, Maryland, USA.
To read
[1] Ben Adida. Advances in Cryptographic Voting Systems . MIT. (2006).
[2] Avi Rubin. An Election Day clouded by doubt , October 2004.
[3] Blakley, G. R. Safeguarding cryptographic keys. Proceedings of the National Computer Conference 48: 313-317, (1979).
[4] Josh D. Cohen and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme. In FOCS, pages 372–382. IEEE Computer Society, 1985.
[5] S. Poblig and M. Hellman, Transformation of Information It is 24: 106-110, (1978).
[6] T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31, pg. 469-472. (1985)
[7] Presentation of the Jimin Park, Applied Cryptography class, Carleton University, Feb. 2011
How it works?
')
I will talk about the e-voting system using the example of Ben Adid’s system, which differs from David Bismarck’s system, but ultimately possesses all the same important properties for people. Both options are just examples; you can come up with a huge number of such systems.
The problem of modern voting systems (both classical and computerized): a person cannot be sure that his vote has been taken into account. This is usually explained by the principle of anonymity of voting, but this is a purely technical reason. If you think carefully, you can find a way to check your own voice without violating accepted norms. A good comparison is ATMs. We all use and trust them, while our money remains safe, and, most importantly, we can always check every transaction (on the website or in a bank). A good electronic election system must be verifiable at all stages.
For such a system, the following requirements were defined:
- public / private key system: voters encrypt voice, candidates decrypt
- easily generated random keys: a random key is generated for each voter, so that the votes for one candidate from different people are not identical in encrypted form
- homomorphism
We will talk about the last point a bit later.
In such a system, you can use any encryption algorithm similar to RSA, which is based on the use of a public-private key pair. In this example, we will use the El-Gamal scheme .
- Each candidate generates and publishes the following information:
- Large prime p
- Number a b ( modulo p)
- Public key y b (y b = a x b mod p)
- Private key x b (random number from 1 to p-1; will not be published!)
- The voter must encrypt his voice - some message m (-1 <m <p). Each voter has his own public and private keys - y a and x a , respectively.
- The shared key SK (shared key) is formed: SK = (y b ) x a = (y a ) x b
- Voice is a pair (c1, c2) = (ya, m * SK) mod p
- Only the candidate for whom the vote was cast will be able to decipher it:
- (m * SK * SK -1 ) mod p = (m * a x a x b * a -x a x b ) mod p = m
Here is a simple example:
1. p = 13, a = 2, y b = 7, x b = 11 (7 = 2 11 mod p).
2. m = 7, (c1, c2) = (2 6 , 7 * (2 11 ) 6 ) mod 13 = (12, 6)
3. (7 * 2 66 * 2 -66 ) mod 13 = 7 = m.
Now a little about the last item in the list of requirements: a homomorphism (in our case, a group homomorphism). If you are familiar with the theory of groups from mathematics, then you should remember this property. In short: a group is a mathematical object, "closed" with respect to some operation. For example, integers with respect to addition are a group, since taking any two elements from this group (two integers) and applying the addition operation (adding these numbers) we will get another integer - another element of the same group. This is “isolation”. Such a group would be designated as (Z, +).
Suppose we have two such groups: (G, *) and (H, ·). A homomorphism is a function h: G → H if h (u * v) = h (u) · h (v). In our case, the function is encryption:
enc (u · v) = enc (u) · enc (v).
This feature of the system is necessary to enable the public to count the votes without violating the anonymity of the vote. In our case, the homomorphism is:
enc (m1) · enc (m2) = (y x 1 , m1 · SK1) · (y x 2 , m · SK2) mod p = (y x 1 , · (m1 · m2) (SK1 · SK2)) mod p = enc (m1 · m2).
How is the vote?
- The voter checks the ballot. The principle of proof with zero disclosure is used . The voter chooses any two bulletins, scrapes random numbers (public key) from one of them (as in a lottery) and scans a two-dimensional bar code to make sure that the order of candidates specified there corresponds to the encrypted information. This ballot is no longer valid, and the voter uses the second one.
- The voter makes a choice.
- Tears off the left side.
- Destroys the public key.
- Scans the bulletin, goes home.
Scanned newsletters are published on the website. The voter can check if his voice was taken into account, and if it was, whether everything went without errors.
Tests
This system was tested in elections to local governments in universities of MIT, Harvard, Unversite Catholique de Louvain (25,000 voters), University of Ottawa. On November 3, 2009, this system was applied in elections in Takoma Park, Maryland, USA.
To read
[1] Ben Adida. Advances in Cryptographic Voting Systems . MIT. (2006).
[2] Avi Rubin. An Election Day clouded by doubt , October 2004.
[3] Blakley, G. R. Safeguarding cryptographic keys. Proceedings of the National Computer Conference 48: 313-317, (1979).
[4] Josh D. Cohen and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme. In FOCS, pages 372–382. IEEE Computer Society, 1985.
[5] S. Poblig and M. Hellman, Transformation of Information It is 24: 106-110, (1978).
[6] T. El Gamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 31, pg. 469-472. (1985)
[7] Presentation of the Jimin Park, Applied Cryptography class, Carleton University, Feb. 2011
Source: https://habr.com/ru/post/113877/
All Articles