Secret Balloting Systems Revisited

Balloting systems were already briefly discussed in Section 6.6. This is an area likely to become one of the testing grounds for the techniques of public-key cryptography. How to guarantee secrecy in elections carried out in a computer network? One-way encryption seems desirable from many points of view. One may also want to implement optional features that are not present in current elections. We will now present in a systematic way the theory of secret balloting systems, having in mind mainly elections carried out in a computer network. Our exposition follows mostly [Renv] and [NuSS], [Schn] is a very comprehensive recent exposition on protocols and cryptographic algorithms in general, with a bibliography of 900 items.

The institution of secret ballot is often mentioned as one of the hallmarks of democratic electoral systems. The reason is obvious. Without ballot secrecy the voters can be deterred from revealing their true opinions about the issues to be voted upon. Thus, the very rationale of voting, giving voters the possibility to express their true opinions without fearing that they will be in some way punished for having them, would be seriously undermined. Secrecy in customary balloting systems relies to a large extent on trusted persons and group work. The counting of votes is done by specific officials. The basic method of securing ballot secrecy is to make sure that the ballots of individual voters are not counted individually but in aggregates. Typically all the ballots cast in a given election locale are counted simultaneously. In this way the link between a voter and his/her (hereafter her) vote is broken. How can the link be broken if there is no election locale but the elections are conducted in a computer network?

The fact that voting takes place in specifically designated areas and that all voters are identified before entering the balloting booth makes many forms of electoral fraud very difficult if not impossible. Thus, deliberate errors in vote counting presuppose the cooperation - voluntary or forced - of all officials working at a given voting locale. A plausible conjecture would be that the more persons there are supervising the electoral procedure and the more variegated political views they represent, the less likely one is to encounter electoral fraud of this kind. (Yet fraudulent elections are known to have been conducted!)

Mathematically, the protocol of the traditional election system is very simple - see also Figure 6.2. The soundness (only legitimate voters may vote and each of them may vote only once) is guaranteed by identifying each voter and keeping a record of those who already voted. The secrecy is guaranteed by the privacy of the voting booth: nobody is allowed to see how a voter votes. (Nobody is allowed to enter the booth with the voter - we disregard here invalids who need assistance.) The link between the voter and her ballot is broken after the ballot is dropped in the box. The ballots are counted as an aggregate - so only the connection between the group of voters using the particular election locale and their votes remains.

Thus under the system with voting booths, a voter can make promises to certain people, perhaps accepting bribes, or belong to an organization committed to a specific vote, and yet in the privacy of the voting booth she may cast the opposite vote without fearing disclosure, revenge or repercussions. The outcome of the election should reflect the true opinions of the people. However, it is well known that various types of fraud have occurred under this very simple system. The counting of the votes has been dishonest. A more sophisticated type of fraud is possible if the voting system employed allows the voters to list their preferences in any order. Then a dictator behind the scenes, say a feared village boss, can assign each voter a specific permutation of the candidates in such a way that the preferred candidates are always placed favorably. If a particular assigned permutation fails to appear when the votes are counted, then the boss can conclude that the voter in question did not follow the "friendly instructions", and reprisals can be taken. This form of fraud brings about a subtle distinction in the notion of secrecy. We will return to the issue below.

When elections are conducted in computer networks, numerous diverse se­curity and secrecy issues have to be taken into account. The security-related questions in telecommunication in general include, for instance:

Fig. 6.2

- Who is out there?

- Is she allowed to get this information?

- Will the information I send reach the right person?

- Has the information been seen by somebody else?

- Has the information been changed in transit?

- Can a sender deny having sent particular information?

- Can a receiver pretend not to have received particular information?

What kind of precautions and safety measures are called for such security, secrecy and authentication issues depends largely on the communication envi­ronment. We shall not dwell upon such precautions but shall rather concentrate on issues directly connected with elections. The main problem of organizing a secret ballot election in a computer network consists of satisfying simultaneously the requirements of legitimacy and secrecy. At first thought this might seem an impossible task. How can the secrecy of the votes be preserved if one must check at the same time that the voters are legitimate? At some time the voter must be known to election officials. How can the link between the voter and her vote be broken afterwards? Several solutions based on public-key cryptography are known. Let us still summarize the basic requirements.

1. Soundness. Only legitimate voters should be able to cast valid votes, that is, votes contributing to the tally. Each legitimate voter should be able to cast only one vote.

