Cryptography Reference
In-Depth Information
∈ Z
n
2
is called an
n
th residue modulo
n
2
if it is an
Definition 8.20
An element
w
Z
n
2
, i.e., if there exists
u
∈ Z
n
2
such that
w
u
n
mod
n
2
.
n
th power in
=
The
n
th residues modulo
n
2
may then be characterized as follows:
∈ Z
n
2
is an nth residue if and only if w
Proposition 8.10
An element w
∈
Ker
δ
g
.
u
n
mod
n
2
is an
n
th residue. Then there exists
Proof
Suppose first that
w
=
(
a
,
b
)
∈
Z
n
× Z
n
n
such that
u
=
ε
g
(
a
,
b
)
and hence we have
δ
g
(
w
)
=
δ
g
((ε
g
(
a
,
b
))
)
=
n
b
n
mod
n
δ
g
(ε
g
((
a
,
b
)
))
=
π(
0
,
)
=
0. The converse is also clear because if
∈ Z
n
and hence
w
b
n
mod
n
2
.
δ
g
(
w
)
=
0 then
w
=
ε
g
(
0
,
b
)
for some
b
=
Remark 8.10
From the preceding proposition we see that the
n
th residues modulo
n
2
form a subgroup of
Z
n
2
. If we denote this subgroup by
n
R
n
2
, then we have as a
consequence of Propositions 2.7 and 8.10 that
δ
g
induces an isomorphism between
Z
n
2
/R
n
Z
n
. The elements of the former group are also called
n
th residuosity
classes and, for
w
n
2
and
∈ Z
n
2
, the element
)
∈ Z
n
determines uniquely the
n
th
residuosity class to which
w
belongs and hence one also says, as in [152], that
δ
g
(
w
)
is the
n
th residuosity class of
w
. Note that there are exactly
n
residuosity classes
and that each of them contains
δ
g
(
w
n
n
2
.
From this it also follows that the number of
n
th roots of each
n
th residue
w
is exactly
n
. Indeed, from Proposition 8.10 it follows that if
w
φ(
n
)
elements so that, in particular,
|
R
|=
φ(
n
)
∈ Z
n
is an
n
th residue, then
∈ Z
n
w
=
ε
g
(
0
,
u
)
for a unique
u
(observe also that
ε
g
induces an isomorphism
Z
n
and
n
Z
n
2
is isomorphic to the direct product
n
between
n
2
).
Thus
u
is the unique
n
th root of
w
which is less than
n
and the
n
elements of the set
{
R
n
2
and that
g
×
R
g
x
u
|
x
∈ Z
n
}
are
n
th roots of
w
and hence they are clearly all the
n
th roots.
The basic idea underlying the Paillier encryption scheme is to use
ε
g
for encryption
and
δ
g
for decryption based on the hypothesis that
ε
g
is a one-way trapdoor permu-
∈ Z
n
tation. The idea is then to encrypt a message
m
∈ Z
n
by picking a random
r
g
m
r
n
mod
n
2
∈ Z
n
2
. Decryption
and computing the ciphertext
c
:=
ε
g
(
m
,
r
)
=
∈ Z
n
2
is conjectured to be hard and this conjecture is named the
computational composite
residuosity assumption
(CCRA) in [152]. However, this computation becomes easy
if the prime factorization of
n
is known (or, equivalently, if
consists of computing
m
=
δ
g
(
c
)
. Computing
δ(
w
)
for a randomly chosen
w
is known), which
is the trapdoor information that is included in the private key and allows decryption.
We are going to describe the Paillier scheme taking, for simplicity,
g
φ(
n
)
=
+
n
, which
is the most common choice. This value of
g
satisfies our requirements, for we have:
1
∈ Z
n
2
is an element of order n.
Proof
Using the binomial expansion of
Proposition 8.11
1
+
n
m
,for1
(
1
+
n
)
≤
m
≤
n
, we see that all
summands except the first two are multiples of
n
2
and hence
m
mod
n
2
(
1
+
n
)
=
1
mn
, so that the smallest positive integer
m
which makes this power equal to 1 in
Z
n
2
is
m
+
=
n
.
