Lottocracy is better than democracy! Article on Cryptographic Elections

This problem can be solved quite simply, without even resorting to any exotic cryptographic systems. Leave only the lowest level of election commissions and send vote count reports directly to a publicly accessible central database. Let each protocol be signed with the electronic signature of each of the observers working at the polling station, as well as with the electronic signature of the election department responsible for the operation of the protocol database. Any citizen will be able to download this database and make sure that the votes are counted correctly. Any observer will be able to verify that the database contains the original protocol of his polling station, and if not, then he will have signed electronic documents in his hands, which will be ironclad evidence in court. At the same time, it will still not be clear from the protocol how each voter voted, i.e. voting will remain secret.

The fact that this system is not used anywhere is in itself quite strange. But sometimes more advanced voting systems are used in local elections, such as the DRE-ip system developed in 2016. I'm focusing on this in this article because it is the only system that does not require Tallying Authorities. In other systems, there are usually several TAs belonging to different parties, and their mutual hostility is supposed to prevent fraud – obviously, unless these parties collude.

The voting procedure in the DRE-ip system looks like this.

A citizen goes to the polling station, where the usual voter registration procedure follows the one-person-one-vote rule. After this procedure, the voter receives a unique token that is not tied to his identity. It then uses this token to log into the DRE machine. He tells the machine his voice, the machine generates a random secret, and based on the voice and the secret, generates a sequence of data from which neither the secret nor the voice can be recovered. She gives the voter a signed document with this data and a unique ballot index. From this document it is impossible to extract information about who the voter voted for, so the vote remains secret (in particular, interested parties do not have the opportunity to buy votes), but at the same time it makes it possible to prove in court the fact of manipulation of the voting results. At this point, the voter must choose between confirming his vote or testing the machine for honesty. In the second case, the machine provides him with another signed document containing the generated secret and the voter's vote, and marked as audited. The voter verifies that the data on the first signed document actually matches this secret. In this case, he can vote again. If this correspondence does not exist, then the voter protests (apparently, goes to court). If he chooses to confirm his vote, then the machine adds the vote to the sum of votes, and the secret to the sum of secrets (from which, of course, neither an individual vote nor an individual secret can be recovered), then it securely erases the voice and secret from memory, and the data from the first document is sent to the bulletin board (BB) – a public storage to which the DRE machine has the right to add records (append-only write access). If the published data does not correspond to the data from the first document, this is another reason for the voter to go to court. The bulletin board includes not only the final voting document, but also all audit documents marked as audited so that members of the public can independently verify each of them. At the end of the voting, the final sum of votes and the sum of secrets are included there. Using all this published data, it is possible to check the correctness of the vote total using a certain mathematical formula.

If the vote is a choice of 2 candidates, then the vote for the first candidate is recorded as 1, and the vote for the second as 0. Then the sum of the votes will be equal to the number of votes cast for the first candidate, and the results of the election are uniquely determined by the sum of the votes. If there are more than 2 candidates, then the DRE-ip system is launched in parallel for each candidate. This complicates the procedure for working with ballots and requires another “proof of well-formedness” to verify that the sum of the votes of one voter is equal to 1.

Off the top of my head, I find one common problem with this system – it still depends on the honesty and responsibility of observers. Therefore, I don’t see how it is better than the option when the protocols are routinely counted and sent to a common database. In the absence of conscientious observers, powerful groups may violate the principle of “one person, one vote” and vote for people who did not turn out to vote. With read access to the DRE machine and outside surveillance of the polling place, they can obtain information about how each voter voted and undermine the secrecy of the vote.

The system does not require unreasonably high qualifications from millions of observers. Observers just need to make sure that there is no external surveillance of the voting process, and monitor traffic to make sure that the DRE machine is not sending any unnecessary information to the network. They are not required to be able to take a machine apart, piece by piece, and confirm that it meets any technical specification. The fair registration of votes and the correctness of their counting are verified mathematically, and the fact of falsification is easily proven using signed electronic documents.

Interlude

Let's talk about democracy itself, as the power of politicians chosen by the majority of voters. Is this idea as good as is commonly believed?

To begin with, do not be misled by the prefix “demo”, which indicates the power of the people. Election campaigns cost astronomical money, so only rich and influential groups can put their person in a certain position. Democracy is the power of elites. A powerful faction can spend an astronomical amount of money on an election campaign if and only if it expects to return the money with interest, so democracy is inseparable from corruption. The group must completely control the politicians it promotes, so it is interested in bringing to power criminals covered in incriminating evidence. Compromising evidence is a very effective and technologically advanced way to ensure loyalty. The worse the compromising evidence, the more control it gives over the politician. Honest people, on whom, in principle, no compromising evidence can exist, are not needed by any of the influential groups, and have no chance of occupying leadership positions.