2. Secrecy. Nobody should be able to find out the voting strategy of any legit­imate voter, without her own consent. This requirement of privacy concerns the voter's relation both to other voters and to election officials.

3. Verifiabilitv. The published outcome of the election should be verifiable. In particular, each voter should be able to check that her vote has been correctly counted.

We have included the requirement 3 in the basic list, although it is not satisfied by any of the balloting systems currently in use. Indeed, in current systems there is no way for a voter to verify that the tally is correctly computed, let alone that she could check that her own vote was counted for the candidate she intended. However, in elections in a computer network the requirement 3 is easy to satisfy, provided requirements 1 and 2 are taken care of. In fact, in all proposed systems 3 is an almost immediate consequence of 1 and 2. Consequently, we have considered the requirement 3 suitable even for the basic list, especially because it is very likely to increase the motivation of individual voters to vote. Other related requirements, such as the possibility of recasting votes, can also be taken care of without any major difficulties, [NuSS],

We will discuss here two methods to satisfy the requirements 1-3. In the method of eligibility tokens the voters cast their votes anonymously but together with an eligibility token. The token is acquired from the officials of the elections in advance. It should be impossible to recognize a voter from her token. Of course, the voters themselves should not be able to produce valid tokens.

In the method of encrypted votes the voters cast their votes publicly but in an encrypted form. Single votes should not be decryptable but, of course, it must be possible to compute the total outcome of the election. In the protocol presented below, this will be accomplished by using certain predetermined and fixed scrambling techniques.

It was already pointed out in Section 6.6 that requirements 1 and 2 are easily taken care of if disjoint groups of officials are in charge of legitimization and of the actual voting and computing the result. However, then the cooperation of the two groups is a very obvious source of fraud. Therefore, we assume that all officials in the election constitute only one group, referred to as the government.

Let us consider first the method of eligibility tokens. First there is a prelim­inary registration phase. The government has generated a large enough set of eligibility tokens, for instance, integers with specific properties, and published them in an encrypted form. This constitutes the setup for secret selling of secrets: the tokens are the secrets, whereas the encryptions form the published list of secrets. The government and the voters now follow a protocol for secret selling of secrets. In this way each voter gets a secret (that is, an eligibility token) but the government does not know how the secrets (tokens) are distributed among the voters. Different voters should get different secrets. The government also publishes a large finite set S and a one-way permutation / of S.

In the actual election the voters cast their ballots anonymously. A ballot is a triple (v, f(s), e), where v is the actual vote, s e S is a random element chosen by the voter and e is her eligibility token.

The government takes into account only ballots having proper eligibility tokens. When the preassigned voting period is over, the government announces the tally of the election. This is done by publishing all the valid ballots, arranged in such a sequence that it is easy for anyone to compute the results, and also easy for each voter to check that her vote has been properly counted. It is clear that the requirements 1-3 are satisfied, provided the protocol for secret selling of secrets has worked properly.

