Cryptography Reference
In-Depth Information
so that no one learns anyone else's vote. Suppose also that each voter casts one
vote (for a given candidate), which can be either neutral or favorable. An obvious
possibility is to make each voter cast her vote by encrypting it with a public-key
encryption scheme using the public key of a trusted authority which will be given the
encrypted votes and will obtain the vote total after decrypting them with the private
key. However, our initial goal is not attained this way since the authority learns the
individual votes. Keeping the basic idea of using a public-key encryption scheme
to encrypt the votes, the goal would then be to devise a protocol that allows the
authority to count the total vote without having access to the individual encrypted
votes, so that the votes can be counted without having to decrypt them. This is just a
particular case of what a homomorphic encryption scheme can do: if the authority is
given the product of all encrypted votes corresponding to a candidate, it can decrypt
it to obtain the product of the corresponding (unencrypted) votes, which allows the
number of favorable votes obtained to be counted. This can be achieved with plain
RSA as the following exercise shows:
Exercise 8.41
Show that plain RSA can be used to efficiently obtain the vote total
from the product of all encrypted votes, assuming knowledge of the private key
(Hint: use two small primes to represent the neutral vote and the favorable vote,
respectively.)
It might seem at first sight that plain RSA is adequate for our purpose of guaran-
teeing vote confidentiality but the sketched protocol fails because, as we have seen,
plain RSA is completely insecure and an adversary that observes an encrypted vote
c
can learn the vote by just encrypting the neutral vote and the favorable vote and
comparing the result with
c
. This total failure is due to plain RSA having a deter-
ministic encryption algorithm and it is clear that, for the protocol to be of any use,
the underlying homomorphic encryption scheme should also be CPA secure (under
some reasonable hardness assumption, as usual). The variants of RSA which are
CPA secure, such as RSA-OAEP, are not homomorphic because the random padding
destroys the multiplicative property. We have seen, however, that there are public-key
encryption schemes, such as Elgamal and Goldwasser-Micali, that are both homo-
morphic and CPA secure. The latter scheme is not suitable for our purpose because
the plaintext space, namely
Z
2
, is too small and the former could be used but we are
going to discuss another scheme which also satisfies the required properties and is
specially suited for counting votes because the plaintext space is
Z
n
for a large value
of
n
:the
Paillier encryption scheme
.
Let
n
pq
be the product of two distinct primes of the same length. We may
describe the group
=
Z
n
2
in terms of the groups
Z
n
and, for this purpose, we
Z
n
and
Z
n
× Z
n
, whose operation will be generically denoted by
multiplication (notice that the first components of the elements of the product are
added and the second components multiplied, in both cases modulo
n
). We have:
will consider the group
Proposition 8.9
Let n
=
pq, where p, q are distinct odd primes of the same length
∈ Z
n
2
be an element of order n. Then the map
and let g
