Cryptography Reference
In-Depth Information
=−
1mod
n
and, although this value is not randomly chosen, this does not
affect the security of the scheme.
3. The reason why the ciphertext consists of the two pairs
u
c
1
)
instead of just the one that will be used for decryption is that the sender does not
know which one of the values
R
,
uR
is a quadratic residue modulo
n
. Therefore,
sufficient information to cover both possibilities must be sent, which effectively
doubles the size of the ciphertext.
4. The hash function
H
must apply identity strings to elements of
(
d
0
,
c
0
)
and
(
d
1
,
J
n
and hence
it may be constructed from a cryptographic hash function such as SHA-256 by
means of a public deterministic algorithm, so that anyone knowing the public
parameters and
id
can compute
H
R
. For example, the cryptographic hash
function can be applied to obtain a value in
(
id
)
=
Z
n
which is then incremented until
reaching the first value whose Jacobi symbol is
1.
5. The elements
t
0
,
t
1
, chosen by the encryption algorithm, are supposed to belong
to
+
Z
n
(where all computations take place) and so one might choose them in
Z
n
as
Z
n
, discarding them if this is not
the case. However, this check can be dispensed with because such an element
does not belong to
indicated and check that they indeed belong to
Z
n
only with negligible probability. In fact, if we find an
Z
n
element of
Z
n
that does not belong to
then, by computing its gcd with
n
,we
obtain the factorization of
n
.
6. As usual with public-key encryption schemes, Cocks IBE will be used mostly in
hybrid schemes to encrypt session keys, i.e., symmetric keys which, in turn, are
used to encrypt data. The scheme is efficient enough for this purpose because,
if the session key is
l
bits long, then the cost of encryption is dominated by the
computation of 2
l
Jacobi symbols—which can be efficiently computed using
Algorithm 2.7—and 2
l
divisions modulo
n
. Similarly, the cost of decryption is
dominated by the computation of
l
Jacobi symbols. As mentioned above, the
main drawback of the scheme is the space requirement which is high because it
uses, for each bit, two numbers of size close to the size of
n
.
=
≡
≡
(
)
∈
QR
n
Exercise 10.2
Suppose that
n
pq
with
p
q
3
mod 4
and let
R
Z
n
be a quadratic residue modulo
n
. Prove that a square root of
R
in
is given by
R
n
−
(
p
+
q
)
+
5
r
=
mod
n
.
8
Exercise 10.3
Explain the reasons why if, in the encryption and decryption algo-
rithms of Definition 10.6 one encodes the bit
m
as
b
=
m
(i.e.,
b
∈{
0
,
1
}
, instead of
b
∈{−
1
,
1
}
), then one obtains a scheme which is completely insecure.
Let us say a few words about the security of the Cocks IBE scheme. It is clear
that the scheme can be broken if the modulus
n
is factored and so, for its practical
implementation the size of the modulus should be similar to the sizes we have dis-
cussed for RSA moduli. It can be shown that Cocks IBE is IND-ID-CPA secure
4
in
4
The definition of IND-ID-CPA is obtained from the definition of IND-ID-CCA above by dropping
the decryption queries.
