Electronic jury voting protocols.
This work stresses the fact that all current proposals for electronic voting schemes disclose the final tally of the votes. In certain situations, like jury voting, this may be undesirable. We present a robust and universally verifiable membership testing scheme (MTS) that allows, among other things, a collection of voters to cast votes and determine whether their tally belongs to some pre-specified small set (e.g., exceeds a given threshold)--our scheme discloses no additional information than that implied from the knowledge of such membership. We discuss several extensions of our basic MTS. All the constructions presented combine features of two parallel lines of research concerning electronic voting schemes, those based on MIX-networks and in homomorphic encryption.
Introduction
In a typical trial by jury in the United States, twelve jurors deliberate in private. A foreman
appointed by the judge among the jurors presides the deliberations. Jurors might be called upon to
decide on several different counts according to a policy which may be complicated. Nevertheless, the
simplest and most important jury verdicts are of the binary type, e.g., innocent/guilty. In criminal
cases unanimity is required in order to reach a verdict. In civil cases there are different standards,
nine out of twelve votes are representative numbers. Jury deliberations proceed in discussion rounds
followed by voting rounds. Voting is performed by raising hands. Hence, a typical requirement of
an election protocol, privacy of the votes, is not achieved. This opens the possibility of biases on
decisions due to jurors fear of rejection, a posteriori reprisals by interested parties, and/or follow
the leader kind of behavior. In fact, just knowledge of tallies can cause undesirable consequences
like follow the pack kind of behavior among jurors.
A ballot box system could be implemented in order to guarantee privacy. A subset of the jury
might be held responsible for tallying the votes and communicating to the others whether a verdict
has been reached. Still, this discloses the final tally to a subset of the jury and allows them to
manipulate the deliberation process. An outside third party (e.g., a judge, government employee,
etc.) could be responsible for tallying the votes, but this would cast doubts on the whole process
since it allows for outside jury manipulation, could cause undesirable leaks on how the jury is
leaning, etc.
Dept. of Computer Science & Engineering, U. of California, San Diego, CA, and Dept. Cs. de la Computaci'on,
U. Chile, ahevia@cs.ucsd.edu. Partially supported by Conicyt via Fondap in Applied Mathematics 1999-2000 and
Fondecyt No. 1981182.
y Dept. Ing. Matem'atica, Ctr. de Modelamiento Matem'atico, UMR 2071 U. Chile-CNRS, mkiwi@dim.uchile.cl.
Gratefully acknowledges the support of Conicyt via Fondecyt No. 1981182 and Fondap in Applied Mathematics
1999-2000.
We provide an electronic drop in procedure for jury voting in the presence of a curious media,
interested parties, dishonest court employees, and conflictive jury members, that reveals nothing
besides whether the final tally exceeds or not a given threshold value.
We stress that we do not question the adequacy of the way in which juries deliberate. There are
good reasons to encourage jurors to express clearly and openly their opinions. The point is that the
way in which juries deliberate is just one familiar example, among many, where it is clear that the
voting procedure itself has an effect on the final outcome. In particular, our work is motivated by
the observation that voting procedures that disclose final tallies may be undesirable. This situation
occurs when small groups wish to reach by majority vote a yes/no type decision on a particular issue:
e.g., whether to accept or reject a paper submitted to a cryptology conference - the cryptographers
program committee problem, to confirm or not someone as president of a committee or chair of
a department, a program committee deciding whether or not to send an invitation to a speaker,
business partners trying to decide whether to go forth with a given investment.
The first electronic voting scheme proposals focused on trying to break the correspondence
between the voters and the vote casted. Afterwards, several other desirable properties of electronic
voting schemes (besides correctness, privacy, and efficiency) were identified, e.g., robustness,
availability, non-duplication, universal verifiability, non-coercibility. Electronic voting protocols
satisfying different subsets of the latter properties were designed. Nevertheless, all of them reveal
the final vote tally. In this work we propose a cryptographic procedure for addressing this problem
and stress its relevance by describing a different application.
Before presenting this work's contributions we begin by discussing past work.
1.1 Related work
Voting schemes where one wants only one bit of information regarding the outcome, like the ones
discussed in the previous section, can be cast in the framework of secure multi-party computation.
Thus, plausibility results, asserting that such voting schemes can be in principle constructed, can
be obtained. Indeed, the application of general secure multi-party computation techniques like the
ones proposed in [GMW86, CCD87, BGW88] yield such constructions. Unfortunately, they yield
constructions that do not exhibit some of the properties one desires of an electronic voting scheme
(e.g., non-interaction among voters).
Electronic voting schemes are one of the prime examples of secure multi-party computation.
Thus, it is not surprising that they have been intensively studied. The first electronic election
scheme in the literature was proposed by Chaum [Cha81]. His work is based on a realization of
a computational secure anonymous channel called the MIX-network. Anonymous channels and
election schemes are closely related. Indeed, an anonymous channel hides the correspondence
between senders and receivers. An election scheme requires hiding the correspondence between the
voters and their votes. Since Chaum's [Cha81] work, several electronic election scheme proposals
based on untraceability networks have been described in the literature, among the earlier ones
see [Cha88, Boy89, PIK93, SK95]. More recent proposals of these type are those of Abe [Abe98],
Jakobsson [Jak98, Jak99], and Jakobsson and Juels [JJ99]. (For actual implementations of MIX-
networks see [SGR97] and the references therein.)
In contrast to the schemes mentioned in the previous paragraph, the ones introduced in [CF85,
BY86, Ben87] do not rely on the use of anonymous channels. In these schemes ballots are distributed
over a number of tallying authorities through a special type of broadcast channel. Rather than
hiding the correspondence between the voter and his ballot, the value of the vote is hidden. Among
these latter type of schemes are [Ive91, SK94, BT94]. More recent proposals are those of Cramer
et al. [CFSY96, CGS97] and Schoenmakers [Sch99]
For other related work on electronic voting schemes see [FOO92, OO89, NR94, HS00]
1.2 Our Contributions
This work's first contribution is that it elicits the fact that all current proposals for electronic
voting schemes disclose the final tally of the votes. As discussed above this may be undesirable
in some situations. Our main technical contribution is a cryptographic protocol to which we
refer as Membership Testing Scheme (MTS). Given a fixed sequence of integers c
allows a collection of parties to cast values
determine whether
belongs to some pre-specified set S.
Based on our MTS we obtain a drop in replacement electronic procedure for a civil case jury
voting protocol by letting
(simpler schemes can be devised for criminal type trials, so we will focus on the more challenging
civil case type trials). For the sake of simplicity of exposition, throughout we informally discuss our
results in the terminology of jury systems. Thus, for notational and mnemonic purposes we refer
to parties voters and denote them by , to the values v
and to
as the tally.
The schemes we propose satisfy some subset of the following properties:
ffl Eligibility: Only authorized voters can vote. No one can vote more than once.
ffl Correctness: If all participants are honest, the correct output will be generated.
ffl Robustness: The system can recover from the faulty or malicious behavior of any (reason-
ably sized) coalition of participants.
Computational Privacy: A voter ballot's content will be kept secret from any (reasonably
sized) coalition of parties that does not include the voter.
ffl Universal Verifiability: Ensures that any party, including a passive observer, can check
that ballots are correctly cast, only invalid ballots are discarded, and the published final tally
is consistent with the correctly cast ballots.
Receipt-Freeness: No voter can prove to a third party that he/she has cast a particular
vote.
In our scheme the voters send in a ballot identical to those proposed in [CGS97], i.e., an
ElGamal ciphertext representing his/her vote plus a proof that the ciphertext is indeed a valid
ballot. Hence, as in [CGS97], both the computational and communicational complexity of the
voter's protocol is linear in the security parameter k - thus optimal. 1 Moreover, for any reasonable
security parameter, the voters' protocol remains the same even if the number of voters varies. The
work performed by each authority is O((mjSj n)k). Moreover, the computational complexity
of verifying each authority's work is proportional to the work performed by each authority. As
in [CGS97] the work needed to verify that a voter sent in a well formed ballot is O(k), per voter.
1 Throughtout, a modular multiplication of O(k) bit sized numbers will be our unit with respect to which we
measure computational costs.
Our MTS proposal combines features of two parallel lines of research concerning electronic
voting schemes, those based on MIX-networks (a la [Cha81]) and in homomorphic encryption
schemes (a la [CF85, BY86, Ben87]). We use homomorphic (ElGamal) encryption in order to hide
the vote tallies. We rely on special properties of the ElGamal cryptosystem in order to perform an
equality test between the tally and members of S. We use MIX-networks (ElGamal based) in order
to hide the value of the member of S involved in each equality test. To the best of our knowledge,
the only other cryptographic scheme which relies on homomorphic encryption schemes and MIX-
networks is the recently proposed scheme of Hirt and Sako [HS00]. But, our MTS combines both
theses schemes in a novel way. Indeed, Hirt and Sako's proposal uses a MIX-network in order
randomly permute, for each voter, potential ballots. Our MTS relies on MIX-networks in order to
randomly permute the elements of the pre-specified set S on which one desires to test membership.
The applications we provide for our MTS constitute novel uses of MIX-networks. A feature
of these applications is that they rely on the capacity, that the overwhelming majority of MIX-
network proposals exhibit, to randomly permute and encrypt a list of ElGamal ciphertexts. On the
contrary, they do not use the decryption capabilities that accompany most MIX-network proposals.
We propose several implementations of a MTS. Our first proposal relies on the homomorphic
encryption based electronic election scheme of Cramer, Gennaro and Schoenmakers [CGS97] and the
MIX-network of Abe [Abe98]. We also discuss alternative implementations of our MTS based on the
work of Jakobsson and Desmedt and Kurosawa [Jak98, DK00] as opposed to that of Abe [Abe98].
Our different MTS implementations exhibit different properties depending on the previous work
we use to build them.
1.3 Organization
In Sect. 2, we discuss the building blocks on which our basic MTS proposal relies. In Sect. 3, we
describe and analyze our MTS and use it for building an electronic drop in replacement for a jury
voting protocol that reveals nothing besides the fact that the final tally exceeds or not a given
threshold. In Sect. 5 and Sect. 6 we discuss variants and other applications of our basic scheme.
We conclude in Sect. 7 discussing a feature of all of the MTSs that we propose and some desirable
future developments.
Preliminaries
We work in the same model introduced by Benaloh et al. [CF85, BY86, Ben87, CGS97], where
participants are divided into n voters authorities A called active parties.
Al parties are limited to have polynomial-bounded computational resources and have access to a
so called bulletin board whose characteristics we describe below.
In the sequel we assume that a designated subset of active participants on input 1 k where k is
a security parameter, jointly generate the following system parameters: large k bit long primes p
and q such that q divides generators g and h of a multiplicative subgroup G q of order
q of Z
. One way of collectively generating these system parameters is letting participants run a
copy of the same probabilistic algorithm, where the algorithm's coinflips are generated mutually at
random.
Conventions: Henceforth, unless otherwise specified, all arithmetic is performed modulo p except
for arithmetic involving exponents which is performed modulo q. Throughout this paper, x
2R\Omega
means that x is chosen uniformly at random
Furthermore, negligible and overwhelming
probability correspond to probabilities that are at most -(k) and respectively, where -(k)
is a function vanishing faster than the inverse of any polynomial in the security parameter k. A
non-negligible probability is said to be significant.
2.1 Building Blocks
Bulletin board: The communication model used in our MTS consists of a public broadcast
channel with memory, usually referred too in the literature as bulletin board. All messages that
pass through this communication channel can be observed by any party including passive observers.
Nobody can erase, alter, nor destroy any information. Every active participant can post messages in
his own designated section of a bulletin board. This requires the use of digital signatures to control
access to distinct sections of the bulletin board. Here we assume a public-key infrastructure is
already in place. This suffices for computational security.
Note that it is implicitly assumed that denial-of-service attacks are excluded from consideration
(see [CGS97] for a discussion of how to implement a bulletin board in order to achieve this).
Distributed Key Generation Protocol (DKG): A DKG protocol allows parties A
to respectively generate private outputs s called shares, and a public output s such
that the following requirements are met:
ffl Correctness: There is an efficient procedure that on input at least t submitted
by honest parties and the public information produced by the DKG protocol, outputs the
unique secret value s, even if up to t shares are submitted by faulty parties. All honest parties
coincide on the public key
on s can be learned by the adversary except what is implied by the
value (for a more formal definition in terms of simulatability see [GJKR99]).
The first DKG protocol was proposed by Pedersen [Ped91]. Henceforth in this work, DKG
refers to the protocol presented in [GJKR99] and shown to be secure in the presence of an active
adversary that can corrupt up to t ! n=2 parties.
ElGamal Encryption and Robust (threshold) Proof of Equality of Encryptions:
Our MTS relies on a robust threshold version of the ElGamal cryptosystem [ElG85] proposed
in [CGS97]. Recall that in ElGamal's cryptosystem the sender chooses r 2R Z q , and encrypts the
message s is the public key and s is the secret key. In
a robust threshold version of the ElGamal cryptosystem, the secret key and public key are jointly
generated by the intended ciphertext recipients by means of a DKG protocol like the one described
above.
A robust threshold ElGamal cryptosystem has a feature on which all our MTS proposals rely.
This property allows checking whether a ciphertext encodes the plaintext 1 without either decrypting
the message nor reconstructing the secret s. Indeed, assume (ff; fi) is an ElGamal encryption
of message m, that is (ff; m). Verifying whether it is an encryptions of 1 message boils
down to checking the following relations:
This equality can be verified by m parties each holding distinct shares s
m of
the secrets s and s 0 without reconstructing either secret. This is achieved, assuming participant j
commits to her secret shares s j and s 0
by posting y
in her designated area of the
bulletin board, by executing three Distributed Exponentiation (DEx) protocols (two for computing
and
and the other for verifying that (ff 0 - in this order). Such protocol
on input ff outputs ff s by means of the following steps:
1. Participant j posts proves in zero knowledge that log g y using the
Chaum and Pedersen [CP92] protocol for equality of discrete logs described in Appendix A.
The protocol is honest-verifier zero-knowledge [CGS97]. This, suffices for our application. In
order to make the protocol non-interactive the Fiat-Shamir heuristic is used. This requires
a cryptographically strong hash function. We henceforth refer to this non-interactive proof
as Proof-Log(g; y
2. Let   denote any subset of t participants who successfully passed the proof and let - j;
denote the appropriate Lagrange interpolation coefficients. The desired
value can be obtained from the following identity:
Y
ElGamal Ballots and Efficient Proofs of Validity: In our MTS each voter will post on
the bulletin board an ElGamal encryption. The encryption is accompanied by a proof of validity
that shows that the ballot is indeed of the correct form. To implement this, consider a prover who
and wants to show that an ElGamal encryption of m, say (ff;
is indeed of this form without revealing the value of m. The prover's task amounts to showing that
the following relation holds:
log
Building on ideas from [CDS94], an efficient witness indistinguishable (in particular honest-
verifier zero-knowledge) proof of knowledge for the above relation was proposed in [CGS97]. For
completeness sake we review it as well as a non-interactive version of it in Appendix B. We
henceforth refer to this (non-interactive) proof as Proof-Ballot fm 0 ;m 1 g (ff; fi).
Universally Verifiable MIX-network: A MIX-network for ElGamal ciphertexts consists of
a bulletin board and a collection of authorities called the MIX-servers. It takes a list of ElGamal
ciphertexts, permutes them according to some (secret) permutation, and outputs an ElGamal re-encryption
of the original list (without ever decrypting the original list of ciphertexts).
We now discuss a proposal by Abe [Abe98] for a MIX-network with the characteristics described
above that satisfies the following properties: correctness, robustness, privacy, and universal verifia-
bility. Initially, MIX-servers jointly generate a secret values s and a public value y as in the above
mentioned DKG protocol. Moreover, the bulletin board initially contains a list of ElGamal ciphertexts
avoid the attack shown in [Pfi95] a proof of knowledge of t 0;l must accompany
The list of encrypted messages is randomized and permuted by the cascade of MIX-servers.
Server j chooses a random permutation - j of S, for each l the sever picks t j;l 2R Z q , reads
l from the bulletin board, and posts in the bulletin board ((G
Processing proceeds sequentially through all servers.
The security of the mix performed by servers relies on the following:
Under the intractability of the Decision Diffie-Hellman problem, given correctly
formed no adversary can determine - j (l) for any l with
probability significantly better than 1=jSj.
An additional protocol is executed in order to prove the correctness of randomization and
permutation to external verifiers as well as convince honest servers that they have contributed to
the output, i.e., no one has canceled the randomization and permutation performed by the honest
servers (with success probability significantly better than a random guess). For completeness sake
we review this protocol as well as a non-interactive version of it in Appendix C. We henceforth
refer to this (non-interactive) proof as Proof-\Pi.
3 Membership Testing Scheme (MTS)
We work in the model described in the previous section where the active set of participants is
authorities). Voters and authorities might overlap.
In what follows, N denotes the cardinality of the set S for which one seeks to verify whether it
contains the vote tally. Also, henceforth, i runs over runs over runs
over S.
Basic MTS Protocol
Input
1. Public Input: System parameters, i.e., k bit long primes p and q, where q ? n divides
and generators g and h of a multiplicative subgroup G q of order q of Z
. A set S ae ng.
2. Private Input for voter 1g.
Goal
To determine whether
belongs to S without revealing anything else besides this bit of
information.
Phase
1. Using the DKG protocol, A jointly generate the public value
and the private shares s Authorities commit to their share s j of s by posting y
in their designated area of the bulletin board.
2. Using the DKG protocol, authorities jointly generate, for each l 2 S, the public value y
l
l 2R Z q and the private shares s 0
l;m . Authorities commit to their share s 0
l;j of
l by posting y 0
l;j in their designated area of the bulletin board.
MIX Phase
1. Let ((G l be a list such that for each l 2 S,
2. Authority A j chooses at random a permutation - j of for each l picks t j;l 2R Z q ,
and posts the list ((G l such that for each l 2 S,
Verification Phase
Authorities cooperate to issue Proof-\Pi - a honest-verifier zero-knowledge (non-interactive)
proof that shows that they know random factors and permutations that relate ((G
with l . Each authority signs Proof-\Pi in order to insure verifiers of the presence
of an authority they can trust. Each authority checks the proof. If the check succeeds the
result is declared VALID. If it fails, dishonest authorities are identified (and removed) by
means of the tracing capabilities that Proof-\Pi provides. The remaining authorities restart
from the beginning of the MIX Phase.
Voting Phase
Voter posts an ElGamal encryption representing his vote v i , say
Output Phase
1. Each authority computes
Y
Y
2. Using the DEx protocol, for each l 2 S, authorities compute
l
Then, using the DEx protocol again, authorities verify whether for some l in S,
l
In the affirmative case they output MEMBER, otherwise NON-MEMBER.
Remark 1 Note that both the MIX Phase and the Verification Phase may be precomputed before the
voting begins. In fact, if the Verification Phase is not declared VALID, there is no need to perform
the Voting Phase.
Electronic Jury Voting Protocol: We conclude this section with a simple observation; an
electronic analog of a 12-juror civil case voting protocol where 9 votes suffice to reach a verdict
can be derived from our Basic MTS by letting 13g.
4 Analysis
Eligibility: The non-anonymity of ballot casting insures that only authorized voters cast ballots.
Indeed, recall that voters must identify themselves through digital signatures in order to post their
vote onto their designated area of the bulletin board. This also insures that no voter can cast more
than one ballot.
No-duplication: Follows from the voter specific challenge in the (non-interactive) proof of validity
of ballots. Indeed, recall that each voter computes the challenge in the proof of validity of
ballots described in Appendix B as a hash of several values one of which is a unique public key
identifying the voter.
Correctness: Clearly, an honest voter can construct a ballot and its accompanying proof of
validity. Moreover, the following holds:
Theorem 1 If all participating authorities are honest, then they will output MEMBER if and only
if the tally of the validly cast votes belongs to the set S.
Proof: In addition to the notation introduced in Sect. 3, for
Assuming that all participants in the Basic MTS are honest,
where
Hence, since ae , and
l
l (- m;l +ae) ; and M 0
l (- m;l +ae) \Delta h s 0
l (
If
holds that
l (
and the LHS
of both equalities in (1) are equal. If
then for every l 2 S it holds that -(l) 6=
Hence, h s 0
l (
and the LHS of both equalities in (1) are distinct for every l in S. Thus,
the Basic MTS outputs MEMBER if and only if
belongs to S.
Robustness: First we observe that robustness with respect to malicious voters is achieved.
incorrectly formed ballot will be detected with overwhelming probability.
Still, we need to show that the protocol cannot be disrupted by dishonest authorities. We will need
the following:
Lemma 3 ([Abe98]) Protocol-\Pi is a honest verifier zero-knowledge proof of knowledge for - and
's. The protocol is also honest verifier zero-knowledge proof of knowledge for - j 's and t j;l 's held
by honest provers.
Robustness with respect to malicious authorities is now guaranteed by the following:
Theorem 2 Assume there are at most participating authorities controlled by an ad-
versary. The goal of the adversary is to force the output of the scheme to be incorrect (i.e., to
be MEMBER when it should be NON-MEMBER and vice versa). The adversary cannot succeed
with non-negligible probability, and the identity of the authorities controlled by the adversary will
be learned with overwhelming probability.
Proof: (Sketch) By Lemma 2 it suffices to consider the case were only correctly formed ballots
will be accounted for. Let T be the tally of the correctly formed ballots.
Observe that there are at least t honest authorities. Any such collection of authorities will be
able to decide correctly whether or not T belongs to S unless ((G m;l ; M m;l )) l is not a permuted
ElGamal re-encryption of ((G . If the latter holds, then Lemma 3 insures that with
overwhelming probability the Verification Phase will detect it, the tracing option invoked, and the
identity of dishonest authorities exposed.
Privacy: We now show that under a standard computational assumption our Basic MTS does not
disclose any information pertaining the honest voter's ballots besides that implied by the output
of the scheme. Specifically, the following holds.
Theorem 3 Assume there are less than t dishonest authorities and n 0 dishonest voters controlled
by an adversary. Let T h and T d be the tally of the correctly emitted ballots among the honest and
dishonest voters, respectively. The goal of the adversary is to learn any additional information
concerning the votes cast by honest voters, besides that implied by whether or not T h belongs to
g. 2 Under the Diffie-Hellman assumption, the adversary has a negligible
probability of success.
Proof: (Sketch) By Lemma 2 it suffices to consider the case were only correctly formed ballots
will be accounted for.
If an adversary succeeds in learning any additional information besides that implied by whether
or not T h belongs to then such an adversary:
(i) either does not learn any information concerning the tally of correctly emitted ballots
besides that implied by whether or not T h belongs to
succeeds in learning some information concerning the votes of honest voters besides that
implied by membership of T h in
(ii) succeeds in learning some information concerning the tally T h of correctly emitted
ballots besides that implied by membership of T h in g.
In case (i), a reduction type argument based on the the existence of such an adversarial procedure
implies that the underlying homomorphic electronic election scheme of Cramer et al. is not private.
This would contradict the assumption on which Cramer et al.'s proposal relies, i.e., the Diffie-Hellman
assumption [CGS97, Theorem 2].
We now consider case (ii). Let T denote the tally and X l denote the random variable corresponding
to the value of the element of S encoded by (G m;l ; M m;l ). We model any prior knowledge about
the tally as a known distribution, i.e., we think of T as a random variable of known distribution.
By the end of the Output Phase some information concerning T is revealed. Indeed, in case
it is determined that X l 6= T for every l, and in case T 2 S, that X l  for an l   and
that X l 6= T for all l 6= l   . Given that s 0
l is uniformly distributed over Z q and is independent of
one has that (G 0
l
l is uniformly distributed over G q if X l 6= T . Moreover, (G 0
l
l
and ((G 0
are independently distributed. Thus, at the end of the Output Phase the only
information revealed is, in case T 62 S, that X l 6= T for every l, and in case T 2 S, that X l
for an l   and that X l 6= T for all l 6= l   .
We claim that at the end of a successful run of the protocol the only information disclosed
concerning X l 's is given by the a posteriori distributions X l =(T 2 S) in case T 2 S, and X l =(T 62
S) in case T 62 S. Indeed, we know from Theorem 2 that as long as t authorities are honest,
the computation is robust. Thus, if a result is declared VALID, then it must be so with an
overwhelming probability. This guarantees that the permutation and randomization performed by
honest authorities during the MIX Phase was not canceled. So, for any permutation (s l ) l2S of S
and arbitrary i,
where probabilities are taken over the random permutation performed during the MIX Phase and
any prior knowledge about T . It immediately follows that for any i,
2 For a set of
integers\Omega and an integer x the set f
2\Omega g is denoted
and,
Hence, if during the MIX Phase the adversary can obtain any information besides that implied by
whether T belongs or not to S, then a reduction type argument implies that there is an efficient
procedure that correlates input elements to output elements of the honest authorities MIX Phase
computation. This would contradict the intractability assumption on which the underlying MIX
network's security claim relies, i.e., the decision Diffie-Hellman problem.
If the result of the Verification Phase is not declared VALID, then honest authorities will
perform the tracing of dishonest authorities. Since both the MIX Phase and Verification Phase are
independent of the votes cast, this does not disclose any information that allows the adversary to
compromise the voters' privacy (even if the Voting Phase is performed, see Remark 1). In case the
Verification Phase is not declared VALID, then the Output Phase will not be performed and thus no
information concerning T h would be leaked (besides that which can be obtained from the ElGamal
encryption of T h ).
Universal Verifiability: Follows from the public verifiability of the proofs of ballot validity
(Proof-Ballot), the proof of randomization and permutation (Proof-\Pi), and the proof of knowledge
of equality of discrete logarithms (Proof-Log).
Efficiency: We make the (realistic) assumption that n - N - t. Recall that a modular multiplication
of O(k) bit sized numbers is our unit measure of computational costs.
The voter's ballot consists of an ElGamal ciphertext and a (non-interactive) proof that it is
indeed a valid ballot. The size of both components is linear in the size of an element of Z
The computational work involved in the computation of both ballot components is dominated by
the modular exponentiations, of which there are a constant number, each one requiring O(k) work.
Hence, the computational and communicational complexity of the voter's protocol is linear in the
security parameter k - thus optimal. Moreover, for any reasonable security parameter, a voter's
protocol remains the same even if the number of voters varies. The work needed to verify that a
voter sent in a well formed ballot equals the computational cost of making the ballot, i.e., O(k)
per voter. We stress that all the above characteristics of a voter's protocol are inherited from the
electronic election scheme proposed in [CGS97].
The work performed by the j-th authority during the MIX Phase is dominated by the cost of
computing
the work performed by each authority during this phase is O(Nk). Analogously, the work performed
by each authority during the Verification Phase is O(Nk 2 ). Finally, since each run of the DEx
protocol costs O(mk) per authority, the work performed by each authority during the Output Phase
is O((mN +n)k) (the O(nk) term is due to the work performed in order to compute
The other tasks performed by the authorities are not relevant in terms of computational
costs. Thus, the work performed by each authority is O((mN +n)k) provided they spend O(Nk 2 )
work during pre-computation. The communicational complexity (in bits) incurred by each authority
exceeds the computational complexity by a factor of k.
The computational complexity of verifying the authorities work is proportional to the computational
work performed by each authority during the corresponding phase.
5 Variants
More Efficient and Alternative MTSs: If one is willing to forgo universal verifiability,
then more efficient MIX-networks like the one proposed by Jakobsson and Desmedt and Kurosawa
[Jak98, DK00] might be used instead of Abe's MIX-network in the MTS of Sect. 3. In this
case, the work done by each authority during the pre-computation stage is reduced to O((m
log N)Nk). In fact, the only essential characteristic our MTS scheme requires from the underlying
MIX-network is that it performs a random secret permutation and ElGamal re-encryption
of an input list of ElGamal ciphertexts. (The threshold decryption capabilities utilized in the DEx
protocol is a feature from the underlying encryption scheme, not of the MIX-network). Thus, other
recent MIX-network proposals like those of Jakobsson et al. [Jak99, JJ99] are good candidates for
drop in replacements in the MIX module of the MTS of Sect. 3.
Receipt-Free MTSs: In some situations it might be desirable to ensure that parties involved in
the MTS can not sell or be coerced into revealing the values they cast. For example, in electronic
jury voting one desires voters can neither sell nor be coerced into disclosing their votes, i.e., the
scheme should be receipt-free. Our basic MTS proposal can be enhanced in order to achieve this
property. Indeed, it suffices to use Hirt and Sako's [HS00] electronic election scheme instead of the
one of of Cramer et al. [CGS97]. Note that this requires new assumptions, among them, physical
assumptions like the existence of secret one-way communication channels from the authorities to
the voters. Moreover, the computational work as well as the communication complexity of Hirt
and Sako's scheme increases linearly with the number of parties/voters involved.
6 Applications
Testing Membership of Linear Functions: We can modify our Basic MTS to allow parties
to determine whether their private inputs v i are such that
are publicly known subsets of Z q ,
is a publicly available fixed sequence of integers. This modification of our Basic MTS
allows to implement a weighted majority voting electronic election scheme.
Scoring: Consider a person/entity which is willing to answer n very sensitive questions to a group
of m evaluators (say for a job interview, insurance application, etc). Assume the i-th question
accepts as answer any element of S i . Each evaluator would like to learn whether the weighted
score of the answers
exceeds a threshold (here again c is a publicly available fixed
sequence of integers). But, the respondent wishes to keep private the answers to each individual
question. This problem clearly reduces to the one discussed in the previous paragraph. Thus, it
follows that our Basic MTS can be used to solve it.
7 Final Comments
An interesting feature of our jury voting scheme is that it combines two parallel lines of research
concerning electronic voting schemes, one based on MIX-networks [Cha81] and the other on homomorphic
encryptions [CF85, BY86, Ben87]. We need homomorphic encryption in order to hide
the ballots content and compute the tally while keeping it secret. We need ElGamal based MIX-
networks in order to hide the value of the elements of S to which the ElGamal encryption of the
vote tally is compared. It is an interesting challenge to design an electronic jury voting scheme in
the model introduced in [CF85, BY86, Ben87] which does not rely on MIX-networks.

Acknowledgement

We would like to thank Mihir Bellare, Daniele Micciancio, and Rosario Gennaro for interesting and
helpful discussions, Martin Loebl for suggesting the Scoring application, and Valtteri Niemi for
making his work available to us.



--R

Universally verifiable MIX-net with verification work independent of the number of MIX-servers
Verifiable Secret-Ballot Elections
Completeness theorems for non-cryptographic fault-tolerant distributed computation
A new multiple key cipher and an improved voting scheme.

Distributing the power of a government to enhance the privacy of voters.
Multiparty unconditionally secure protocols.
A robust and verifiable cryptographically secure election scheme.

A secure and optimally efficient multi-authority election scheme
Untraceable electronic mail
Elections with unconditionally-secret ballots and disruption equivalent to breaking RSA
Wallet databases with observers.
Proofs of partial knowledge simplified design of witness.
How to Break a Practical MIX and Design a New One.
A public key cryptosystem and a signature scheme based on discrete logarithms.
A practical digital multisignature scheme based on discrete logarithms.
A receipt-free election scheme tolerating a dynamic coercer (with applications to key escrow)
Achieving independence efficiently and securely.
Secure distributed key generation for discrete-log based cryptosystems
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design.
Efficient Receipt-Free Voting Based on Homomorphic Encryption
A cryptographic scheme for computerized general elections.
A practical mix.
Flash mixing.
Mixing in small batches.
How to prevent buying of votes in computer elections.
Divertible zeroknowledge interactive proofs and commutative random self-reducibility
Distributed provers with applications to undeniable signatures.
Breaking an efficient anonymous channel.
Efficient anonymous channel and all/nothing election scheme.
A simple publicly verifiable secret sharing scheme and its application to electronic voting.
Anonymous connections and onion routing.
Secure voting using partially compatible homomorphisms.

ae 2R Z q (a
--TR
Distributing the power of a government to enhance the privacy of voters
Elections with unconditionally-secret ballots and disruption equivalent to breaking RSA
Completeness theorems for non-cryptographic fault-tolerant distributed computation
A new multiple key cipher and an improved voting scheme
Efficient anonymous channel and all/nothing election scheme
Receipt-free secret-ballot elections (extended abstract)
Achieving independence efficiently and securely
Protecting data privacy in private information retrieval schemes
Untraceable electronic mail, return addresses, and digital pseudonyms
Practical multi-candidate election system
An optimally robust hybrid mix network
A verifiable secret shuffle and its application to e-voting
Almost entirely correct mixing with applications to voting
A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic
An Efficient Scheme for Proving a Shuffle
Wallet Databases with Observers
Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
Secure Voting Using Partially Compatible Homomorphisms
A Practical Secret Voting Scheme for Large Scale Elections
Mix-Networks on Permutation Networks
Mix and Match
A Length-Invariant Hybrid Mix
Optimistic Mixing for Exit-Polls
Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking
Remarks on Mix-Network Based on Permutation Networks
Multiparty Unconditionally Secure Protocols (Abstract)
Fault tolerant anonymous channel
Private information retrieval
Millimix: Mixing in Small Batches
Anonymous Connections and Onion Routing
Verifiable secret-ballot elections
A study of secure database access and general two-party computation
Efficient threshold cryptosystems
election scheme;MIX-networks;majority voting;membership testing