The votes of the vast majority of voters are not the result of a balanced and thoughtful decision. Decisions are made under the influence of advertising media content prepared by people who understand the psychological aspects of propaganda. This content appeals not to logic, but to emotions and deep instincts.

But if I don’t like democracy so much, then what do I offer in return? What political system could be better?

2. Lottocracy

Imagine that the president of a country is chosen at random from among several million people—say, from the top 10% of people with the highest incomes. That the president is literally chosen by a random number generator, and no one knows in advance who exactly will be chosen. This makes it impossible for any influential group to push the candidate it wants into this position. No organization can secretly recruit several million people at once. Since candidates are selected at random, their average personality traits—intelligence, responsibility, and destructiveness—will be the average of the group from which they are selected. And this is one of the advantages of the proposed system. If the president is NOT chosen by chance, then the worst of the worst are most likely to fill that position. If he is chosen randomly, then on average the position will be occupied by people with an average degree of depravity. Average is better than the worst. Therefore, the quality of statesmen under such a system will greatly increase.

This method of election is called “sortition” in English, and “election by lot” in Russian. The political system itself is called “demarchy“(demarchy) or lottocracy.

Electoral democracy refers to the power of powerful groups rather than the power of the people. Lottocracy has much more reason to be called a democracy than what we have now.

Lottocracy existed in ancient Athens, where elections to the city council, legislative assembly and most government offices were held using the kleroterion, a special device for drawing lots. Most Athenians believed that real democracy was about drawing lots, not voting. And voting for them was an attribute of the oligarchic system.

In Lombardy and Venice, a mixed system of ordinary elections and elections by lot existed from the 12th to the 18th centuries, and in Florence from the 14th to the 15th centuries.

In one of the state institutions, a similar system still exists. It's called a “trial by jury.”

Lottocracy has many active supporters. You can read this article in Nature about random election algorithms that allow you not only to recruit an authorized group of people, but to comply with various quotas – professional, age, level of education, etc. In the terms of the article, such a group is called a “panel”, but I will call it “advice” for avoiding unnecessary analogies.

If you want transfer all power to the soviets If you want to try one of these algorithms, the article contains a link to a site that allows you to do this. There you can upload two CSV files – with a description of social groups, a list of candidates and an indication of how many representatives of each group should be on the council. After several (tens) minutes of heavy calculations, the site will return you a CSV file describing all the options for the composition of the board and the probability calculated for each option. I experimented with a community in which there are people belonging to several social groups at the same time. Judging by the calculations, such people do not receive an advantage over people belonging to only one group, and have about the same probability of getting on the board. Obviously, this is exactly what the authors of the algorithm intended.

The key problem with lottocracy is choosing a source of random numbers that is not influenced by people interested in certain election results. If government officials are chosen by a random number generator, then the task of usurping power will be reduced to the task of influencing the result of this generator, or to the task of accurately predicting this result.

One realistic (but narrowly applicable) idea on this matter is outlined in the document RFC 3797which describes the IETF's internal procedure for randomly selecting voting NomCom members from a pool of eligible candidates. A random seed is formed from sources of random information such as government lottery results, Treasury balances, or trading volume on the New York Stock Exchange. It is assumed that people who can influence the New York Exchange have no interest in interfering with the NomCom, so the results of the draw can be considered fair.

This may be fine for a committee nominating candidates for the Internet Architecture Board and other IETF divisions, but not for selecting senior government officials. In order to place their own person in a key position, believe me, political groups will find means to change the results of government lotteries, adjust the Treasury balance and somehow learn to manipulate trading on the New York Stock Exchange. Random grain must be taken from such a source that every citizen can personally verify its randomness. This check should not require extraordinary efforts, and should be available to any capable person. The grain itself must have an even distribution so that all candidates have an equal chance of winning, and a set of possible values ​​large enough to allow for several million candidates to choose from.

There is a simple way to collectively generate a random number that meets all these requirements. A group of people gathers in one place, and everyone brings to the meeting a closed envelope, inside of which is written a random number from 0 to N – 1. Then they simultaneously open the envelopes, add up the numbers written in them and take the remainder of dividing the resulting amount by N. As a result, the desired random number is obtained.

In a lottocratic voting system, N is the number of candidates in the election, and the resulting random number is the number of the winning candidate.

It makes no sense for unscrupulous participants in such an event to collude and try to ensure a certain (non-random) result of the procedure, because in the final amount one random number is enough for the result to be completely random and have a uniform distribution density from 0 to N – 1. It is enough for one participant to bring a truly random number, and the result will be just as random and unpredictable as if everyone involved had acted in the same good faith.

