CA 02550259 2001-03-24
VERIFIABLE, SECRET SHUFFLES OF ENCRYPTED DATA, SUCH
AS ELGAMAL ENCRYPTED DATA FOR SECURE
MULTI-AUTHORITY ELECTIONS
TECHNICAL, FIELD
The following relates generally to encryption, and more
specifically to electronic encryption such as for use in voting schemes.
BACKGROUND AND SL~I~IARY
The notion of a shuffle of a collection of objects, records, or
tokens is simple and intuitive, and useful examples abound in various
daily human activities. A gambler in a casino knows that when he picks
up his hand of cards, each one will be one of 52 unique values, and that
no one else at the table will have duplicates of the ones he holds. He does
not, however, have any knowledge of how the cards are distributed, even
though he may have recorded the exact card order before they were
shuffled by the dealer.
In the context of electronic data, the problem of achieving
the same kind of random, yet verifiable pe~nutation of an input sequence
is surprisingly difficult. The problem is that the data itself is either
1
CA 02550259 2001-03-24
WO 01/'7369a PC'IYLTS0r109550
always visible to the auditor, or it isn't. If it is, then the comespondeace
between input records end output records is trivial to reconstruct by the
auditor or other observer. If it isn't, then input and output records must be
different representations of the same underlying data. Bnt if the output is
different enough (that is, encrypted well enough) that the auditor cannot
reconstruct the correspondence, then how can the auditor be score that the
shu$Ier did not change the underlying data in the process of shuffling?
Most of the description below is devoted to giving an
e~cient (linear) method for solving this problem in an important context
- ElGamal encrypted data. In order to make the exposition as clear and
concise as possible, the majority of the description below explicitly refers
to the specific case when operations are carried out in Zl, the
multiplicative group of units modulo a large prime, p. However, the only
properties of the underlying (multiplicative) group used is that the
associated ElGamal cryptosystem should be secure, and that the
Chaum-Pedersen protocol for the relation logs X = loge, Y = a (D. Chaum_
Zero-knowledge undeniable signatures. Advances is Cryptology -
EUROCRYPT '90, Lecture Notes is Computer Science, volume 473,
pages 458-464, Springer-Verlag, 1991. D. Chaurn and T.P. Pederserr.
Wallet Daxabases With Observers. In Advance~c in Cryptologyr --
CRYP~'O '91, Volume 740 of Lecture Notes in Computer Scfence, pages
89-105, Berlin, 1993. Springer-Verlag.) should not leak information
about floe secret exponent, r<. 1n fact, for one embodiment, a universally
verifiable, mufti authority election protocol - the verifier will be
implemented via the Fiat-Shatnir heuristic (A. Fiat, A. Shamir. How to
--prove yourself-. Practical solutions to identification and signature
problems. Adv~ces in Cryptology - CRYPTO '86, Lecture Notes in
Computer Science, pp. 186-194, Springer-Verlag, New York, 1987,), so
in this case it is sufficient that the protocol be zero-knowledge against an
honest verifier. (R. Cramer, R. Geanaro, B. Schoenmakers. A secure and
optimally efficient mufti-authority election scheme. Advances in
Cryptology - EUROCRYPT '97, Lecture Notes in Computer Science,
2
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO O1h369.i PCTNSO1/09550
Springer-Verlag, 1997.) Thus, ~c shuffle protocol is also useful when
the ElGamal cryptosystem is implemented over other groups such as
elliptic curves. 'the general Boolean proof techniques of R Cramer, I.
Damgrd, B. Schoenmakers, Proofs of partial k~wwledge and simplified
design of witness hiding protocols (Advances in Clyptology--~RYPTO
'94, Lecture Notes is Computer Science, pp. 174-187, Springer-Verlag,
Berlin, 1994.), can also be used to construct a proof with the same
properties, however, the resulting proof size (complexity) is quadratic,. or
worse, in the size of the input sequence.
The protocols or methods described below also offer several
advantages over the cut-and-choose technique as used in K. Sako, J.
Kilian. Receipt $ce mac-type voting scheme-A practical solution to the
implementation of a voting booth, Advances in Cryptology-
EUROCRYP? '95, Lecture Notes in Computer Science, Spzinger-Verlag,
1995. In this approach, the siu of the proof is dependent on the
probability of a cheatit~ proven that is required to satisfy all participants.
In the shuffle protocol described herein, this cheating probability is
essentially k/q, where k is the number of elements to be shuffled, and q is
the siau of the subgroup of Zl in which ,the elements are encrypted.
Although no analysis of the proof size is done in the K. Sako paper, it
$ppesrs that, in order to obtain similarly low cheating probability, ii will
need to be orders of magnitude larger than the siu of the proof provided
herein. (Moreover, if the K. Sako protocol is implemented non-
interactively, the cheating probability would need to be chosen
exceedingly small, because a malicious participant might use considerable
ofF-l~iune computation to generate a forged proof by exhaustive search_
This of course, could he the case with the protocols described, but the
probability k/g is, for all practical values of k and q, certainly small
enough.)
The advantage of the current scheme becomes even more
apparent when sew in the context of the resulting universally verifiable
election protocol. In K Sako, each voter must interact sequentially with
3
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
we oin3s~ rcrnrsoiro9sso
each "counting center" before actually casting his/her vote. On this
account; it is unlikely that a useable implementation could be built for
large scale, public sector elections in the near future. In contrast,
protocols described below, put all authority participation (except,
possibly, for the creation of basic election parameters) at the close of the
election, purely for the purpose of tabulation.
This nice property is also found in the elegant homomorphic
election protocol in the paper by R Cramer, R Gennaro, and B.
Schoenmskers. However, that protocol can only be applied to ballots
whose questions are of a simple "choose (at most) m of n" type. Ibis
effectively precludes "wsite-in" responses, as well as "proponional type"
questions where the voter is expected to indicate answers in preferential
order, and questions are tabulated in accordance with this preference. A
couple of somewhat less_importaat disadvantages of the R Cramer, R
GGnnaro, and B. Sehoenmakers scheme are that it expands vote data siu
considerably, and that it requires a voter validity proof. This proof further
expands the vote data size by about an order of magnitude, and is
unattractive from a practical perspective, because it presumes special
purpose code to he running on the voter's computer.
The protocol is described below constructed entirely from a
sequence of Chaum-Pedersen proofs, and elementary arithmetic
operations. It is thus simple to implement.
BRIEF DESCRIPTION OF THE DRAWIrTC3~S
Figure 1 is a block diagram illustrating a suitable
w environment for implemactting embodiments of the invention.
Figure 2 is a schematic diagram illustrating a simple
implementation of the shu$le protocol descn'bed herein as applied to a
simple ballot with three voters and three shuttles.
Figwe 3 is a flow diagram illustrating a scaled iterative
logarithmic multiplication proof protocol.
4
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO o117369s ~CT/USO1/09550
Figure 4 is a flow diagram. illustrating a simple shuffle
protocol where the shuf~ler knows the encryption exponent_
Figure 5 is a flow disgiam illustrating a general shuffle
protocol where the shu$ler does not lmow the encryption exponents.
Figure 6 is a flow diagram illustrating an anonymous
certificate distribution routine.
Figure 7 is a flow diagram illustrating an alternative
embodiment to the anonymous certificate distribution routine of Figure 6.
Ia the drawings, identical reference numbers identify
identical or substaatislly similar elements or acts. To easily identify the
discussion of any particular element or act, the most significant digit or
digits is a reference number refer to the Figure number itt which that
element is first introduced (e.g., element X04 is first introduced and
discussed with respect to Figure 2).
The headings provided herein are for convenience only and
do not necessarily a~'ect the scope or meaning of the daimed invention.
DETAILED DESCRIPTION
1. Overveew
Described in detail below is a cryptographic protocol to
vesihably ah~le a series of eletaeats, :uch as an input sequence of public
keys in discrete log form or k input ElGamal encryptions, that has
applications ill, e.g., a secure, universally verifiable, mufti-authority
election scheme. In the case of k input ElGamal encryptions, the output
of the shuffle operation is another sequence of k ElGamal encryptions,
tech of which is a re-rncryption (i.e., as ElGamal pair which encrypts
exactly the same clear text) of exactly one of the input encryptions, but
the order of elements, in the output is kept secret. Though it is a trivial
matter for the "shu$ler" (who chooses the permutation of the elements to
be applied and the encryption keys used) to compute the output from the
input, the construction is important because it provides a linear size proof
SU95TtTUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO 01/~369d pCT/Ugpl/09550
of coorrccmess f~ the output sequence (r. e_, a proof that it is of the form
claimed) that can be cltecaced by an arbitrary verifier. The security of the
proof protocol is the same as that of the Chaum Pedersen protocol for the
relation logs~r = logs, y, which is sufTcient for the election application in
which it as used.
The following description provides specific details for a
thorough understanding o~ and enabling description for, embodiments of
the invention. However, one skilled in the art will understand that the
invention may be practiced without these details. In other instances, well
laaown structtars and functions have not been shown or described in
detail to avoid unnecessarily obscuring the description of the
embodiments of the invention.
Much of the detailed description provided below is
explicitly disclosed is tl~,e provisional patent applications noted above;
much of the additional material will be reco~nized by those skilled in the
relevarst art ss being inherent is the detailed description provided in such
provisional patent applications, or well known to those skilled in the
relevant art. Those skilled is the relevant art can implement aspects of the
invention based on the detailed description provided in the provisional
patent applications.
The mathematical aotatian used here is readily
understandable to those skilled in the relevant art; however, for those
unfamiliar with the art, the following definitioons and descriptions are
provided. Such definitions, although brief, will help those generally
unfamiliar with the art to more fully understand aspects of the invention
.based on the detailed description provided herein. Such definitions are
further defined by the description of the invention as a whole (including
the claims), and not simply by such definitions.
Figures 1-5, as well as the detailed description provided
herein, describe protocols betaroea a party (e.g., a vatzr) and a verifier (or
between a proving Patty and a vorifyi~ng Party). The actions performed by
the parties are grouped together into flow diagram boxes. Tn general, each
6
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO O1I13G94 PCTIITSoI/09550
line of text or equations is a box describes a step, such as a computation,
transmittal of infozmation, or storage or retrieval function. Such flog
diagra~ans are read line by line and box by box.
The tenor "party" as generally used herein, indicates an
entity, and might be an agent who performs a step or a collection of steps
under the protocol. It may also refer to a means or method for perfonszirtg
some or all of the steps. Thos, some or all portions of the protocols may
be performed wader at~y suitable configuration of digital logic circuitry.
Far example, auy or all steps under the protocol may be realized by not
only a general purpose cotaputer, such as a personal computer, but by a
hard wired or dedicated combinatorial logic device, or any sort of suitably
propratnmed maehiae or naicroprocessar, so long as such device or
machine performs the required processing steps, storage, input and output,
and the like.
The symbol " Ex " generally indicates that a number or
numbers on the le$-hand side sre chosen from a set on the right hand side
according to a probability distn'bution that is substantially uniform and
independent (random). In practice, a physical random number generator
can be used, possibly in conjunction with additior~sl past processing, or a
deterministic pseudo-random number generator. Mtthods of generating
random numbers are lmown by those skilled in the relevant art.
The symbols "II" and "E" respectively denote product and
sum, which are indexed.
The symbol "Zo" denotes a set of numbers of integers 0
through p.-1, or sing of integers, modulo p. Addition and multiplication of
elements m the ring Zp are defined modulo p.
The symbol " E " denotes that an element on the left-hand
sida is a member or element of a set on the right-hand silo.
The symbol " a " denotes that a set on the left hand side is a
subset of a set orl the right-hand side, that is, that the set on the left
hand
side is contained is the set on the right hand side.
7
svesT~TUre sHe~ ~RUt_E zs~
CA 02550259 2001-03-24
WO 01173694 PCT/tTS01/0955D
The angle brackets symbols (t. e., " ( ~ ") are paired symbols
that generally indicate that the term or terms between them denote a
subgroup generated by a subset of a given group or ring of integers (e.g.,
the ring Zp). A subgroup is a subset of another group (or ring) that is also
a group under the same binary operation (e.g., the integers are a subgroup
of the real numbers under addition, but the integers modulo n are not a
subgroup of these since the operations are differently defined.
1u the following, unless explicitly stated otherwise, n will be
a positive integer, p and g will be prime integers, publicly known.
Arithmetic operations are performed in the r~aodular ring Zp (or
occasionally Z"), and g E ZP will have (prime) multiplicative order q. (So,
trivially, gl(p-1).) Iri each proof protocol, P will be the prover
(shu~ler) and V the verifier (auditor).
One embodilment described below, employs a Zp (F.lGalnal)
cryptosystem, although an elliptic curve cryptosystem and cryptosystems
under general groups may be used. Such cryptosystems employ public
keys for asymmetrical cryptosystems. Public key systems employ so-
called one-way functions and trap-door functions. A "one-way function"
is a function that is relatively easy to calculate output therefrom but
whose inverse functions are far more difficult to compute. For example,
power functions are such that they are easy to compute the product of a
number of equal factors, but the reverse operation of finding the root of a
quantity, is more complicated. "Trap door" functions are similar to one-
way functions, but where the inverse functions are extremely diifficult
unless some additional information is available. This additional
information is typically the "private key" held by a party, such as a voter.
' The below methods and protocols frequently use the
Chaum-Pedersen proof of equality for discrete logarithms. For g, X, h, Y
a Zp this is a proof of knowledge for the relation
loggX= loge, Y (1)
8
SUBSTITUTE SHEET (RULE ~6)
CA 02550259 2001-03-24
WO 01/7%9d PCT/US01/09»0
It is not known to be zero-knowledge, however it is known
to be zero-laiowledge against an honest verifier, which is su~rient for
our main application where the verifier is implemented via the
Fiat-Shamir heuristic.
"Zero-lmowledge proofs" allow a voter or proven party to
demons>tate lmowledge of a secret while revealing no information
whatsoever of use to the vori~fier parry in conveying this demontstration of
knoyvledge. Only a single bit of information is conveyed, namely that the
pmvcr party actually dots lmow the secret. In other words.-a votez and a
verifying authority exchange messages, where the voter's objective is to
convince the verifier the truth of an assertion, e.g_, that the encrypted
ballot is, or shu$1ed sequence of ballots or elements are, complete and
correct, without revealing how die voter voted on each question in the
ballot or how the saries of elements were shuffled. Undo such zero..
knowledge proofs, each voter or proven party effectively g~er$tes certain
numbers that only a person having his or her own private key could
generate. A verifier or authenticating party then confirms that each.
calculated number indeed is generated under a known algorithm to
thereby authenticate the voter and that his_ or h~ dectronic ballot is
complete and correct or "well-formed" for all allowable choices and
constraints, or that the series of elements have not been uttered (besides
being shuffled and encrypted).
Definition 1 An instance of the Chaum-Pedersen proof, as
above, will be denoted by
C'P ($. X. h, ~'!.
Definition Z For feed g ~ ZP be the binary operator on
(g~ x (g~ denotes subgroup generated by a s~rbaei of a ring defined by
logs ~_ ~a y) _ mgt ~r logsy
9
SUBSTITUTE SHEET (RULE 2s)
CA 02550259 2001-03-24
WO 01/73696 pGT/USOL09550
for all x, y a ~g~ . Alternatively
g~ ~ B ~ ~ g~6 - ~)b - ~g~Q
for all a, b a Zq Following the indexing converaionr used for
summations and multipltcatiorts, we also trse the notation
t
~ ~ X~ = Xo ~= X~ ~s . _ . ~~ Xt
ia)
This operation as is referred no herein as logarithmic multiplication base
8
Ia each of the notations in the preceding definition, the
subscript g may be omitted when its value is clear from context. As
generally used herein, "binary operator" refers to an operator defined on a
set which takes two elements from the set as inputs and returns a single
element.
Remark 1 Notice that in the Chaum-Pedersen proof if h
~, and the eoaunon logarithm is a = logeX= log,,Y, then t:'p (g, X, h, Y) is
obviously also a proof of the relation Y = h ~=X ~ X ~l h.
Remark 2 The about proof is obviously zero-lmowledge
with respect to s, since the proven need ~nvt have any lalowledge of this
value in order to construct the proof.
Note the following collection of well-lmowa results since
they will be heavily used in the remainder of the detailed description.
Lemma 1 Let f ~x) a Zq ~:~ , 6e a polynomial of degree d Then
" rheie are at most d values z~, . . . , zd a Zq such that f[sr) ~ 0.
Corollary 1 Let~x), g(r) E Z4 [s] be two polynomials of degree
at most d, with f ~ g, Thest there are at most d values z~ , . . . , zd E ZQ
such that
,ltzi) = BtZ~).
SUBSTITUTE SHEET (RULE Zs)
CA 02550259 2001-03-24
WO Oa/7369.i PCTlITS01b95.50
Coronary I Lar~~r), g(x) E Z9 L=l ae two p~oly~omials of degree
at rnosr d, with f # g. If C E R Zq (c is selected art sad fror~r 2~ ), them
the
following probability Jalds:
p(~~I(t)=g(~)~ s q
Lemma Z Let Z~ be tl~e sk dirnaissional vector space
over Z9, mid fcr v = (v1, . . . , . . . v~ E Z~, v $ 0. If r En Zo is chosen
as
random, then
P({r: v.~ =0~~= 1
Q
2. Proofs for Iterated Logari~hmit MultiQlication
For the rest of thin section, all logarithmic multiplieations
will be computed relative to a fixed element g, and hence we will omit the
subscript in notation. The following problem is fimdsmental to the
shu$le pmofs which are to come later.
Iterated Logarithmic Multiplication Problem: Two
sequences (X, ~; , and ~Y, ) _, are publicly latown. The Prover, P, also
Ioaows u, = logy X, and of = logs Y, for all l, but these are unknown to the
verifier, Y. P is required to convince V of the relation
t t
~X, _ ~Y, (Z)
.=y
without revealing any information about the secret logarithms r~, and v,.
Intuitively, this pmblem is simple in light of Remark 1_ The
Proven can conshuct two sequences of k Chsutn-Pedersen proofs to
t - t
convince Y of both the value of ~X; and the value of ~Y, , and V can then
check that these two values are the same. If all the Xr and Y, are known to
be random and independent, this might be acceptable for the purpose of
11
SUBSTITUTE SHEET (RULE Z8)
CA 02550259 2001-03-24
w0 01/73694 PCT/U501/09550
keeping the u, and v; secret and may be implemented under one
embodiment of the invention, but it is clear that this protocol reveals some
information that v can not compute himself, namely the values of
Ir k
~X"~Y" as well as the intermediate logarithatic rnultiplications. In
order to strengthen the protocol, the depicted embodiment and method
described is detail below introduces some randomness in order to ensure
that it leaks no more information than the underlying Chaum-Pedersen
protocol.
Iters~ted Logarithmic Multiplicatiott Proof-.
1. P secretly generates, randomly and independently,
k+ 1 values {r; }~ a Zq and reveals the exponCntiated values R, = g'' .
2. For each 1 <_ i 5 k, P secretly computes w; = r,.u; /T~, ,
and reveals W, = g'~ , z; ~ w; /v; .
3. P sets Z; - g'' and constructs the two
Chaum-Pedersen proofs
CD ~Rr_t.Xr.Rr,W,.~ (3)
~ (Y,g~,R;,Zr~
which he reveals to V. ?here two Chaum-Pedersen proofs taken together
cannot reveal any more information about the secrets than the information
that is revealed from each of them taken separately. The key to seeing
this is Remark 2 The first proof is aero-knowledge with respect to
/,r,_, , though only honest verifier zero-knowledge with respect to u; /~;a ,
But the second proof is zero-knowledge with respect to r, r,_~ and u, since
even the Proven need not know these values in order to generate the proof.
Of course, one can gain some information about these values froax the
revealed value z" but only if some information is known about v;. Tt is
not lmown if this can happen with a dishonest verifier, but does not when
I2
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO Ol/7369~ PCT/1JS01/09550
the veriSer is honest, and this is the case with embodiments and
applications described below.
Clearly the quotients i /r,_, are all uniformly distributed and
independent, so the values r, themselves do not reveal any information,
by themselves, about the e; and v;.
4, V checks that Z, - g'' and checks each
Chaum-Pedersen proof.
5. Y finally evaluates z = ~~~ z; and checks that
One can easily check that this protocol solves the iterated
logarithmic multiplication problem by referring to Rennark 1 and by
simply multiplying out the exponents. The probability of a forged proof
is bounded above by the probability that one or more of the
Chaum-Pedersen proofs have been forged. Each of these probabilities is
1/q. Hence the ovcrsli probability of a forged proof is bounded above by
2klq.
For reasons that will become apparent later, the following
variant of the iterated logarithmic multiplication problem will actually be
of more use to the method. _
Scaled Iterated Logarithmic Multiplication Problem: As
in the original problem, tyro sequences (X, } :~ and {Y,. }k ~ are publicly
known, u, = log~Y; and v, = IogrY~ for all i arc ktwwn to P, but secret from
Y In addition, a ~oastant c a 29 is known only to P, but a commitment of
c, C = g~ is made known to r! P is required to convince Y df the relation
k
~ X; _ ~Y,. (5)
r~i ~-i
Without revealing any information about the secret logarithms u,, v;, and c.
Scaled Iterated Logarithmic Multiplication Proof:
The proof requires only a miner variation to the original.
The Chaum-Pedersea proof in 4 nccds to be replaced by the similar proof
13
SUBSTITUTE SHEET (RULE I6)
CA 02550259 2001-03-24
WO 01/73694 PCT/US01109550
G'P (Y;, C,, Wt, Z;) (6)
3. The Simple K-Shuffle
The first shuffle pmof we construct requires a restrictive set
of conditions. It will be useful for two reason. First it is a basic
building block of the more geneial shu$le proof to come later.
Fartuitously, it also serves a second important purpose. A single instance
of this proof can be constructed to effectively "commit" a particular
permutation. This can be important when shuffles need to be performed
on tuples of Zp elements, which is exactly what is required is the voting
application. (A "tuple" refers to a sequence or ordered stt. For example,
a 5-tuple or quintuple is an ordered set of five alcments, while a k-tuple
refers to a finite ordered _set with an unspecifiod number of members)
Simple k-Shuffle Problem: Two sequences of k elements of
Zr, X,, . . . , Xk and Yl, . . . , Y~ are publicly known. The Proves, P, also
lasows u;, = logg.Y; and v, = loggY,, but these are uala~own to the verifier,
Y. In addition, a constant c E Z9 is known only to P, but a commitment
of c, C = ga is made lrnown to Y. P is required to convince Y that there is
some permutation, ~ ~ E, with the property that
YA,,} = x,.' (
for all 1 <_ i < k without revealing any information about a or the secret c.
The function re corresponds to a function for mapping a set of input
-~ elements to a permuted set of output elements.
Simple k-Shuffle Proof: The proof construction is alutost
trivial in light of the previous section and Corollary Z_
1. V generates s random t E Zq and gives it to P as a
challenge.
2. P computes T = g~ (also known T~ and S = T' g".
14
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO OI/7369~1 PC?/U5011095=0
3. P generates the Chaum-Pedersen proof CP (g, C, T,
S) and reseals this to V.
4. P computes publicly (i.e., checked by 1~ the values
U~ ~ T/X, and Y~ = SIY,. Note: U, and V, are chosen thusly to be more in
line with the notation in Corollary 2. In one embodiment, the method
implements the protocol with U, m X,IT and Y,- = YdS since divisions are
computationally more expensive than multiplicatiorns.
The Proven executes the scaled iterated logarithmic
cnultiplieation proof protocol for the sequences {U; ~~~ and { V ~~~ and the
comtaitment C_ 8y checking the scaled logarithmic multiplication proofs
on sequences U and V, the verifier ensures that the desired relationship
between the initial input sequence of elements X and the sequence Y
holds (based on Collorary 2).
A forged proof caa valy be generated if either the scaled
iterated logarithmic multiplication proof is fanged, or the single proof of S
= T° is forged, or, V happens to choose c from the exceptional set in
Corollary 2. hence the overall probability of a forged proof is bounded
above by (3k+ l~q. Further information regardiag proofs provided under
the shuffle protocols described hereia ~sy be found in the above-
referenced U.S. Provisional Patent Applications_
In ge~aeral, the simple k-shu$le may be sufficient for some
applicatioas. To shu$le itetn5, an individual needs to employ a
cryptographic transformation (e.g:, exponentiation) where there is
certainty that a seriea or sequence of output elements Y~through Yr were
derived $rnn as original or iaput sequence of olements Xl through Xk
based on wnstant cryptographic information, without revealing which of
the original X elements produced a resulting 'Y element_ Furthermore,
individuals wish to provide such shuffling without also having to employ
a burdensome proof of validity, such as cut and choose type of validity
proofs lmown in the prior art that require numerous iterations far a
su~cient level of proof. Instead, a series of k independent Chaum-
SUBSTITUTE SHEET (RULE 26~
CA 02550259 2001-03-24
WO 01/7369s ~CTIUSO1/095so
Pedersen proofs based on a secret expottentiation value c are employed,
as described herein-
4. The General R Shuffle
An obvious limitation o~ the simple k-ShufFle protocol is
that the shu$ler, P, must lmow all the original exponents s,, . . . , s,~. In
many applications this will not be the case. The next step is to eliminate
this restriction-
General k-Shuffle Problem: Two sequences of k elements
of Z~, Xl, _ . _ , Xr and Y,, , , , , Yr are publicly latown. In addition, a
constant c E ZQ is lotowa only to P, but a wmmittnent of c, C = g' is
made lmown to V_ P is required to convince V that there is some
permutation, ~c ~ ~ t , with the property that
' Y.ti~ = Xi C$)
for all 15 r <_ k without revealing any information about tc or the secret c.
General k Shuf~te Proof. The proof is constructed from a
simple k-shu$le that has bees "appropriately randomized" by the verifier,
and an application of Lemma 2.
1. P generates a sequence ~u; ~~~ a Z9, randomly and
independently and reveals the sequence ~; = g'' .
2. V generates another sequence {e, ~~~ a Zq, randomly
and independently, and gives this to P as a challenge.
3. P publicly sets Ui = g' .~I, , and secretly sets u, ~ e, +
.~ u, :, By requiring the Provcr to add a value generated by the Verifier
prevents the Drover from picking certaixt secrets (exponents) snd
otherovise helps ensure encryption robustness.
4. P cons-nuets a simple k-shn$le on the sequence
{U; ~~~ , with another commitment D = ~ (different secret exponent), and
inverse permutation, a ~, resulting in the sequence (Y, ~~~ _ ~g"~ }' ~ and
the
16
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
Vf0 a117369~t pCTlUS01l09550
corresponding proof as in the simple k-shu$le section. (Recall that the Y
are public, but the v, grc secret to P.)
S. P publicly sets A, ~ X w and B, = Y,"' , and reveals the
Chaum Pedersen proofs
G'P (g. vi, X ~ Ai)
CP (g. U~~ Y;. B~ (1~)
Thus, tho sequence of elements A and B correspond to the
input sequence of elements ?~ at~d Y.
6. Publicly, the values
A=~A; (11)
t
B=~B, (12)
are evaluated.
7. P rcv~eals the Chaum-Pedersen proof
CP (D, A, C, B) (13}
Steps 5-7 above effectively require the Prover to pin down
the data to help ensure that the Prover has not tampered with ~e original
data. (These steps differ from the simple shuffle description above.) A
forged proof can only be generated if either the simple k-shufDe proof is
forged, or one of the Chaum-Pedersen pmofs is forged, or the tuple (ur,. . .
r~k ) is chosen from the exceptional set in Lemma 2. Hence the overall
probability of forgery is bounded above by
17
SUBSTITUTE SHEET (RULE Z6)
CA 02550259 2001-03-24
(3k+1~+2k+1 _(SkT2) (14)
9 q 9 q
5. K-Shuffles of Ta~,les
Those skilled in the relevant art will recognize that in the
previous section, the choice of the simple shuffle essentially "froze" the
permutation that could be proven. This makes it easy to see how to
extend the previous section to shuffles of k ruples of elements of ~g~ .
T'hinlcing of a sequence of k I-tuples as a k x 1 array, a single simple k
shuffle can serve to prove that all columns have been permuted according
to the same permutation, but each row left unchanged. Thus, the k shuffle
described above is performed 1 times, once for each column of the array
of k elements (each of the k shuffles reuses the simple shuffle). In
particular, this extends to tuples of ElGamal pairs.
6. The Voting Application
in one embodiment, votes are submitted as ElGamal pairs of
the form (g~,ha'm), (or a sequence of these pairs if more data is
18
CA 02550259 2001-03-24
o9i19i2oo2 09;55 FA.T ~Jo~l
WO 01/7369; PCT/USO1lti95i0
requited), where m is some standard encoding of the voter choices
(desctt'bed herein), the a; are generated secretly by the voters, and h is a
public parameter constretcted via a desIerleSs secret sharing scheme (see,
e.g, T. Pedersen_ A threshold ctyptosystem without a trusted party,
Advances in Cryptology - EUROCRYPT '9I, Lecture Notes in Computer
Science, pp. 522-526, Sponger-Verlag, 1991.), Once the polls are closed
(voting finished), an independent collection of authorities sequentially
shuffles the ballots. Qn output of the final shu$le, the final collection.of
encrypted ballots is decrypted in accordance with the threshold scheme,
and the clear text votes are tabulated in full view by normal election rules.
The authorities who participate in the sequential shuffles,
may be arbitrary in number, and they may be completely different from
those who hold shares of the election private key. The sequence of
ballots which are finally decrypted can only be matched with the oarigiaal
sequence of submitted ballots if al! of the shuffling authorities collude,
since each of their permutations is completely arbitrary_
Each shuffle is performed by an individual authority as
follows:
1, ~~ are chosen secretly, randomly and iadepcadently_
2. Each vote v, _ ( g°' , h~' m ) is replaced, in sequence,
by (g'~r~,h~+°m ). A Chaum-Pedersen proof is published without
revealing the secrets.
3. A shuffle with secret exponent c is performed on the
resulting encrypted votes.
4. Steps 1-2 are repeated.
5. At this point, the messages that are encrypted are the
c-th power of ttte original messages. This is easily fixed by raising each
coordinate of each vote to the 1!c power. A Chantn-Pedersen proof of
this operation is equally easy to provide, thus keeping c secret while
convincing verifiers, by simply reversing roles of g and C = g'.
Steps 1 cad 2 above help randomize the input data. to
prohibit one from tampering with it such as selecting a relationship
19
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
09%19/2002 09:55 FAg (~J032
w0 07173694 pCTItJS01109550
between ballots before shu~licvg. The Chaum-Pedersen proof ensures the
correctness of the additional value added for this raadamiriag. In an
alternative embodiment, steps 1 and 2 may be. omitted (and step 4).
7. Secure Messaee Encoding
Ifp-1 has small prime factors, some information about the
encoded messages can be leaked. This is not a problem with the shuffle
protocols, rather it is a problem for strongly encrypting the m, in the first
place. Whether or not this is significant enough to worry about depends
on the expected value of the messages to be encoded. 'Ibis problem can
also be eliminated however, by taking special care in. the encoding. Each
message can be projected onm a subgroup whose order contains only
large prime factors. Since most embodiments described herein are
restricted to the case where Kg~l is a prime, g, we will only discuss in
detail the case p = 2q + 1. However, the more general case can be
handled by an extension of these techniques.
Suppose that the bit length of p = 2q + 1 is b, that is
2m <P<2b
so
2''~ 5(p-1)~2=q <2°' (15)
We require that all messages m be of bit length at most b-
2. Rather than enorypting each messagt as ( g° , h°m ) as is
standard, we
encrypt it as
( 8''. h'mx )
Thus means that all messages are encoded with the same trivial projection
on the order 2 subgroup of Z~ . Equation 15 guarantees that the map
m -s ma is invertible on the domain of definition. To invert, simply take
sUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
09'19/2002 09: 5B FAX C~ 033
WO n1/7369a pCT/US01/09550
the unique square root which is less than (p-1)~2. Thus it is a simple
matter to recover the original message, m, once the actual message, mz,
has been decrypted.
8. Suitable S~rstem
Figure 1 and the following discussion provide a brie
general description of a suitable computing environment in which aspects
of the invention can be implemented. Although not required,
embodiments of the invention will be described in the general context of
computer-execurable instructions, such as routines executed by a general-
pmrpose computer, such as a personal computer or web server. Those
skilled in the relevant art will appreciate that aspects of the invention
(such as small elections) can be practiced with other computer system
configurations, including Internet appliances, hand-held devices, wearable
computers, personal digital assistants ("PDAs"), multiprocessor systems,
microprocessor-based or programmable consumer electronics, network
PCs, mini computers, cell or mobile phones, set-top boxes, mainframe
eocnputers, and the like_ Aspects of the invention can be embodied in a
special purpose computer or data processor that is specifically
progruruned, configured or constructed to~erForm one or more of the
computer-executable instructions explained herein. Indeed, the term
"computer," as generally used herein, refers to any of the above devices,
as well as arty data processor.
The invention cart also be practiced in distributed
computing enviranments where tasks or modules are performed by remote
processing devices, which are linked through a communications network,
such as a Local Area Network (LAN), Wide Area Network (WAN), or the
Internet. In a distributed computing environment, program modules or
sub-routines may be located in both local and remote memory storage
devices. The invention described herein may be stored or distributed on
computer-readable media, including magnetic and optically readable and
removable computer disks, stored as fumware in chips, as well as
21
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
09/19i2002 09:58 FAg f~034
WO OI!'7369d PCTJUSOI/09530
distributed electronically over the Internet or other networks (inducting
wireless networks). Those skilled in the relevant art will recognize that
portions of the protocols deseiibed herein may reside on a serves
Computer, while corresponding portions reside on client computers_ Data
structures and transmission of data particular to such protocols are also
encompassed within the scope of the invention.
Unless described otherwise, the construction and operation
of the various blocks shown in Figure 1 are of conventional desigi. As a
result, such blocks need not be described in fiuther detail herein, as they
will be readily undesstood by those skilled in the relcvsnt art.
Referring to Figure 1, a suitable environment of system 100
includes one or more voter or client computers 102, each of which
includes a browser program module 104 that permits the computer to
access and exchange data with the Interact, including web sites within the
World Wide Web portion 106 of the Internet. The voter computers 102
may include one or more central processing units or other logic
processing circuitry, memory, input devices (e.g., keyboards,
microphones, touch screens, and pointing devices), output devices (e.g.,
display devices, audio speakers and printers), and storage devices (e.g.,
fixed, floppy, and optical disk drives), all well known but not shown in
Figure 1. The voter computers 102 may also include other program
modules, such as an operating system, one or more application programs
(e.g., word processing or spread sheet applications), and the like. As
shown in Figure 1, there are N number of voter computers 102,
x~epresentiag voters 1, 2, 3 . . . N.
A server computer system 108 or "vote collection center,"
coupled to the Internet or Wvrld Wide Web ("Web") 106, performs much
or all of the ballot collection, storing and other processes, A database
110, coupled to the server computer 108, stores much of the Web pages
and data (including ballots and shu$le validity. proofs) exchanged
between the voter computers 102, one or more voting poll computers 112
and the server computer 108. The voting poll computer l I2 is a personal
22
SUBSTITUTE SHEET (RULE 2s)
CA 02550259 2001-03-24
computer, server computer, mini-computer, or the like, positioned at a
public voting location to permit members of the public, or voters who
may not have ready access to computers coupled to the Internet 106, to
electronically vote under the system described herein. Thus, the voter
computers 102 may be positioned at individual voter's homes, where one
or more voting poll computers 112 are located publicly or otherwise
accessible to voters in a public election. The voting poll computer 112
may include a local area network (LAN) having one server computer and
several client computers or voter terminals coupled thereto via the LAN to
thereby permit several voters to vote simultaneously or in parallel.
The voting poll computer may also include an rButton
reader for reading iButtons, such as cryptographic iButtons provided by
DaTIas Semiconductor Corp. An rButton is a 16 mm computer chip
armored in a stainless steel can that may include a microprocessor for
high-speed arithmetic computations necessary to encrypt and decrypt
information, such as signatures of voters who have registered.
_ Of course, other
data storage devices besides iButtons may be employed, such as computer
readable media described herein, radio frequency identification (RFID)
tags, one or two dimensional bar codes or other data collection devices,
and associated readers for these.
Under an alternative embodiment, the system 100 may be
used in the context of a private election, such as the election of corporate
officers or board members. Under this embodiment, the voter computers
102 may be laptops or desktop computers of shareholders, and the voting
poll computer 112 can be one or more computers positioned within the
company (e.g., in the lobby) performing the election. Thus, shareholders
may visit the company to access the voting poll computer 112 to cast their
votes.
One or more authority or organization computers 114 are
also coupled to the server computer system 108 via the Internet 106. The
authority computers 114 each hold a key necessary to decrypt the
23
CA 02550259 2001-03-24
WO 01173694 PCr/USOLO956o
electronic ballots stored is the database 110. Threshold crypt<rgraphic
systems require that a subset t of the total number of authorities n (i.e.,
tin) agree to dectypt the ballots, to thereby avoid the requirement that all
authorities are seeded for ballot decryption. 1n other vYVrds, the objective
of s threshold cryptosystem is to share a private key, s, among n members
of a group such that messages can be decrypted when a substantial subset,
T, cooperate - a (t, n) threshold aypbosystxm. Protocols are de$ned to (1)
generate keys jointly among the group, and (2) decrypt messages without
reconstructing the private key. The authority computers 11A may provide
their decryption share to the server computer system 108 after the voting
period ends so that the server eoraputer system may decrypt die ballots
and tally the results.
Furthermore, undo the depicted embodiment, each of the
authority computers perform one shu$le of the ballots, as described
herein. In conjunction with each shuffle, each authority computer
generates a shuffle validity proof, which may be encrypted cad forwarded
to the server computer 108, or stored locally by the authority computer.
In as alternative embodiment, an additioasl set of authority computers are
provided, where one act of authority computers shu$le the encrypted
ballots and generate shuffle validity proofs, while the second set of
authority computers employ keys shares for decrypting the ballots.
One or more optional verifier computers 130 may also be
provided, similar to the authority computers 114. 'The verifier computers
may restive election transcripts to verify that the election bas not been
compromised. For example, the verifier computers may receive the
.shu$le validity proofs from each o~ the authority computers, as described
herein. The verifier computers may perform verifications aft~a the
election, and need not be connected to the Internet. Indeed, the
verifications may be performed by other coraputrss shown or described
herein..
the server, verifier or authority connputers rnay perform
voter registration protocols, or separate registration computers may be
24
SUBSTITUTE SHEET (RULE Z6)
CA 02550259 2001-03-24
w0 01/7369; PCT/ITSO1/0955D
provided (not shown). The registration computers may include biometric
readers for reading biometric data of registrants, such as fingelpaitlt data,
voice fingerprint data, digital picture comparison, and other techniques
lozown by those skilled in the relevant art. Voter registration and issuing
anonymous certificates for use with ve 'nflable shuffles is described below.
The seer computer 108 includes a server engine 120, a
web page management component 122, a database management
component 124, as well as ottrer components not shown_ 'fheserver
engine 120 performs, in addition to standard functionality, portions of the
electronic voting protowl. The encryption protocol may be stored on the
server computer, and portions of such protocol also stored on the dient
computers, together with appropriate constants. Indeed, the above
protocol may be stored and distributed on coxaputer readable media,
including magnetic and optically readable and removable computer disks,
microcode stored on semiconductor chips (e.g., EEPRQIVn, as well as
distributed electronically over the Internet or other networks. Those
skilled in the relevant art will recognize that portions of the protocol
reside on the server computer, while corresponding portions reside on the
client computer. Data structures and transmission of data particular to the
above protocol are also encompassed within the present invention. Thus,
the server engine 120 may perform all necessary ballot transmission to
authorized voters, ballot collection, verifying ballots (e.g_, checking
digital signatures and passing verification of included proofs of validity in
ballots), vote aggregation, ballot decryption and/or vote tabulation. Under
an alternative embodiment, the server engine 120 simply collects all
electronic ballots as a data collection center. The electronic ballots are
then stored and provided to a third party organization conducting the
election, such as a municipality, together with tools to shuffle ballots,
decrypt the tally and produce election results. Likewise, election audit
inforiaation, such as shuffle validity proofs and the like may be stored
locally or provided to a municipality yr other organization.
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO 01/73694 PCT/US01109S5o
The web page component 122 handles creation and display
or routing of web pages such as an electronic ballot box web page, as
described below. Voters sad users may access the server computer 108
by mesas of a URL associated therewith, such as
htxp:\\w~uvw.votehere.net, or a URL associated with the election, such as a
URL for a municipality. The municipality may host or operate the servez
computer system 108 directly, or automatically forward such received
electronic ballots to a third patty vote authorizer who may operate the
server computer system. The URL, or any link or address noted herein,
can be any resource locator.
The web page management process 122 sad server
computes 108 may have secure sections or pages that may only be
accessed by authorized people, such as authorized voters or system
administrators. The scryer computrr 108 may employ a secure socket
layer ("SSL") and tokens or cookies to authenticate such users. Indeed,
for small elections, or those where the probability of fraud is low (or
results of fraud are relatively inconsequential), the system 100 may
employ such simple network security measures for gathering and storing
votes as explained below, rather than employing complex electronic
encrypted ballots, as described in the above-noted patent application.
Methods of authenticating users (such as through the use of passwords),
establishing secure transmission connections, and providiryg secure
servers and web pages are lmown to those skilled in the relevant art.
The election scheme and system uses a "bulletin board"
where each posting is digitally signed anal nothing can be erased. See
papers by K Sako, J. K~iia~ R. sad Cramer, R. Gcnnaro, B.
Schoenmakers_ The bulletin hoard is implemented as a web server, The
"ballot box" resides on the bulletin board and holds all of the encrypted
ballots. Erasing can be prevented by whiting the web server data to a
write-once, read-many (WORM) permanent storage medium or similar
device. Further details on such a bulletin board system are found in U.S.
26
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO Ol/7369~ PCT/IlSo1l095io
Patent Application No. 09/534,836, entitled "Electronic Voting Scheme
Fsaploying Panaaneat Ballot Storage."
Note that while one embodiment of the invention is
described haeia as employing the Iatemet to connect computers, other
alternative embodiments arc possible, For exsraple, aspects of the
invention may be employed by stand alone computers_ Aspects of the
invention may also be employed by say interconnected ilam processing
machines. Rather than employing a bmwser, such machines may employ
client so$ware for implementing aspects of the methods or protocols
described heroin.
9-EI ct~on Expmple
One application of the gaieral k shuttle protocol is in the
area of electronic voting. In order tA make an election universally
verifiable, submitted ballots must initially be irrefutably connectable to a
valid (i.e., registered) voter. Somehow ballots must be "separated from
their signatures" by a verifiable process - i.e., one that does not allow
phony ballots to be substituted in the separation process - before they can
be "opened".
The protocol we present here relies on a set of N "tabulation
authorities" with differing interests is the election results.
1. The protocol is a threshold scheme in that at least t
aufhorities must behave honestly in order for tabulation to be completed.
(The parameter t can be chosen in advance of ~e election~to be nay value
1 S r S N.) Thus, in paxticular, it is not necessary that the authorities
complete their shuffles in any particular order, nor is it even necessary
(except in the special case t ~ N) that all the authorities participate.
2. Even if all the authorities conspire, they cannot
produce false election results without being caught by as external auditor
who wishes to verify the rtsults
3. Privacy of sa individual vote catv only be
compromised by a conspiracy of at least r of the authorities to do sa_
27
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
wo oin3s9a pcr~rsoiro9sso
The protocol proceeds as follows:
First: Initialize Election
1. The sutborities first agree on the election parameters:
(a) Parameters necessary for any election,
including: the set of eligible voters, the ballot
duestions, the ballot answers, the ballot style,
the time the polls are to be opened and closed,
ctc.
(b) The collection of tabulation authorities: i.e.,
themselves. (We henceforth use N to denote
the number of authorities in this group.)
(c) .~ The threshold parameter, 1.
(d) A shuffle parameter, 1 ~ a S t. (s = t is a
natural choice.)
(e) A group G and a subgroup generator, g a G.
(In order to achieve secure encryption, the
prime factors of ~ should be large, however,
this requiranent is, of course, open to
interpretation by the autharities thennselves.)
(fj A standard "bit encoding" for responses)
(e.g_, ASCII) and a small "message
multiplicity" integer d Z 1. The message
multiplicity refers an agreed upon subdivision
of each ballot, and corresponds to ballot
formatting (similar to the layout of a paper
ballot to indicate where responses to each
ballot question are to be located). d is
typically chosen as small as possible to
28
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO 01/73694 PCTIUS01/09550
accommodate the ballot response size. Most
often, d = 1 will world because the message
multiplicity is determined by the key lengdz,
and because a sufficiently large key length
(e.g., 1024 bits) can accommodate most
baDots having a ressonable number of
questions.
(g) A group element h a (g) which is created by
way of an (N, t) - secret clearing scheme
executed by the authorities. (See, T. Pedersen
article.
2. Once agreennent is reached on the election
parameters, the authorities all "sign" them, and some representation of
this signed set of parameters becomes the signed ballot,
Second: Vote
1. During the election (i.e., while "polls are open"),
each voter V . encodes his responses) by the election standard "bit
encoding" (agreed upon and signed by tie authorities during election
initialization - see above) into a sequence of messages, m~,.." nod a G.
(More on this in section below.) The "message multiplicity," d is another
election parameter (see above).
2. Y selects exponents cr,,...,ad independently at
random from 0 S a~ < ~ for the encryption.
3. Y returns to the ballot collection center, the
encrypted response sequence
(8''> h°'m; )...., (8°'> ha', ma) (16)
along with an "attached" digital signature, created by Y, to authenticate
the response by tying it to a particular eligible voter.
29
SUBSTITUTE SHEET (RULE ~6)
CA 02550259 2001-03-24
wo oir~~ rCrmso~ssu
4. If the digital signature submitted by Y verifies and Y
has not previously been issued a ballot, then Y is issued a receipt, sigied
by the cenn~al collection agency. This receipt ac3anowledges that a ballot
from this votes, in this particular election has been received, but includes
no information (not even encrypted or hashed information) about the
contents of the ballot. 'the receipt may also be broadcast to the voter.
The receipt also serves to confirm that the voter's ballot was not lost and
not maliciously deleted.
Thlrd: Tabulate Results
1. At the start, the collection of voter responses are laid
out in 2d sequences, each of length N~,, where N~,sr is the total number of
ballot responses rcccived. Fach sequence corresponds to a coordinate in
the standard ballot response format (equ~ttio~n ~ø). The entries is each
sequence are ordtrcd by voter. The index assi~ed to each voter is not
important, just so long as the indicts are consistent, This way, an external
observer can check that the signed ballots have been transformed in a very
simple way, and that, applying the night interpretation to the data layout, it
still represents the same set of responses that were signed arid received.
2. In any convenient order, a sequence of s authorities
each execute the following steps:
(a) Let S be the authority currently in sequence.
(b) S selects independently at random aBV~"
exponents
I<_~gf~c~g) lSj_<N~"andl5l~d
(c) S calculates ~e group elements gs v~ n = g°p
sad hr (j, ~ = i~~~' . further, as intermediate
Chaum-Pedersen proof is generated on (g, g~(
J~ ~~ H~ hs~J~ ~)..
30
8UB5TITUTE-SNEET (RULE 26)
CA 02550259 2001-03-24
WO O1/7369.i PCT/US01/09550
(d) S then transforms the 2d input sequences into
2d intermediate sequences. The j-th entry of
the 1-th input sequence of the form ga m is
transformed by multiplying it by gs ~', ~ and
the j-th entry of the 1 th input sequence of the
form h°ni is transformed by multiplying it by
ha (j, Q. The transformed entries are ail. kept
in the same order.
(e) S chooses a random exponent 0 5 c < fig/, and
a random permutarion fi a ~N~, and
commits ha = g'.
(f) S then executes a geaeral k-shuffle (with k =
N~) on each of the 2d intermediate
sequences, using the secret parameters c and
9r1, and rearing the same simple k shuffle as
the basis for each general k-shuffle. (This
ensures that each of the Zd sequences are
subjected to the.same secret "permutation".)
(p~ (i) S repeats step (d) with new random pi's.
(ii) raising each coordinate of each vote to the
1/c power and providing a Chaum-Pedersea
proof of this operation, thus keeping c secret
while convincing verifiers, by simply
reversing roles of g aad C = gs:
(h) (Note that S need not explicitly compute the
intermediate sequences at this stage. ?hey are
necessary for external verification later, but
the output can be computed directly and the
intermediate sequences constructed on request
31
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO 01/73694 PCT/I1S01/09550
of an auditor. However, security concerns
may dictate that the auditor perform the
verifications before beginnnng the next
shuffle.)
3. Shu$led ballots are now reconstructed by combining
entries of each of the 2d sequences ia~ the same way they were formed.
4. Finally, t authorities execute the threshold decryption
protocol on each shu$led ballot.
In general, the tabulation phase includes two subphases.
First, a sot of T _< t of the tabulation authorities each execute, in
sequence,
a verifiable k x d shuffle (where k is the total number of ballots cast).
The output sequence and proofs from each shuffle is signed and passed to
the next tabulation authority. (Each tabulation authority executes its
shuffle only if the input Sasses both a signature check and a check of the
(previous) shuffle zero-latowledge proof ("ZKP") and the intermediate
Chautn-Pedersen proofs.) Second, once the full round of shu$les have
been executed and verified, a set of r tabulation authorities use their secret
key shares to jointly (and verifiably) compute a decryption of each m's in
the final set of filCiatnal pairs.
In general, each shu$ling authority will latow the input-
output correspondence, since it is responsible for generating the
permutation in the first place. However, shuffles are staged. Thus the
output of one shuffle is used as the input to another shu$le performed by
a different shuffling authority. Thus, unless all authorities conspire, no
one shu$ling authority will have any lmowledge of the correspondence
. between initial input and Seal output, As described below, however, a
further enhancealeat eliminates this possibility.
Faurth: Externally Verify Elecf9on
On request, each authority publishes
(a) His interrnediatc sequences.
32
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO 01/73694 PCT/US01/09550
(b) Chaum-Pedersen proofs P(g, g,( j, Tj, h, h,( f,
1)) for 1 5 j S N~" and 1 S 1 _< d.
(c) His k shuffle proof,
(d) The Chaum-Pedersen proofs under step (g)
about.
In general, an election trrorascrtpr may be published that
contains the following:
1. The voter roll contaiaiag voter identification
information and voter public keys_
2. The otigiaal set of k voter-signed ballots_
3. The t k x d shuffles (including proofs, as
noted above.
4, The final share decryption validity proofs.
5. The final tallies.
Remark: Several variations oa the order in which the
authorities execute their tabulation steps (Tabulation steps 2 (a) - (h)
above) are possible. Is particular, the steps can be interleaved under
alteraati~re embodiments.
Remark: The External Verification phase can be carried
out as tabulation is going on, or at a later time. The authorities need only
save their stage parameters.
Refcrrsng to Figgie 2, a schematic diagram illustrates a
basic application o~ the shu$le protocol to an election, shows as a method
200. In block 202, three eaaypted ballots are snbmiited, one each for
voters Joe Smith, Sally Jones, and Ian Kelleigh. In block 204> the list or
roll of voters is separated from the encrypted ballots, which are shown in
block 206. Thereafter, a one-way reencryption of the ballots is performed
m produce a shuffled set of ballots, shown in block 208. A shuffle
33
SUBSTITUTE SHEET (RULE Z6)
CA 02550259 2001-03-24
w0 01/73694 PC?lfSO1l09550
validity proof is generated based on this first shu$le, shown in block 210.
?he shuffle validity proof allows a third party to ensure that all input data
(the ballots) had the same operation applied to them, and that no altering
of the ballots had been performed.
A second shuffle of the (previously shu$led) ballOtS 15
performed, to generate a second shu$led set of ballots, shown as block
212. Again, a shuffle validity proof is generated, shown in block 214.
The shuffled ballots of block 212 are shuffled a third time, to produce a
final shu$led set of ballots under block 216_ A third validity proof 218 is
likewise generated based on the third shuffle. In. sum, a three-by-three
shu$le array is provided under this example. Following, the shuffling,
the ballots are decrypted to product a tally, shown as block 220. A third
parry rnay verify that the election by analyzing, among other things, each
shu$le validity pmof to ensure that each shuftler has preserved election
integrity.
The shuffle protocol is presented above as effectively
separate subroutines that may be employed for various applications, such
as in a electronic voting scheme. A first subroutine provides the
fiu~ctionality of scaled, iterated, logarithmic multiplication pmofs between
a proven and a verifier. A second subroutine provides the functionality of
a simple shu$le protocol and employs the scaled, iterated, logarithmic
multiplication proofs. Thereat~ter, a third subroutine implements general
shu$le fuactio:<ality, where the shuffler does not lmow the exponents,
building upon the second subroutine of the simple shuffle. A fourth
sub~routinc extends the third subroutine to shu~Iing k tuples of elements.
~ w Referring to Figure 3, a routine 300 is shown for
implementing scaled" iterated, logarithmic multiplication proofs. In block
302, initial cryptographic parameters are agreed upon, such as by a voting
organization_ These initial parameters include the group (e_g., ZD), a
subgroup operator g, the size of the group G, and the size of the generated
subgroups p and q. This information may be provided to a number n of
shu$ler or authority computers 114 and verifier computers 130.
34
SUBSTITUTE SHEET (RULE Z6)
CA 02550259 2001-03-24
WO 01/7369 PCT/U'S01/09550
In block 304, the shuftler (or Drover P) selects a secret
exponent c, and based on the subgroup generator g generates C.
Additionally, the shu~ler may receive or generate Y values for received
X's and, for indexes of i for 1 through k, and provides the Xs, Y's, and C
to the verifier_
In block 304, the shu8ler also seerady generates random
exponents as ri, which, based on the subgroup generator g, are used to
generate valves R~ for each value of i of 0 through k. Similarly, under
block 304, the shu$ler employs the generated random exponent r, to
gtnerate Wi and Z,.
In block 306, the shu~ler provides Chaum-Pedersen proofs
for each. clement 1 through k for the values of Rte,, Xw R;, W,, and Yw C,
Wb Z,. These values for the Chaum-Pedersen proofs are then provided to
the verifier, together arith values z, and Ro. The vezifier then, in block
308, verifies the correctness of the proof data to accept or reject the proof
Ia other words, the verifier checks that each z, as as exponent to the
subgroup generator g, generates a corresponding Z, checks each Chauro-
Pedersen pmo~ checks that the product of the zf s is equal to z, and that
the value RD raised to the power z is equal tctRk.
Referring to Figure 4, a routine 400 is shown for performing
a simple shuffle protocol, as described above. Following block 302, the
block 404 is similar to block 304, but the shu$ler shuffles the X eleaaents
by a permutation a to generate the Y elements. 'Ihe verifier in block 406
generates a random value t as a ehallenge_ In response, the shuffler is
block 408 uses t as an oxponem to the subgroup generator g to secretly
generate the value T, which, when combined with the shuffler's secret
exponent c, permits the shu$1er to secretly generates a value S. As
shown, the shuftler they publicly generates values U and v and provides a
Chaum-Pedersen proof for (g, C, T. ~ ~ block 410. In block 410, the
shu$ler also generates proof data as scaled iterated logarithmic
multiQlication proof for each of the elements X and Y in the series of i of 1
through k. The proof data is then provided to the verifier in block 412.
35
SUBSTITUTE SHEET (RULE Z6~
CA 02550259 2001-03-24
we oin3s9s pcrmsovo9sso
The verifier verifies the correctness of the proof data and accepts or
rejects it In other words, the vaiBer executes the scaled iterated
logsrithtnic multiplication proof protocol noted above for ~e sequcrnces
of U and V, and checks the commitment value C_
Referning to Figure 5, a general shu$le protocol SOD is
shown where the shu#ler does not know the exponents. The initial steps
in the protocol 500 are similar to that of 400, except that the verifier adds
a raado~,~ element to the shu8ler's secret exponents. As shown in
block 502, the shuffler secretly generates a random sequence of initial
values, which are used as exponents with the subgroup generator g to
generate an initial sequence (t7! =g' ). Likewise, in block 504, the
veri5a secretly generates another seqneaee of elements a for values l of 1
through k, and provides the sequence to the shu$ler as a challenge. In
block 506, the shut~ler secretly adds the sequence challenge a to the
previous sequence, to then publicly generates a series of values t! (U, _
g4U! ~.
In block 508, the shu$ler constructs a simple k shuffle on
the sequence U with another secretly generated ~ conzmitmcnt D (that
employs a different secret exponent d chosen by the shu$ler) and
generates a sequence of values V Then publicly, the shu~ler reseals
t,'.hautn-Pedersen proofs for a sequence of values A and B for indexes 1
through k, publicly generates the product of the sequences as values A
and B, and provides a Chaum-Pedersen proof for the relatiaa between D,
A, C and B, as shown. Under block 510, this proof data is provided to the
verifier, who verifies it under block 512.
_r ~~
10. Issuino norvmous Certificates With Verifiable Shuf~lea
Presented above is a new, efficient construction for
veritably shu$ling encrypted data, and a particular way that this
construction can be used to conduct a ~rnivarsally verifiable electronic
election system. That system depends on a collection of election
authorities to "shu$le," or "anonymize" the ballot data that has been
36
SUBSTITUTE SHEEP (RULE 16)
CA 02550259 2001-03-24
WO 01/73fi9~ PCT/USULU95S0
collected at vote time. ?his process takes place after aU votes have been
cast, but before ballots am decrypted and tabulated, The validity
construction prevents any one or more of the election authorities from
making any changes to the original election data without being discovered
by anyone auditing the final election transcript.
A disadvantage with this approach is that voter anvnymiry is
not protected by as strong a mechanism as is election integrity. Election
integrity is protected by pure computational intractibility-it is essentially
impossible for the election authorities to produce false election results
without detection-even if they arll act in collusion. However, by acting
in collusion, they are able to determine the contents of any individual
voter's ballot with relative case.
The same underlying shuffle construction can be used to
construct a new election protocol that eliminates this weakness. The idea
is to awve the shuffling to the registration, or ballot request phase of the
election, thereby anonynuzing the identities of the voters without losing
strict control, and audit of election eligibility rules-i_e., only ballots
cast
by registered voters should be counted, and multiple ballots from the
same voter should not be accepted. With. this accomplished, it is no
longer avert necessary to encrypt ballots, and tabulation can be performed
"in the clear =which is obviously an easy process to audit.
The idea of using the construction as part of an anenyrnous
registration process has applications beyond voting. Any situation where
access to a resource, such as a server or file, needs to be limited to
authorized personnel, but where those who are authorized wish to protect
their individual identity, may use this wnstruction to meet both
requirements simultaneously. For example, applications of group
signatures may be equally applicable to the protocols described herein.
Note also that the term "voter" is generally used herein to refer to any
individual or organiizarion that employs some or all of the protocols
described herein.
37
SUBSTITUTE SHEET (RULE Z6)
CA 02550259 2001-03-24
WO Ol/7369~ PC1'1U501/095.50
Outline of the Protocols
Two protocol variants are provided, both of which follow
the same high level flow of information. Each protocol begins with the
assumption that a set of public keys has been stored in some central
authentication database, or certificate server. Each corresponding private
key is known by one, end only one, eligible votes. Furthermore, the
correspondence between public key sad individual voter is known by the
entity, or entities, who control the certificate server. ('The exact form of
these public/private key pates are slightly different in each variant of the
protocol.) In practice, the public keys will likely be wrapped in the form
of a digital certtfircate which ties ate idenbfjning information together with
the public key in a single piece of formatted data (This is the convention
followed by widely accepted Public Key Infrastructures, or PKTs.)
Typically, this distribution of keys and certificates wiD be
accomplished by a tightly controlled registration process, the most secure
of which would be an "in person" registration process where the voters
can be physically identified at the time of certificate generation. (Suvh
registration processes are described in detail in U.S. Patent Application
No. 09/534,836 noted above.) It is important to distinguish between two
di$erent types of ccrbhcates that exist in the protocols. The first type are
the certificates just described, where the association between public key
and individual person is publicly, or at least widely known ("standard
certificates"). The second type are the certificates that will be distributed
in the stages of the protocol that follow the initial registration phase just
described ("anonymous certij~cates"). These anonymous certificates are
-distinguishable from each other, at very least by the fact that they contain
different public keys, however, the only individual who knows the owner
of a gven anonymous certificate is the owner himself. It is the goal of the
protocol to guarantee that
~ Only individuals who own one of the standard certificates
are issued an anonymous certtf' tcate.
38
SUBStITUTE SI~IEET (tZULE 261
CA 02550259 2001-03-24
WO Ol/'f369-~ PC't/I1S01/U95.50
In most applications, such as ~e voting application, it is
also the goal o~ the protocol to guarantee that
Each individual is issued only as many anonymous
certificates as he/she has standard certiscates. (Usually,
each owner of a standard cerdScate v~n'll have only one
standard certificate)
Once the registration of standard ceriiScates is cotnplLte,
the protocol variants each proceed as follows.
Initisliretion: A set, K, of raw public keys is corutructed at
the certificate server (e.g., server 108), and initially set to be the set of
public keys associated with the set of standard certificates. The set of
public keys is generated during the initial registration process of each
individual, when that individual registers and receives, for example, a
standard digital certificate. ?he public keys generated under the initial
registration process are pooled together to generate the set X. Each
individual holds a private key associated with one of the public keys is
the set K.
1. An individual, P, contacts the certificate serv~ei; S, through a
digital communication channel (such as the Internet)
indicating that he wishes to obtain au anonymous
certificate.
2. S ret~nns to P a sat, H a K , of public keys (which includes
Ss public key), and stores the set J = 1i' - H . (Ideally,
H = X and J = 0 , but for reasons of communication
bandwidth, the inclusion may be proper. For example, a
subset of the public keys K may be provided to the
individual P where the set of public keys is quite large, and
bandwidth constraints for transmission effectively Iimit
transmission of such a large set of keys. For other reasons,
39
SUBSTITUTE SHEET (RULE is)
CA 02550259 2001-03-24
WO oill3s9; pCTlUSo11o9550
the certificate server may wish to return only a subset of the
public keys.)
3. P selects a subset M ~ H , which may be all of H, and sets
M'~H-M
4. P computes X' which is a shuffle transformation ofM_ (See
above and the following sections.) P also generates a
formatted anonyntovs cent fcate requesr_ 'This is done by
generating a random public/private key pair, and formatting
tho public part with some "random )D" data to conform to a
specified certificate format. (Needless to say, P must also
store the private part in some safe place.)
5. P returns X ', M and M' to S along with
(a) The shu, j'le transcript, or validity proof, wrhieh
proves to S, or any ar~ditor, that X' is, in fact, a valid
shuffle transformation ofM.
(b) A proof that P knows the private key corresponding
to a particarlar element, h a fl'
(c) The formatted certificate request.
6. S checks that H = M v M' along with the validity of both
Sa and Sb.
(a) If ar~yr of the checks fail, S indicates failure to P and
either terminates the contircunication with P, or gives
P an appropriate chance to retry_
(b) If both checks pass, then
40
SUBSTITUTE SHEET (RULE Z6)
CA 02550259 2001-03-24
WO Oi17369.t pC"I/US01I095E0
i. . If anonymous certificates are intended to be
issued only a»ce to each owner of a standard
cert~cate, S sets
g~~' H~_~~ (17)
x=.r~~.r~~xw (1g)
or, if, for some reason, it is desired to issrce
anortyno~rs cert~cates nrulttple times to each
owner of a standard carti~cate, S sets
x =r~~.r~~x~ (19)
ii. Anc~ S digitally signs the formatted certif'~rcate
request thereby creating an anareyrnorcs
certificate-returtrs the (signed) certificate to
P, and stores tits certt,Jlcate in the data base
for later anonymous authentication.
7. The pmcess now continues from the beginning with a new
P, and x appropriately modi5ed.
In other words, the individual P may prove to the certific$te
server S that the individual holds a private key associated with one of the
public keys is the subset M selected by the individual, without revealing
which one by shu$ling the subset M of public keys. After issuing an
ano~rmous certificate, the certification setvrer then removes the one
shuffled public key from the shu#lled set of public keys for use by the
next iadividusl requesting an anonymous certificate.
Anonymous Authentication and Sigoatur~ea
The basic construction a~f the shu$le protocol above solves
the following problem.
41
SUBSTITUTE SHEET (RULE Z6)
CA 02550259 2001-03-24
wo oirrssss pCTIUSOi/o9sso
General It Shuffle Problem: Two sequences of k elements
of ZP, S = ~X,,...,~L'k ~, and T = ~1;,...,Yt ~ are publicly laiown. Is~
addition, ~t constant c a Zq is lmown only to P, but a commitment of
c, C = g° is made known to V P is required to convince V that there is
some permutation, st E ~k , with the property that
Y"~r~ = X; (2Q)
iwr all 15 t 5 k without reveali:lg stay information about ~c or the secret c.
In the shuffle protocol above the solution to this problem is
first presented as as interactive proof protocol executed by P and V, but it
is made non-imeraetive by standard application of the Fiat-Shamir
heuristic. We denote the resulting verification transcript, produced by the
shuffler, P, by T (S, T, g, .C7,
Anonymous A~rthentication Protocol 1
rn this variiant of the protocol
~ the public keys are elements h E (g) c Z, , and the
eorr~sponding private keys are simply the socaret exponents,
s = lost h ,
~ The set H must always be taken to be all of K, i. e. H = K .
The set M must also always be all of H, i. e. M = X and
M'=o.
. S must store one additional modular integer, G a ~g~, which
will be modified duriag each autlneatication session. At
iaitislizatioa, G is set equal to g_
The protocol proceeds as described in the previous section,
with the following modifications_
1. In step 2, S must also return G to P.
42
SUBSTITUTE SHEET (RULE 26j
CA 02550259 2001-03-24
WO 01/'7369; PCZYtJ501/09550
2. The tcsnscript that is retuincd to P in step Sa is exactly
T(M,H',G,C)=T(H,H',G,C) (21)
3. The proof of private key latowledge in step Sb, is exactly
the integer a = cs ~ Z9, along with the particular value
h' a H' (or its index) which satisfies
h' = G' (22)
Note that there will be one, and only one, such value.
Further note that since c is random and independent of s,
revealing a does not reveal information about s. The
corresponding check that S perfvtms is simply to verify
equation 22.
4. 1~f the checks in equation 22 all pass, then in additiozt to the
transformations performed is 1 and 2, S also performs the
transformation
G = C (23)
Anonymous Autbentication Protocol Z
A shortcomiltg of the first anonymous authentication
protocol is that the set to be shuffled by P must always be all of X. The
same transformation (exponentiation) is applied to all public keys in the
set H~K Since tech of the transcripts T(H,H',G,C), must be stored
until all audit requirements are fulfilled, this can create a large amount of
data if the original set of standard certificates is large. This problem is
addressed with the following second anonymous authentication protocol.
In this variant of the protocol
43
SUBSTITUTE SHEET (RULE 26)
CA 02550259 2001-03-24
w0 oinss9s PCTIUSoi/o9550
The public keys are pairs of elements (k, h) E ~g~ x (g), and
the corresponding private keys are simply the secret
exponents, s = log k h .
Ihc set H must contain P's public key. This can be
achieved in s variety of ways.
1. S and P can engage in a series of retries until this
property ofH is achieved
Z. or, at initial registration, standard certificates can be
assigned to "blocks. " When P first contacts S, he
identifies himself only so far as his block number.
Effectively, a difFereat base G is act for each individual P,
aad the individual shuffles only a subset of the entire set of public keys
(which subset includes the voter's public private key pair). The protocol
proceeds as described in the previous section, with the following
modifications.
1. The transcript that is returned to P in step Sa is the shuffle
transcript fvr the set of pairs. See above for the details of
this construction.
Z. The proof of private key lmowledge in step Sb, needs to be
a bit more complicated in order to avoid revealing the
private key.
(a) P must Indicate to S a particular pair, (k', h'~ a H',
or its index, which is the new index ojthe pair
belonging to P's private key. That is, h' _ (k ~l.
(Notice that such a pair exists uniquely since the
shu,8?e operation esponentiates both the k's and the
h's Iv the same secset ezponent c. So h=k' if, and
only if, h' _ (k')' .)
44
SUBSTITUTE SHEEP (RULE 26~
CA 02550259 2001-03-24
WO 01173691 ptTJt1S01l09550
(b) P reveals to S a 'hero-~owledge proof that he, P,
knoyvs s = logs h : (See the Chaum articles,) This
proves that P knows the corresponding private key
without revealing it.
3. The corresponding checks that S must perform are obvious.
(a) S checks the varlidity of P's shrr~le trr~nsc~pt . ,
(b) S checla the validiry of P's proof that he known that s
= lo8a~s.
Note: under an alternative embodiment, some or all of the
keys in the set K (1.e., the subset ~ may be shuffled by certain
individuals or authorities before any one individual requests an
anonymous certificate. In other words the pool of public keys stay be
sufficiently ra:tdomized before eithtr of the above anonymous
authentication protocols are employed for a particular requesting
individual. As s result, a smaller subset of public keys may be selected by
each individual under Protocol 2_
Referring m Figure 6, an ex~nple of a routine 600 for
implemtenting the first variant of the anonymous certificate distribution is
shown. After initializing cryptographic parameters is block 302, a
stutdard set of public keys H are provided, in block 604, which may be
collected by a registration set~rer after a set of registrants or voters have
each registered and submitted public keys h (that comspond to
individually held private keys s, as shown in block 606). In block 60B,
the subgroup geue~ g is set to G.
In block 610, an optional randomization performed by one
or more authorities may be performed. Under block 610, in sequence,
each authority perfornas a verifiable shuffle on the set of standard public
keys H nsiag (G, C-G'~ as a shu$le commitment, where c is a secret key
held by the authority. Each authority rchans the shuffled set of public
keys, H', along with shuffle verification transcript, T (H, H', G, C~ by
45
SUB8T1TUTE SHEET (RULE 26)
CA 02550259 2001-03-24
WO 01/7369a PCT1U5o1/o9550
employing the general shuffle described above. If the verification
transcript is correc'f, then the registration server performs the
substitutions
G~C and HsH; and stores the previous values, along vrith the shu$le
verification transcript for later auditing purposes_ The optional
randomization under block 610 may be performed as part of the previous
initialization, or at any intermediate stage of anonymous certificate
generation described below.
Blocks 612-618 represent a single request for an ananymous
certificate by an individual who previously provided one of the public
keys h in the set H. These steps are repeated for each requesting
registrant. In block 612, the registrant (or more accurately, the voter's
computer 102) generates a request for an anonymous certificate. In
response thereto, the registration server retrieves the value G , and the set
of public keys H under blocks 6I4 and returns them to the registrant. 1n
block 616, the registrant computes a shuffle and corresponding
verification transcript under the general shu$le protowI described above
and returns T (H, H; G, C) and a (which is equal to cs, known only to the
registrant), for each index 1 <_ j _< k. Additionally, in block 6I6, the
registrant generates a PKI tertificate request with certain random
identifying information. The random identifying information may be any
user ID the registrant chooses to employ that cannot be used to identify
the registrant_ Under block 616, the registrant also safely stores a
corresponding private key based on this request (which differs from the
private key s~).
In block 618, the registration server checks the shuffle
. verification transcript and checks that h j = G'. If both of these checks
pass, then the reBistzation server sets H ~ H' minus the one public key
used by the registrant for certification (h~ ), G ~ C and k = k 1. For
auditing purposes, the registration server in block 618 also stores the
registrant's verification transcript (i.e., T(H, H; G, C)). The registration
server also digitally signs the certificate request R to create a PKI
46
SUBSTITUTE SHEET (RULE ~6)
CA 02550259 2001-03-24
wo omas~ rcrNSoiro9sso
certificate that is rebmrned to the registrant. The routine then is ready for
the next registrant's xequest
Referring to Figure ?, a routine 700 shows the second
variant described above for anonymous certificate distribution. The
routine 700 is similar to the routine 600. Block ?04 is similar to block
604, except that the set H iacdudes public/private key Pairs, and may be a
pmper subset. Similarly, block 710 is similar to black 610, as shown in '
Figure 7.
After receiving a request, the registration server in block
714 retrieves a set H of public key pairs. Under an alternative
embodiment, the registration server retrieves only a subset that includes
the registrant's public key. 1a block 716, the registrant selects a subset of
the public key gains M and sets M' = H M. The registrant computes a
ahu~le 15f of M and a coaespondiag verification traasaipt (T (M, H: g.
G7), and generates a zero-Imowledge proof, P that the registrant lmows a
secret exponent s as shown in Figure 7. Additionally, the registrant
generates pKI certificate request with random identifying information and
stores the private key, as described above.
In block 718, ~e rtgistratia~ saver checks the shu$le
verificatian transcript and P. If both checks pass, then the registration
server sets X (with the public key pair (~f> h j ) removed under
equations(18) or (19)) and sets k ~ k-1. The remainder of routine 700 is
substantially similar to ti~at of routine 600.
11_ Conclusion
One skilled is the art will appreciate that the concepts of the
invention can be used in various envimnmcnts ether than the Internet.
For example, the concepts can be used in an electronic mail environment
in which electronic avail ballots, transactions, or forms are processed and
stored. Im general, a web page or display descritpti~ (e_g., the bulletin
board) tray be in HTNB., ?~, or WAP format, email format, or any
over format suitable for displaying information (including charaeterlcode
47
SU9STITUTE SHEET (RULE 2B)
CA 02550259 2001-03-24
WO 01/73694 PCT/USO1/U9550
based formats, bitmapped formats and vector based formats)- Also,
various communication channels, Such as local area networks, wide area
networks, or point-to-point dial-up connections, may be used instead of
the Internet. The various transactions may also be conducted within a
single computer environment, rather than in a client/server environment_
Each voter or client computer may comprise any combination of hardware
or software that interacts with the server computer or system. These
client systems may include television-based systems, Internet appliances
and various other consumer products through which transactions can be
perfo~cd.
In general, as used heroin, a "link" refers to any resource
locator identifying a resource on the network, such as a display
description of a voting authority having a site or node on the network. In
general, while hardware platforms, such as voter computers, terminals and
servers, are described herein, aspects of the invention are equally
applicable to nodes on the network having corresponding resource
locators to identify such nodes.
Unless the context clearly requires otherwise, throughout
the description and the claims, the words 'comprise', 'comprising', and the
like are to be construed in an inclusive sense as opposed to an exclusive
or exhaustive sense; that is to say, in the sense of "including, but not
limited to"_ Words using the singular or plural number also include the
plural or singular number, respectively. Additionally, the words
"herein", "hereuader", and words of similar import, when used in this
application, shall refer to this application as a whole and not to any
-.particu,>ar portions of this application.
The above description of illustrated embodimcnxs of the
invention is not intended to be exhaustive or to limit the invention to the
precise form disclosed. While specif c embodiments o~ and examples for,
the invention are described herein for illustrative purposes, various
equivalent modifications are possible within the scope of the invention, as
those skilled in the relevant art will recognize. The teachings of the
48
SUBSTITUTE SHEET (RULE 261
CA 02550259 2001-03-24
WU 01/7369.1 1'CTNSO1l09S50
invention provided herein can be applied to other encryption applications,
not only die eleebronic voting sysbeln described above. For example, the
protocol has applications in electronic ~ commerce where both anonymity
and auditability are requirements. Examples of this are electronic
paymcrrt schemes ("e-cash").
The various embodiments described above can be combined
to provide further embodiments. All of the above references end U.S.
pate~ats and applications are incorporated herein by reference. Aspects of
the invention can be modified, if necessary, to employ the systems,
functions and concepts of the various patents artd applications described
above to provide yet further embodiments of the invention.
These and other changes can be made to the invention in
light of the above detailed description. 1n general, in the following
claims, the terms used should not be construed to limit the invention to
the specific embodiments disclosed in the specification and the claims,
but should be construed to include all encryption systems and methods
that operate ands the claims to provide data security. Accordingly, the
invention is not limited by the disclosure, bnt instead the scope of the
invention is to be determined entirely by th~claims.
While certain aspects of the invention are presented below
is certain claim forms, the inventor contemplates the various aspects of
the invention in any number of claim forms. For example, while only one
aspect of the invention is recited as embodied in a computer-readable
medium, other aspects may likewise be esabodied in computer-readable
medium. Accordingly, the inventor reserves the right to add additional
claims after filing the application to pursue such additional claim fo~as
for other aspects of the invention.
49
SUBSTITUTE SHEET (RULE 26)
