Electronic voting protocol: my version

Observing elections in different countries, complicated by various scandals around frauds, makes you wonder: why does such an important event, the legitimacy of which is so necessary to protect, use the mechanisms of protection of many centuries ago? This is especially strange, given that the scheme for voting, even if far from ideal, but much better than the current one, can come up with even a person who understands cryptography at the initial level. It just so happened that I attributed myself to such people, so I thought: why not try?

A number of articles on electronic elections ( one , two , three ) have already been published on Habré, but I didn’t find a well-developed protocol that meets the basic requirements. So meet: my version of the protocol of electronic voting.

Disclaimer

The author is not a professional in cryptography and mathematics, so this scheme does not pretend to infallibility or deep elaboration.
The scheme turned out pretty simple, so it is very likely that I invented a bicycle.

System requirements

What do we want to get out? I formulated the following requirements:

The possibility of independent control;
Resistance to fraud by the electoral commission, voters and third parties
Inability to find out how a particular voter voted

Tl; dr: a brief description of the protocol

The voter registers with the electoral commission, providing his personal data, masked voting key and verification key. The Electoral Commission signs a masked voting key;
The voter unmasks it and receives the signed voting key, creates an anonymous vote on its basis and publishes it;
Each vote is selected verification of the number of voters. The owner of the voice sends his personal data to the verifier using his public key. The verifier checks that the voice matches the real person.

Detailed protocol description

In the protocol, I used only 2 cryptographic primitives: asymmetric encryption and a blind signature algorithm . Naturally, encryption and masking operations must be commutative relative to each other.
')
Note: a hash operation when signing will be omitted if required.

List of notation

e

$e$ - encryption key;

d

$d$ - decryption key;

m

$m$ - masking factor;

E_{k}

$E_k$ - encryption with key k;

D_{k}

$D_k$ - decryption by key k;

M_{m}

$M_m$ - masking factor m;

N_{m}

$N_m$ - unmasking by the factor m;

i

$i$ - information about the person;

c

$c$ - choice;

K

$K$ - the contract;

V

$V$ - voice;

I

$I$ - information for verification

0. Baseline

Voter:

$e_ {personal}$ - encryption key (closed) of the personal electronic signature of the voter;
$e_ {vote}$ , $d_ {votes}$ - encryption and decryption keys. Created by the voter for a specific vote;
$m$ - masking factor. Created by the voter for a specific vote;
$e_ {check}$ , $d_ {check}$ - a pair of keys for the verification phase. Created by the voter for a specific vote.

Public repository of personal data:

The following information is stored for each citizen:

$i$ - information about the voter : name, year of birth, address registration, etc .; $d_ {personal}$ - public key of personal EDS;
$E_ {e _ {\ Large State}} (i + d_ {personal}))$ - state signature certifying the accuracy of the data.

Also stored in the repository:

$d_ {state}$ - public key of the state;
$d_ {electoral committee}$ - the public key of the electoral commission.

State:

e_{s t a t e}

$e_ {state}$ - private key of the state.

Electoral Commission:

e_{e l e c t o r a l c o m m i t t e e}

$e_ {electoral committee}$ - private key electoral committee.

Note: I used the assumption that at the moment of the start of voting the information in the repository is correct: the EDS key corresponds to each person one-to-one, there are no “dead souls” there. I will not consider the mechanisms for verifying this information: it seems to me that they should be administrative rather than mathematical. Also, information is assumed to be unchanged during the entire voting.

1. Registration

Each voter presents his data to the electoral commission. He checks that the voter is not registered yet and has the right to vote. After verification, the commission together with the voter creates what I will further call a contract .

The contract contains the following data:

$i$ - voter identification data
$M_m (d_ {vote})$ - the decryption key for voting disguised by a secret voter multiplier
$M_m (e_ {check})$ - the encryption key disguised by the secret multiplier of the voter to verify
$E_ {e _ {\ Large Election Commission}} (M_m (d_ {vote}))$ - the decryption key for voting disguised by a secret voter multiplier, signed by the electoral commission
$K_{1} = i + M_{m} (d_{v o t i n g}) + M_{m} (e_{c h e c k i n g}) + E_{e_{L a r g e E l e c t o r a l C o m m i s s i o n}} (M_{m} (d_{v o t i n g}))$
$K_1 = i + M_m (d_ {voting}) + M_m (e_ {checking}) + E_ {e_ {\ \ Large Electoral Commission}} (M_m (d_ {voting}))$

This information is signed by both the electoral commission and the voter:
$K = K_{1} + E_{e_{L a r g e P r i v a t e}} (K_{1}) + E_{e_{L a r g e E l e c t i o n C o m m i s s i o n}} (K_{1})$
$K = K_1 + E_ {e _ {\ Large Private}} (K_1) + E_ {e _ {\ Large Election Commission}} (K_1)$

All contracts are published by the electoral commission.

At this stage, the following attacks are prevented:

The electoral commission will refuse to publish the contract. In this case, the voter will be able to prove his existence, since it is signed by the electoral commission;
The voter will try to register again. The electoral commission can prove that the voter has already registered with his signature;
Election Commission will register non-existent people. In this case, any observer will be able to prove this by showing that from the data there is no personal data in the repository;
The electoral commission cannot register real people without their presence, since does not have their private key $e_ {personal}$

