Cryptography Reference
In-Depth Information
used to encrypt the vote by choosing a random
b
j
∈
Z
and computing
c
j
=(
α
b
j
,α
v
j
k
b
j
), posting it to the bulletin board. We assume that
each voter has signed
c
j
and correctlyperformed a proof of knowledge
(see Section 5.3 on page 202) to verifythat the protocol has been validly
followed. Failure to meet anyof these criteria means that the vote is
discarded as invalid.
/q
Z
2.
Tallying the Votes
: Since all the
c
j
are posted on the bulletin board, then
anyone can compute the following:
α
v
j
k
b
j
α
j
=1
b
j
(mod
p
)
.
u
j
=1
b
j
u
j
=1
v
j
u
u
u
≡
α
b
j
,
≡
(
V
1
,V
2
)
,α
k
j
=1
j
=1
Each authority
A
j
posts
α
a
j
b
j
to the bulletin board. Once
t
honest au-
thorities, say
A
1
,A
2
,...,A
t
for simplicity, have posted their data to the
bulletin board, then anyone can use their data to compute the following:
t
j
=1
a
j
K
j
1
j
=1
j
=1
a
u
u
b
j
b
j
V
1
≡
g
≡
V
≡
α
≡
k
(mod
p
)
,
where
K
j
=
1
−
j
≤
≤
t
=
j
(see page 213).
Thus,
u
j
=1
v
j
V
2
g
−
1
α
D
(mod
p
)
,
≡
≡
α
j
=1
v
j
is the difference between the number of yes and no votes.
Hence, we see above that (
V
1
,V
2
) is actuallythe cryptogram enciphering
α
D
and we used the homomorphic propertyto get it. Now the tallyis
accomplished bycomputing
α
D
α
−
u
+
i
(mod
p
) for
i
=0
,
1
,
2
,
3
...
, until
we have that
α
D
α
−
u
+
i
u
where
D
=
≡
1(mod
p
). Then that value of
u
−
i
is
D
, the
tally.
Analysis
: Privacyis provided bythe in-built ElGamal cipher, which rests
upon the intractabilityof the DLP (see pages 186 and 187). Given a coalition of
no fewer than
t
w
honest authorities, anyone can verify the tally, a property
called
universal verifiability
, something currently
not
available to voters. Also,
the message sent byeach voter is simple and concise, so the time complexityof
the scheme can be shown to be exceptionallylow. Our version of the original
scheme is necessarilya simplified one for pedagogical reasons.
There is a mechanism for eliminating the role of Trent. To do so, Trent's ac-
tions need to be performed bythe authorities. Since this is a minor modification,
we will not discuss the details.
≤
Search WWH ::
Custom Search