Cryptography Reference
In-Depth Information
Proposition 10.1
In the Cocks IBE scheme we have that, using the preceding nota-
tion, for any id such that r is the private key corresponding to this identity and any
m
∈{
0
,
1
}
,
Dec
(
n
,
r
,
id
,
Enc
(
n
,
id
,
m
))
=
m.
·
t
n
,
m
,
c
i
Proof
Keeping the notations above we have to show that, if
b
=
(
−
1
)
=
b
t
−
1
i
t
i
u
i
R
d
i
=
(
+
)
mod
n
and
g
=
(
d
i
+
2
r
)
mod
n
,for
i
∈{
0
,
1
}
such that
c
i
·
n
.Wehave:
r
2
u
i
R
≡
(
mod
n
)
, then
b
=
t
i
u
i
R
t
−
1
i
2
t
−
1
i
g
=
(
d
i
+
2
r
)
mod
n
=
((
+
)
+
2
r
)
mod
n
=
(
t
i
+
r
)
mod
n
.
(10.1)
x
−
1
mod
n
n
for every
x
⊂
J
n
and
n
=
∈ Z
n
(because of the mul-
tiplicative property of the Jacobi symbol and the fact that
n
Since
QR
n
=
1), we see from
Eq.
10.1
that
t
−
1
i
t
i
n
g
n
mod
n
n
=
=
and hence
t
i
n
g
n
g
n
b
g
n
2
c
i
·
=
b
·
=
=
b
,
so that the correct plaintext is recovered.
Remarks 10.1
n
is to make either
R
or
uR
a quadratic residue modulo
n
and hence to make it possible to extract
its square root in
1. The purpose of the randomly chosen element
u
←
QN
Z
n
, which is easy if one knows the factorization of
n
(i.e.,
the master private key of the scheme, which is a possession of the PKG) but is
presumed to be difficult without knowing this factorization; this is precisely the
quadratic residuosity assumption, see Definition 8.18. Since
R
=
H
(
id
)
∈
J
n
,
∈
QR
n
then we have that
p
q
if
R
=
=−
1 and, on the other hand,
n
also implies that
p
q
∈
QN
=
=−
u
1. Thus in this case we have, by
the multiplicative property of the Jacobi symbol, that
u
p
u
q
=
=
1 and
1
so
uR
n
is easy
to choose if the factorization of
n
is known because, as discussed in relation
with the Goldwasser-Micali encryption scheme, it suffices to choose an element
whose Legendre symbols with respect to both
p
and
q
are equal to
∈
QR
n
by Proposition 2.14. Note also that a random
u
←
QN
1.
2. In the original version of the scheme in [51], the prime factors
p
,
q
of the
modulus
n
are taken to be Blum primes, i.e., such that
p
−
≡
q
≡
3
(
mod 4
)
.In
this case, both
(
p
−
1
)/
2 and
(
q
−
1
)/
2 are odd and hence, as a consequence
of Euler's criterion (Proposition 2.12) we have that
−
p
−
q
=
=−
1.
−
p
−
q
Then
−
n
1
=
=
1 and hence
−
1
∈
QN
n
. Thus we can choose