This scheme works well, for example, for a group of 5 people, but when trying to carry out such a procedure for 100 million participants, certain organizational difficulties will arise. How to gather 100 million people in one room and not disrupt the measures to counter Covid? How to organize the summation of numbers so that each of 100 million people can personally verify its mathematical accuracy?

The natural desire would be to move this event to the Internet, but how can we ensure that all random numbers are revealed at the same time? First, it is quite difficult to get such a large number of voters to synchronize and publish their numbers in a short time window. Secondly, if some influential group controls the election system servers, then it can find out all the random votes at the end of this time window, calculate the required number in about 1 nanosecond, vote on behalf of one of the group members, entering this number into the register , and get the desired generation result, which will ensure the victory of a certain candidate.

3. Non-Malleable Time Lock Puzzles

On the equalitybylot website There is an article by Matthew Gray that suggests using Non-Malleable Time Lock Puzzles to collectively generate a random number according to the principle described above. Such puzzles tend to be calculated quickly in one direction and slowly in the other. In this they are similar to hash functions. However, the calculation of a time lock puzzle cannot be parallelized, therefore, even if you spend an infinite amount of money on computing equipment, you will not be able to speed up the solution of this puzzle beyond a certain limit. In this case, the limit can be chosen such that it is convenient for organizing the draw – for example, 24 hours. It is assumed that no political group can own a computer capable of calculating the puzzle key during the period of time allotted for the elections.

Each participant in the draw must come up with a secret key (an integer from 0 to N – 1, where N is the number of candidates in the elections), with the help of which the puzzle is generated. All generated puzzles are published in an open public repository within a pre-agreed period of time. After this period, the private keys are sent to the public storage. Publishing the secret keys is not necessary, but it will save the energy needed to solve the puzzles. All puzzles must either be solved or verified using the published clues. The remainder of the sum of the secret keys divided by the number of candidates is used as the number of the winning candidate.

Even if some group controls the nth number of voters and can add any number to the sum of the keys at any time during the election, it will not know which number needs to be added to get the desired candidate number until it cracks all the puzzles, and it does not will be able to crack all the puzzles before the end of the elections, because there are no computers in the world capable of this.

If an influential group gains control of the election system server and tries to falsify the drawing of lots, then it will have to falsify ALL published puzzles, i.e. this deception will become obvious to absolutely all citizens of the country. If among these puzzles there is at least one truly random one (with a key unknown to this group), then the result of the draw will be as unpredictable as if there were five, ten or a million such puzzles.

A specific procedure for identifying falsification, in my opinion, in this case should be based on a document signed with electronic signatures of at least 60% of citizens, and stating that the voting system implicitly rejects puzzles sent by citizens, without returning confirmation of the refusal and without saving the corresponding records in public records. logs

Another sign of falsification can be detected after the end of voting and the publication of the puzzle registry, signed with the electronic signature of the election department. The appearance of two versions of the registry, signed with this electronic signature, but having different contents, is evidence that the private key of the electronic signature has been compromised.

Matthew Gray himself believes that Non-Malleable Time Lock Puzzles should only be used as a backup option. As a primary option, he proposes tiered in-person voting, where 1,000 people get together and pile paper envelopes with fireproof signs inside. The random numbers of the candidates must be written on the signs. At the appointed time, all the envelopes are burned at once, and the data from the tablets is publicly tallied and used to select a representative from these 1000 people who will participate in the next stage of the election. Then 1000 of these representatives get together again, have another burning of envelopes, and everything is repeated until one person is chosen.

We can say that 1000 people at the last stage of the elections is too small a number, and if they wish, the special services will be able to intimidate or bribe all of them. Besides, I have a hard time imagining how 1000 people would collectively add up the numbers written on a thousand tablets. But there is also a rational grain in Matthew Gray's arguments against Non-Malleable Time Lock Puzzles. Understanding the mathematics behind these puzzles can only be achieved after years of study. It touches on areas such as Circuit complexity, number theory and modern cryptography, and only a small part of the population will be able to understand the proof that this circuit is a fair way of random selection. Everyone else will simply have to trust this small group of people, which creates an obvious threat of usurpation of power and generally indicates that there is no smell of democracy here. By the way, the same argument applies against the DRE-ip system.

In conclusion, I will say that the above schemes solve the problem of randomly selecting one dictator. This is done to simplify the presentation of the concept, but in fact, nothing prevents us from slightly modifying the election mechanism, and instead of one person, choosing a collection of voting members. This will create a body that is inclined to make informed and coordinated decisions, as well as mitigate the risks associated with a psychopath getting into a responsible position.