Cryptography Reference
In-Depth Information
Proof
Let
m
0
,
m
1
be the two plaintexts output by the adversary in the IND-CPA
experiment and let
c
g
m
b
r
n
mod
n
2
be the ciphertext corresponding to a randomly
=
cg
−
m
0
mod
n
2
∈ Z
n
2
and we claim that
b
chosen bit
b
.Weset
w
=
=
0 if and only
r
n
mod
n
2
is indeed an
n
th residue. For
=
=
if
w
is an
n
th residue. If
b
0 then
w
g
(
m
1
−
m
0
)
mod
n
r
n
mod
n
2
, where we
may assume that
m
0
and
m
1
are distinct. Therefore,
the converse, assume that
b
=
1. Then
w
=
0
and hence
w
is not an
n
th residue by Proposition 8.10. As a consequence of the
just-proved claim, the CPA attack is successful if and only if composite residuosity
can be successfully decided.
δ
g
(
w
)
=
(
m
1
−
m
0
)
mod
n
=
Remarks 8.15
1. Observe that the DCRA implies the CCRA and that the latter condition, in turn,
implies that factoring the modulus is hard. It is not known, however, whether
any of these implications are in fact equivalences (and it seems likely that the
factoring assumption is weaker than the other two assumptions, see [152] for
details).
2. Corollary 8.1 says precisely that Paillier decryption (which is given by the func-
tion
δ
g
) is a group homomorphism and hence we see that the Paillier encryption
scheme is homomorphic. This property is especiallywell suited for the electronic
voting problemmentioned above because the plaintext space is the additive group
Z
n
. Thus it suffices to encode the neutral vote as 0
∈ Z
n
and the favorable vote
as 1
∈ Z
n
and then, if the votes cast by
t
voters are
m
1
,
m
2
,...
m
t
∈ Z
n
c
t
∈ Z
n
2
, the favor-
able votes can be counted without having to decrypt them by just giving
c
and the corresponding encrypted votes are
c
1
,
c
2
, ...,
i
=
1
c
i
mod
n
2
∈ Z
n
2
to the authority which, after decrypting
c
with
its private key will obtain
:=
t
m
i
mod
n
i
=
1
which, assuming that the number
t
of voters is less than
n
, is precisely the
number of favorable votes.
9
For this, the authority need not know the individual
ciphertexts
c
i
and hence it need not know the individual votes
m
i
. Observe,
however, that we have only described the basic ideas about the voting system
on the assumption that all parties act honestly but we have not given a complete
voting protocol which would require other ingredients such as an efficient proof
of validity of the vote and a threshold scheme
10
to allowan authority consisting of
a set of parties that share the private key to obtain the vote total as indicated above
without allowing a single party to decrypt individual votes (see, for example,
[63] for a generalization of Paillier's scheme that meets these requirements).
9
This will certainly be the case in any practical situation since, for the scheme to be secure,
n
should be hard to factor and hence
t
will be much smaller than
n
.
10
A scheme for distributing a secret among several parties, each of whom is allocated a share of the
secret, which can be reconstructed only when a sufficient number of shares are combined together.
