Cryptography Reference
In-Depth Information
∈ Z
n
2
|
Z
n
2
{
+
∈ Z
n
}
Exercise 8.43
Show that the set
1
xn
x
is a cyclic subgroup of
∈ Z
n
2
|
∈ Z
n
}
{
+
whose generators are the elements in the set
1
xn
x
.
We next describe the Paillier scheme.
Definition 8.21
The Paillier public-key encryption scheme
(
Gen
,
Enc
,
Dec
)
is
defined as follows:
Gen
: On input 1
k
, generate an RSA modulus
n
•
pq
, where
p
and
q
are
k
-
bit primes. The public key is
n
and the private key is the pair
=
(
n
,φ(
n
))
, where
φ(
n
)
=
(
p
−
1
)(
q
−
1
)
.
← Z
n
at random
•
Enc
: Given the message
m
∈ Z
n
and the public key
n
, choose
r
and output the ciphertext:
m
r
n
mod
n
2
∈ Z
n
2
c
:=
((
1
+
n
)
·
)
∈ Z
n
2
and the private key
•
Dec
: Given the ciphertext
c
(
n
,φ(
n
))
, output:
c
φ(
n
)
mod
n
2
:=
(
)
−
1
)
−
1
mod
n
m
·
φ(
n
,
n
c
φ(
n
)
mod
n
2
where the quotient
((
)
−
1
)/
n
is computed in
Z
.
c
φ(
n
)
, where
=
+
=
To prove the correctness of the scheme, set
g
1
n
and let
d
g
m
r
n
mod
n
2
c
φ(
n
)
))
φ(
n
)
c
=
(
·
)
=
ε
g
(
m
,
r
)
.Wehavethat
d
=
=
(ε
g
(
m
,
r
=
)
φ(
n
)
)
=
ε
g
(
r
φ(
n
)
mod
n
ε
g
((
m
,
r
m
φ(
n
)
mod
n
,
)
=
ε
g
(
m
φ(
n
)
mod
n
,
1
)
=
m
φ(
n
)
mod
n
mod
n
2
(
1
+
n
)
=
1
+
(
m
φ(
n
)
mod
n
)
·
n
(where we used the binomial
expansion as before to obtain the last term). Thus
(
d
−
1
)/
n
=
m
φ(
n
)
mod
n
and,
finally, the output of multiplying this integer by the inverse of
φ(
n
)
modulo
n
is
precisely the plaintext
m
.
Now, it is clear that the Paillier encryption scheme is OW-CPA secure if and only
if the CCRA holds but, as on other occasions, we are interested in obtaining a scheme
that is, at least, CPA secure. We can show that the Paillier scheme enjoys this prop-
erty under a suitable hardness assumption. This assumption refers to the
decisional
composite residuosity problem
, which is the problem of distinguishing a random
element of
Z
n
2
. The hypothesis that this problem is
hard, i.e., that no probabilistic polynomial-time distinguisher can distinguish these
elements with non-negligible probability is called the
decisional composite resid-
uosity assumption
(DCRA) in [152] and we are going to show that it provides the
required CPA security.
n
R
n
2
from a random element of
Exercise 8.44
Give a formal definition of the DCRA by considering an experiment
similar to the
QR experiment
inDefinition 8.18, whichwas used to define the hardness
of the quadratic residuosity problem.
Theorem 8.6
The Paillier encryption scheme is CPA secure if and only if the DCRA
holds.