Also other related requirements can be satisfied, for instance, recasting of votes is possible without compromising ballot secrecy. Let us see how this can be done. (It can happen within specific periods or continuously.) Assume that a voter whose ballot was w = (v, y, e) changes her opinion from v to v'. Then she sends, again anonymously, to the government a quadruple (w, v', f(s'), s), where s = f~^l(y) and s' e 5 is a new random element chosen by the voter. The government then checks whether or not f(s) = y and, if it is, replaces the old ballot w by the new ballot (i/, f(s'), e). Since / is a one-way function, nobody can compute s from y and, thus, the new ballot must come from the original voter. The recasting of votes can be repeated arbitrarily many times.

It is obvious from the above discussion that, as regards the presented method of eligibility tokens, practically everything rests on the reliability of the protocol for secret selling of secrets. Such protocols were discussed in Section 6.5, see also [Renv] and [Schn], It was observed that it can be viewed as an advantage if there are several buyers. Based on different ideas, several protocols have been constructed for secret selling of secrets. We do not go here into details but mention only one general principle and one particularly simple protocol.

After reading Section 6.5, it might seem obvious that oblivious transfer is much simpler than secret selling of secrets, viewed as tasks for constructing cryptographic protocols. However, this is not the case. It has been shown in [Renv] how any protocol for the former can be transformed to a protocol for the latter. The result can be formalized to show that all security requirements are preserved in the transformation. Moreover, several similar cryptographic tasks can be shown equivalent in the sense that a protocol for any one of them can be transformed to a protocol for another.

We present, finally, a particularly simple protocol for secret selling of secrets, also due to [Renv]. We follow the setup of Section 6.5. The seller A has k secrets $1,..., st, each of them being a sequence of f bits. The buyer B has decided to buy the secret s, .

Step I: A gives B a cryptographic one-way function /, mapping f-bit numbers onto f-bit numbers, but keeps the trapdoor and thus also /"' to herself. She also gives B a sequence X\,... ,x_k consisting of k f-bit random numbers.

Step 2: B chooses a f-bit random number a and computes f(a). He gives A the number a = x, XOR f{a).

Step 3: For j = I,... ,k, A computes the number

yj = sj XOR r^l(a XOR _Xj) and gives the sequence of numbers y, to B.

Step 4: B learns s, by computing y,- XOR a. Indeed,

y, XOR a = s, XOR/^-1(*i XOR/(a) XOR *,•) XOR a

= Sj XOR/^-1 (/(a)) XORa = s₍ XOR a XOR a = s,.

It is obvious that the protocol guarantees security for B. The only information B gives to A is the number a = x, XOR f(a). However, because a is randomly chosen, a looks completely random from A's point of view. This means that A cannot learn anything about i.

It is not so obvious that the protocol is secure for A. After all, A gives all the secrets sj to B, encrypted as If B has followed the protocol honestly and chosen the number a randomly, then a XORxj is random, and thus the probability of B learning /"'(aXORx_;) is negligible. Therefore, B cannot learn sj for j i. However, if B is dishonest, he might try to learn two secrets Si and Sj by finding two numbers b\ and bi such that

f(b₂)XORf(b_l)=x_JXORx_i.

If he succeeds in finding such numbers b\ and b₂, he takes a = b\. B then learns Si as before but now also

f~^x{a XORxy) = /"'(/(£>,) XOR.t, XOR.tj)

= r\f(bx) XOR f{b₂) XOR/(b,)) = b₂

and, consequently, B learns Sj as well. This means that it should not be possible for B to find numbers b\ and b₂ as required. The cryptographic function / has to satisfy some additional rather natural requirements. Indeed, the encryption function of an RSA system seems to possess all properties needed, [Renv],

This concludes our discussion about the method of eligibility tokens. The essence of the mathematical problem amounts to constructing a proper protocol for secret selling of secrets. Here "proper" means that the security issues are taken care of and also that no secret is sold to two buyers. We still mention that in the protocol above the random numbers xj can be replaced by a second one-way function g. The details are left to the reader.

We discuss next a secret balloting system based on the method of encrypted votes. We consider here a network, referred to as the public file. Also persons who are not legal voters might have access to the public file. In the method of encrypted votes, the voters cast their votes publicly but in an encrypted form. Thus, we assume that the government has a way of telling whether or not a message in the public file stems from a legal voter; the legality of voters has to be checked in every election.

The officials of the election, referred to also collectively as the government, consist of the control C and scramblers Sj, i = 1,..., k. According to the pro­tocol, the different parts of the government should follow certain rules. Nothing can be done against such a rotten government, where all parts are dishonest. However, if only one of the scramblers follows the protocol honestly, a fraud of the other parts will be disclosed. An individual voter may feel secure if she trusts one of the scramblers, say, a representative of the voter's own political party. In this sense, one swallow makes the spring!

The protocol operates on a certain basic domain, a finite set whose cardinality is much bigger than the total number of voters. Both the encrypted votes and the "plaintext" votes are elements of the basic set. Each of the scramblers commits himself publicly to a scrambling strategy. The latter is a permutation of the basic domain, satisfying certain additional requirements. The protocol is so designed that the election result is unreadable from the set of (encrypted) votes, but it will become readable after each of the scramblers has scrambled the set according to his particular strategy. The original set of encrypted votes is a subset of the basic domain, and so is the set after the work of each scrambler. The tally can be computed from the set after the last scrambler has applied his strategy. Thus, the voters first cast their votes in an encrypted form, giving rise to a list X₀ of elements of the basic domain. For i = ... ,k, the scrambler S, applies his strategy to the list X,_i, producing another list X, of elements of the basic domain. The election result can be computed from the list X_k. The link between a voter and the element she contributed to the list X_Q is known to C. However, the link is broken latest after the work of the honest scrambler. We have now described how everything is supposed to work. Let us go into details.

The basic domain will be the set F*(q) of nonzero elements of a finite field F{q), q = p^h, where p is a large prime. Our overall cryptographic assumption will be that discrete logarithm is intractable. Let g be a generator of the set F"(q). The numbers g and q are public knowledge. Consider a scrambler S. His scrambling strategy will be a number a, indicating that 5 will replace each element t of F*(q) by t". S discloses his commitment to the strategy by publi­cizing the number g^a. By our assumption about the intractability of the discrete logarithm, the commitment does not disclose the scrambling strategy itself. On the other hand, publishing g" is a commitment for S: S cannot later scramble t to t^b, b ^ a, because g" ^ g^b.

An important property of the scrambling strategies thus defined is commuta­tivity: it is immaterial in which order the scramblers apply their strategies. This is an immediate consequence of the commutativity of exponentiation: (t")^b = (t^b)". In fact, we could take a more general approach and consider an arbitrary basic domain rather than F*{q). Then, in view of the voting protocol, the require­ments concerning scrambling strategies would be that all strategies come from a commutative pool and commitments do not give away the strategies.

We still have to tell how the "plaintext" votes (elements of the set X_k, according to the notation above) are associated with the candidates. Plaintext votes are elements of the basic domain T which is a huge set. We define a mapping <p of T onto the set of the candidates. The definition of cp should be as simple as possible, and it will be publicized before the actual election. For instance, if there are 8 candidates, we can define

<p(w'wx) = w, \w'\ = 4, |w|=3; w', w, x e {0, 1}*,

indicating that bits 5-7, viewed as a binary integer, tell the number of the candidate who gets the vote. All other bits in the representation of an element of T are irrelevant. Thus, each of the following (plaintext) votes

11011101011011, 001011000011101101, 0111110111111101101, 0001110001001101101

goes to the 6th candidate, because in each of them the bits 5-7 spell out the number 110. As in this example, the basic domain should be divided evenly between the candidates.

We are now ready to present an election protocol, based on the method of encrypted votes. Steps 1-5 can be viewed as system construction. The actual voting takes place in Step 6, whereas the remaining steps contribute towards the computation of the result. The protocol presupposes an authentication procedure, that is, when a message beginning with a name, say (C,...), floats in the public file, then at least the persons to whom the message is intended can verify its authenticity.

Step 1: The control C chooses a large enough basic domain T = F*(q), its generator g, as well as a mapping (p of T onto the set of candidates. C publicizes the items mentioned by writing the quadruple (C, q, g,<p) in the public file.

Step 2: Each scrambler S,, i = 1,... ,k, chooses privately a random number a, having no common factors with <7 — 1. (The latter condition is to guarantee that the scrambling strategy will be a permutation of T.) S_l then computes g"' and writes the pair (5,-, g^a') in the public file. The mapping f of T into itself, defined by

fi(x)=x^a> is referred to as S, 's scrambling strategy.

Step 3: Denote z_Q — g. For i = 1,..., k, the scrambler 5, applies his strategy to z,_i, yielding /ifo-i) =z, and writes the triple (5,,z,_i,z,) in the public file.

Step 4: Each S,- convinces C in zero-knowledge that he performed Step 3 hon­estly. (Details of a zero-knowledge proof can be found in [Renv].)

Step 5: C writes the triple (C, g = z₀, z_k) in the public file.

Step 6: Suppose KIM is the chosen candidate of a voter Vj. Then V, considers z_k and q, and tests random numbers b until she finds an exponent bj such that

<p(z^b_k') = KIM.

(Approximately as many tests as there are candidates will suffice. Observe that we are here avoiding the computation of the discrete logarithm!) Then vj = g^b> is vj's vote in an encrypted form. Vj writes the pair (Vj, v/) in the public file. Similarly all voters cast their votes within a preassigned voting period.

Step 7: C goes through the pairs (Vj, Vj) in the file, removing illegitimate pairs. In other words, C removes a pair if Vj is not a legitimate voter or V, appears in more than one pair. (Observe that we need here our general assumption about authentication: pairs having Vj as their first component come from Vj.)

Step 8: C collects the remaining pairs (Vj,Vj) and produces a list X₀ = (x₀i,x02,...), where the elements x_0j are the encrypted ballots Vj, written in the increasing order of magnitude. C writes the pair (C, X₀) in the public file. (It is extremely unlikely that a repetition occurs in the list X₀. This happens when two voters who have chosen the same candidate hit the same random number. In such a case C will know that the two voters voted for the same candidate. Also the identity of the candidate will eventually be disclosed, since scrambling does not remove repetitions. By choosing a large enough q, the probability of such a coincidence can be made arbitrarily small.)

Step 9: For i = 1,..., k, the scrambler 5, applies his scrambling strategy to the elements of the list . He writes the resulting elements in the increasing order of magnitude, obtaining a list X, = x_i2,...). S, writes the pair (5, , X,) in the public file.

Step 10: C computes, for each candidate CAND, the number of elements x_kj in the list X_k with the property <p(x_kj) = CAND. The result R of the election is the list of candidates, each candidate together with the number of his/her votes. C writes the pair (C, R) in the public file.

Let us now analyze the above protocol, having in mind in particular the requirements 1-3 of soundness, secrecy and verifiability.

As regards soundness, the very construction of the protocol guarantees le­gality. Since voters act openly, C can immediately verify the legality. It is also a matter of soundness that the encrypted votes go to the candidates intended. This is seen as follows. When a voter V, chooses the exponent bj and writes the pair (Vj,g^b>) in the public file, she commits herself to the scrambling strategy hj which maps each x to x^b>. Moreover, hj maps z_k to a number ziqm which brings a vote to KIM. Altogether, g goes to z_K[_M in a succession of scramblings as follows:

g = Z₀ Z\ —Z₂ ------- ► Z_t ZKIM

01 Si S_t Vj

The following succession of scramblings takes place in Steps 6 and 9 of the election protocol:

In the two successions, the same scrambling strategies have been applied to g, although in a different order. However, the order of application is immaterial and, consequently, the resulting numbers must be the same:

yk = ZRIM •

Thus, V/s encrypted vote goes to the candidate she intended. This happens if C and the scramblers act honestly. If C or some S, makes an error or tries to cheat with respect to her vote, then Vj can immediately notice it. This is a consequence of the fact that V, can follow the passage of her encrypted vote through the scrambling process. V, only needs to check that vj is in the list X₀, z*' is in the list X,, z^' is in the list X₂, and so on. Thus, the requirements of soundness and verifiability are satisfied. Of course, a more detailed protocol should include also instructions for the case that C or some 5, is caught cheating.

We still have to consider the requirement 2 of secrecy. If all scramblers are dishonest, they can find out the voting strategy of any single voter. There is clearly very little one can do against such a totally rotten government. However, the total conspiracy of all scramblers is needed to find out the voting strategy of an individual voter; one honest scrambler 5, is enough to prevent this. By our cryptographic assumption concerning the intractability of discrete logarithm, only Si knows the scrambling strategy / (or equivalently the number a,), al­though Si's commitment g^a' is public knowledge. In fact, / could be referred to as a zero-way function because neither / (*) nor f~^l(x) is computationally tractable. Even if one knows the commitment g"¹, it is intractable to compute fi(x) or f~^[(x), and it is also intractable to verify whether or not f,(x) = y, for given x and y. Considering the lists and X, and an element x e AT, _ i, it is impossible to know which element y 6 X, satisfies fi(x) = y. Thus, an honest scrambler necessarily breaks the link between a voter and her vote. From the point of view of the voters, it suffices to select the scramblers in such a way that each voter trusts at least one scrambler. It is not even necessary for the voter to tell which of the scramblers she trusts!

Recasting of votes presents no problem in this protocol. The voters who wish to recast their votes just do so in public but in an encrypted form as before, within a preassigned period, after which the government does all the work. First C replaces the old votes of those voters who voted for the second time by their new votes, but leaves the (encrypted) votes of the other voters untouched. This produces a new version of the list X₀, after which the scramblers work as before. After a few repetitions of this procedure (provided one wants to recast votes several times) also the scrambling strategies have to be changed because, otherwise, it will become more likely that some accidental or partial information about them will be disclosed.

Observe that the above protocol also provides the following interesting pos­sibility of casting a "random vote", a possibility certainly not present in current electoral systems. The voter V, just chooses in Step 6 a random number bj (without experimenting in any way with the function <p), computes Vj = g^b' and writes the pair (V, , Vj) in the public file. If she so desires, V, may later find out for whom she actually voted! Such a possibility could be interesting for voters who want to prove that they are not inactive politically but who do not care a bit about any of the candidates. If the voter Vj writes in the public file the pair (Vj, Wj), where wj is just a random element of the basic domain, she cannot even herself find out for whom she actually voted. Only the total conspiracy of all the scramblers can reveal the lucky candidate!

In the rest of this section we address the rather important issue of selling and buying votes or, more generally, of forcing or persuading somebody to vote against her own free will. The election protocol presented above possesses the following property that can be considered either desirable or undesirable, depending on the point of view. Apart from allowing a voter to conceal her vote, it also allows the voter to carry away a receipt telling how she actually voted. In case of our protocol the receipt consists of the number bj. The voter Vj may use this receipt to prove to somebody else that a particular candidate got her vote. It is even possible for V, to let somebody else cast the vote instead of herself! The possibility of carrying away a receipt leads to the following distinction, subtle and seemingly irrelevant at a first sight but very important from certain points of view.

In the traditional election protocol, the voting booth does actually more than permits a voter to keep her vote private; it forces the votes to remain secret. In the world of an individual voter this means that the voter can make promises to unreasonable employers, bad dictators, dictator-like family heads or compelling spouses, accept bribes, or belong to an organization committed to a particular vote. Yet in the privacy of the voting booth the voter can cast a quite different, maybe opposite vote. She can do it in a happy mood, perhaps with a broad grin on her face, because nobody can accompany her to the voting booth (we disregard again the invalid voters). This means that the voter can cast a vote according to her true opinions, without any fear of repercussions or recrimination, even if her vote is against her previous promises. Even if she wanted to, the voter cannot prove to a bad boss how she actually voted; the voting booth forces the vote to remain secret. Things are drastically different in our election protocol presented above. A compelling spouse knows that the voter Vj carries the receipt bj and may want to see it. The protocol leaves the secrecy to the discretion of the voter, it does not force secrecy.

It is of course an additional incentive for selling votes if the buyer can get a proof that the service was actually rendered. Protocols, where a voter can get a receipt about how she actually voted, might increase drastically political pressure inside certain groups of people. On the other hand, at a first glance, getting a receipt seems to be a property inherent in every verifiable election scheme. But public-key cryptography is often counterintuitive. We outline now a protocol, where it is impossible for a voter to prove afterwards how she voted, but still the requirements 1-3 of soundness, secrecy and verifiability are satisfied. The protocol is due to [NieR], another method has been presented in [BenT].

The protocol we are going to outline is a modification of the method of eligibility tokens. Each voter will be convinced that her token is a valid one (that is, of a required form) but she is not able to transfer this confidence to anyone else. This means that she is given a token, and the validity of the token is shown to her by a zero-knowledge proof. In this setup the most important part is the zero-knowledge proof of the equation f(x) = y, where / is defined as the scrambling strategies above. (Thus, we consider a generator g of F*(q), g and q being public. The function / in F"(q) is defined by f(x) = x". It is intractable to verify the equation f(x) = y, although the commitment g", g and
q are known.) Let us see how a prover P (who knows a and, thus, is able to compute /) can convince a verifier V of the validity of the equation f(x) = y in a zero-knowledge fashion. V knows P's commitment g". P and V repeat the following protocol sufficiently many times.

Step 1: V randomly chooses two numbers i and j, computes mi = x'g^J, and gives mi to P.

Step 2: P randomly chooses a number I, computes m₂ = mig' and mi = f(m₂) and, finally, gives V the pair (m₂, m^).

Step 3: V gives P the pair (/, j).

Step 4: After checking that m, = x'g^J, P gives I to V.

Step 5: V checks that m₂ = m^g¹ and /n₃ = y'g^a('^+l). If not, then V rejects.

It is fairly easy to analyze this protocol and show that it is zero-knowledge. If f(_x) = y, then

m₃ = f(m₂) = /(x'gJg¹) = (f(x)y(f(g)y⁺' = y'(_gy^+l,

as it should be. On the other hand, if a cheating P is going to pass the protocol, he should be able to compute y'g^aj from m i = x'g^J. But i and j cannot be extracted from m\. (The low probability of success can be computed, and this gives an estimate of the number of rounds of the protocol needed for any preassigned degree of confidence.) It is obvious that the protocol is zero-knowledge. V learns nothing because, before she gets anything from P, she has to prove that she already knew it!

In the actual voting protocol, the above zero-knowledge proof has to be generalized as follows: one proves in zero-knowledge that two lists x\,... ,x, and yi,..., y, correspond to each other by the relations /(x,) = y_aU), 1 < i < r, where a is a permutation of the index set {1, 2,..., r}. A protocol similar to the one presented above can be given for this generalization, although a complication is caused by the fact that the permutation a is not to be disclosed.

In the following description of a protocol for receipt-free elections we try to make the setup similar to the election protocol presented above. Thus, we

speak of the control C and scramblers Si, i = 1......................... k. The work of the latter

is different from what it was before; the scramblers do not scramble encrypted votes but eligibility tokens.

The protocol we are going to describe might seem computationally very complicated. However, a more detailed analysis shows that it is effective in any reasonable setting. Moreover, no time-consuming computations are needed in the actual voting phase. The whole procedure can be divided into phases in such a way that, as regards both time and space, practical requirements can be taken care of. This will become more apparent below. In the description of the protocol, we do not go to the level of individual steps. We only describe the general phases of the protocol: preliminaries, registration, voting and counting. Some phases can be repeated (and their results reused) in several elections. However, we do not discuss here the matters to be taken care of in such a case. Our somewhat informal exposition gives us also an opportunity for on-line explanations.

In the preliminary phase of the protocol C first publicizes q and a gen­erator g of F*(q). Then each of the scramblers S, chooses a secret exponent a_t and commits himself to it by making g"' public. The product a = a\... a_k is the secret key for the permutation f(x) = x". Moreover, / is the compo­sition f\... fk of the scrambling strategies of the individual scramblers. The order of the factors in this composition is immaterial. All of the scramblers must cooperate in the computation of the function value f(x). Indeed, / can be viewed as a "collective zero-way permutation". Next C publishes a set of valid eligibility tokens jci o, x₂.o, ■ • •, x_{l 0}. The set should be much larger than the number of legal voters. Each scrambler 5, , in turn, applies his scrambling strategy to the set {jci.,-_i, ..., and proves to C in zero-knowledge (using

the protocol outlined above) that the resulting set is obtained honestly. In other words, Sj proves that the numbers {.ri.,,..., x_ti} that he has produced are the numbers {jc^-i. • • •. -^-i 1 in some permuted order, without disclosing the per­mutation. Now the numbers yj = x_J-k, j = 1,..., t, are the numbers f(x_J:o), j = 1,..., t, in some order which is not known by anybody, provided that at least one scrambler is honest in the sense that he keeps his secret. (Similarly as before, we have also here the situation where one swallow makes the spring!) Thus, the numbers y_} are the original eligibility tokens, first permuted in a way that can be known only if all scramblers cooperate and then encrypted by the collective zero-way permutation /. The numbers yj are referred to as encrypted tokens. C allocates one encrypted token to each legal voter. After this, C of course knows which encrypted token each voter gets. However, these tokens are not yet the ones the voters will actually use. (Additional precautions are needed to prevent the unlikely event that a voter tries to proceed with somebody else's encrypted token, not using her own one at all, and thus can nullify both votes in the final count.)

To end the preliminary phase, the scramblers generate collectively another one-way function E. The voters will encrypt their votes using E. The encryption key E will be made public. (It is largely irrelevant and does not affect the other parts of the protocol which public-key cryptosystem is used here. Because the setup of q and g is already present, an El Gamal system is very suitable, see Section 4.6. This means that each scrambler S, commits himself to another number bj by publishing g^bi.)

We describe next the registration phase of the protocol. In this phase a voter communicates with each scrambler, one after the other. As a result of the communication, the voter knows her voting token, the token she is going to use in the actual election. But she can never prove to anyone, not even the scramblers, let alone some family head or organization boss, which token she has obtained. In this registration phase it is important that the voter actually proves that she is a legal voter. (In the preliminary phase this is not important;

it does no harm if C distributes encrypted tokens also to some false voters.) One way to handle this situation is that the voter is first identified (perhaps in some office), after which she gets a private line to each of the scramblers. The registration phase might seem quite complicated. Observe, however, that it can be completed long before the actual election. Perhaps the same registration phase can also be used for several elections.

In the registration phase, the voter Vj with the encrypted token yj leams Zj = f(yj). This z_; will be her voting token, the token V, is going to use in the actual election. Thus, a valid voting token z results from one of the original eligibility tokens chosen by C, say x, by applying twice the collective zero-way permutation f:z = f if (x)). By the definition of /, because the scrambling strategies commute, we can also say that z results from x when each of the scramblers applies his strategy twice. It is essential that the registration phase is carried out in such a way that Vj cannot convince anyone about the validity of her voting token.

The voter V, has the encrypted token from the preliminary phase. She learns Zj = f(y,) by asking first for yj = fi(yj) from S_u then fiiy]) from S₂, and so forth, all the time using the private lines. Thus, the voter Vj approaches each of the scramblers 5,- and asks for the result of 5,- 's secret scrambling strategy when applied to the particular number Vj gives to 5, . The scrambler tells her the result and, moreover, proves in zero-knowledge referring to his commitment that the result he gives the voter is the correct one. This is done by the zero- knowledge proof protocol presented above. After communicating with the last scrambler, the voter is convinced that she has a valid voting token but cannot transfer her conviction about zj being a valid voting token to anyone else.

However, there is the following obvious problem in this procedure. The voter approaches the last scrambler S_k with some number, say y_jt and so the last scrambler will know the number fkiyj) he gives to the voter. But the number f_k{yj) = Zj is the voter's valid voting token and, thus, it should not be known by anybody. This cannot be remedied by simply letting the voter approach the scramblers in a secret order because even then the probability of a correct guess will be unacceptably high. But the following slight modification of the idea will work. It is used with all scramblers to take care of the possibility that some of the last scramblers are in conspiracy.

Suppose Vj has so far learned the number x when she approaches the scram­bler Si. Thus, she must learn fi(x). The voter V, does not give S, the number x but picks up randomly a number n and gives S, the number xgⁿ. Then 5, tells Vj the value fj(xg") and, moreover, convinces V, in zero-knowledge about the correctness of this value. The voter V, now learns / (x) because

/■(*) = Mxgⁿ)(g^aT\

and Vj knows the commitment g"^:. On the other hand, 5, learns nothing about x from the number xgⁿ.

The actual voting phase is extremely simple. Consider again a voter Vj. Let Vj be her voting strategy. By now she also has her voting token Zj. The voter sends to a public file the pair (Vj,Zj), encrypted with the one-way function E publicized in the preliminary phase. She makes sure that E{vj,Zj) appears in the public file by sending it again if necessary. The votes float in the public file in an encrypted form; otherwise, strategic manoeuvres based on the current count would be possible. If further desired, a method of an anonymous channel, [PIK], can be used to prevent the item E(vj, z/) being traced back to Vj. No identity check of the senders is in use. False votes floating in the public file can do no harm.

The counting phase begins when the preassigned voting period is over. First the scramblers, supervised by C, decrypt the pairs (vj,Zj) from the items E(vj,Zj) floating in the public file. Then C collects, for each voting strategy v, in one list all tokens associated to v. At this stage valid tokens can in no way be distinguished from false tokens or junk. The scramblers will now decrypt the tokens, seeing whether one of the original eligibility tokens x results. The procedure is the one used in the preliminary phase, now only f, is replaced by fi~^l fj~^l■ Indeed, each scrambler 5,- has to "unlock" his scrambling strategy twice because he did apply his strategy twice before: once in the preliminary phase in the process of changing an eligibility token to an encrypted token and, for the second time, in the registration phase when the encrypted token was changed to a voting token. Each scrambler convinces C in zero-knowledge about the correctness of his actions. After each scrambler has done the unlock­ing, C counts how many of the original eligibility tokens xj are associated with each voting strategy, and publishes the tally. Observe that the order of inverse scramblings is quite different from the original order of scramblings. The former is /,^-1/f'... /jT¹/*^-1' whereas the latter is f\ ■ ■ ■ fkf\ ■ ■ ■ fk- Thus, there are no matches in the various intermediate data, and no partial information can leak out in this way.

This concludes our description of an election protocol, due to [NieR], having the properties of soundness, secrecy, verifiability and receipt-freeness. There are no trusted parties, votes remain secret, correctness of the results may be checked by anyone and yet selling of votes is impossible. Computations are mainly based on modular exponentiations. The protocol can be easily implemented because there exist many kinds of hardware for modular exponentiation and, moreover, the most time-consuming computations are needed in the preliminary and counting phases. At least in the former, time is not at all critical. Since the whole setup is rather complicated, we have not presented many minor details. Some parts can also be simplified. For instance, the role of C is unimportant; C only acts as a manager for the scramblers.

Date: 2015-02-16; view: 877