2. Voting

The voter unmasks the signed voting key:

N_m (E_ {e_ {electoral commission}} (M_m (d_ {vote}))) = E_ {е_ {{\ Large Electoral Commission}} (d_ {vote})

$N_m (E_ {e_ {electoral commission}} (M_m (d_ {vote}))) = E_ {_ {{\ Large Electoral Commission}} (d_ {vote})$

And it creates a voice not connected with his personality:

V = d_{v o t e s} + E_{e_{L a r g e E l e c t o r a l C o m m i s s i o n}} (d_{v o t e s}) + e_{c h e c k} + s + E_{e_{L a r g e V o t i n g}} (c)

$V = d_ {votes} + E_ {e _ {\ Large Electoral Commission}} (d_ {votes}) + e_ {check} + s + E_ {e _ {\ Large Voting}} (c)$

Where

c

$c$ - the choice of the candidate.

Voter anonymously sends a vote to the electoral commission. Election Commission publishes it in open access and returns as evidence of admission

E_{e_{L a r g e E l e c t i o n C o m m i s s i o n}} (V)

$E_ {e _ {\ Large Election Commission}} (V)$ .

3. Verification

Unfortunately, at the last stage, the electoral commission could create as many votes as they did, not associated with real personalities, so checking every vote is necessary. Who is to entrust the check? I believe that it is best to refer to the principles of demarchy and entrust verification to a random voter. You can come up with an infinite number of distribution schemes for checking-verifying on a set of voices, but the following seems to me optimal: divide the set into pairs and designate them to check for each other. Thus, the verifier who divulges information can be held accountable by the verifier. Whichever scheme is used, the algorithm for its formation must be published before the start of registration, and depend on a key unknown before the end of registration. For example, a key can be generated from exchange rates, or publicly and jointly by candidates (for example, with the help of a lotto machine). If you ignore this condition, the electoral commission will be able to find and add to the list such a large number of fake voices that all or most of them will be checking for each other.

So, the key is generated and published. Now every voter must find his verifier, get his public verification key from the vote base.

e_{c h e c k}

$e_ {check}$ generate verification information

I = V + E_{e_{L a r g e c h e c k v e r i f i e r}} (i + m + E_{e_{L a r g e p e r s o n a l}} (i + m))

$I = V + E_ {e _ {\ Large check \ verifier}} (i + m + E_ {e _ {\ Large personal}} (i + m))$

and anonymously send her to the electoral commission. Election Commission publishes it in the public domain and returns as evidence of admission.

E_{e_{L a r g e E l e c t i o n C o m m i s s i o n}} (I)

$E_ {e _ {\ Large Election Commission}} (I)$ .

Inspector finds

I

$I$ checked in the database

V

$V$ decrypts

E_{e_{L a r g e c h e c k}} (i + m + E_{e_{L a r g e p e r s o n a l}} (i + m))

$E_ {e _ {\ Large check}} (i + m + E_ {e _ {\ Large personal}} (i + m))$ using your

d_{c h e c k}

$d_ {check}$ , via

m

$m$ unmasks

M_{m} (d_{v o t e})

$M_m (d_ {vote})$ and

M_{m} (e_{c h e c k})

$M_m (e_ {check})$ and checks that:

$i$ there is in the database $i$ and $K$ ;
signature $E_ {e _ {\ Large Personal}} (i + m)$ valid;
$d_ {votes}$ matches the stored in $K$ ;
$e_ {check}$ matches the stored in $K$ .

The following attacks are prevented:

If the verifier does not provide $I$ his voice is not counted;
If the verifier provides false information, the verifier will be able to prove the forgery by publishing his $d_ {check}$ ;
The verifier cannot publish the personal data of the verifier, since the verifier also has the data of the verifier and will be able to bring him to justice
The electoral commission cannot create voices unrelated to the real person;
The tester could not replace the keys stated in the contract;
The voter can not vote twice, because has only one key signed by the electoral commission;
Electoral Commission can not replace $c$ because does not possess $e_ {vote}$ .

results

Protocol flaws:

Unfortunately, complete anonymity could not be achieved: one random voter will know who you voted for;
The protocol does not protect against the purchase of a vote: a voter can prove that he voted exactly as he had declared;
The protocol is inconvenient for use for people who do not have access to the Internet: it requires at least 2 times an Internet connection (probably in a polling station). Moreover, the polling station can track the voice and de-anonymize the voter. Probably, the first problem can be solved by allowing the voter to give up the role of the verifier and adding a sign of this in the contract and voice. Missing checks will be distributed among the remaining voters;
The protocol does not protect against the following problem: the electoral commission may simply refuse to accept the “wrong” voice. As a solution, you can use an independent platform (for example, a social network) by equating the publication of a vote in it to sending it to the electoral commission.

It is also possible that the verification phase can be simplified and made more anonymous, using evidence with zero disclosure . Unfortunately, I do not know how to do it yet and whether it is possible.

If you know, write in the comments. Also write if you know how to improve the protocol, find an error or vulnerability, and other constructive criticism.

Source: https://habr.com/ru/post/335398/

All Articles