Cryptography Reference
In-Depth Information
to a single bit is essentially a pair of elements of
Z
n
, where
n
is an RSA modulus.
Thus the expansion factor is about 2 log
2
n
and hence, if we want to encrypt, say, a
256-bit symmetric key using a 2048-bit RSA modulus, we will need 2
2048
bits or, equivalently, 1 mebibit (the 'binary version' of 1 megabit). There is another
IBE scheme, due to Boneh, Gentry and Hamburg [36] that is also based on quadratic
residuosity and achieves a ciphertext size of
l
·
256
·
log
2
n
for an
l
-bit message. The
trade-off, however, is a substantial increase of encryption time so that, for now,
pairing-based IBE schemes—which will be presented later on—are preferred.
+
Definition 10.6
Cocks IBE scheme
.
Like every IBE scheme, the Cocks scheme uses a set of public system parameters
that specify the message space, the ciphertext space and the identities space. We will
not make them explicit but these parameters may be used by any of the algorithms
belonging to the scheme, as may some other public system parameters that will be
specified below. The Cocks scheme is the IBE scheme (
Setup, Der, Enc, Dec
), where
the algorithms are defined as follows:
•
Setup
: On input 1
k
, the PKG runs the modulus generation algorithm to obtain
(
n
,
p
,
q
)
, where
n
=
pq
and
p
,
q
are primes such that len
(
p
)
=
len
(
q
)
=
k
.The
master key is then the pair
(
n
,(
p
,
q
))
, where
n
is the master public key and
(
p
,
q
)
n
is chosen
3
and published
as a system parameter. The remaining public system parameter is a hash function
H
mapping user identities to
the master private key. Moreover, a random
u
←
QN
J
n
.
•
Der
: On input the master private key
(
p
,
q
)
and an identity string
id
, the PKG
proceeds as follows. First, it computes
R
:=
H
(
id
)
∈
J
n
.If
R
∈
QR
n
, then it
R
1
/
2
mod
n
(i.e.
r
is a square root of the quadratic residue
R
in
Z
n
),
sets
r
:=
1
/
2
mod
n
. The output is
r
, the private key of the user
otherwise it sets
r
:=
(
uR
)
with identity
id
.
•
Enc
: On input the master public key
n
, an identity
id
and a one-bit message
m
m
. Choose two random elements
∈{
0
,
1
}
, compute
R
:=
H
(
id
)
and
b
:=
(
−
1
)
t
i
← Z
n
with
i
∈{
0
,
1
}
and compute:
t
i
n
t
i
u
i
R
t
−
1
i
d
i
:=
(
+
)
mod
n
,
and
c
i
:=
b
·
.
((
d
0
,
c
0
), (
d
1
,
c
1
))
Output the ciphertext
.
•
Dec
: On input the public parameters, the user private key
r
, the identity
id
, and the
ciphertext
such that
r
2
u
i
R
((
d
0
,
c
0
), (
d
1
,
c
1
))
,set
i
∈{
0
,
1
}
≡
(
mod
n
)
, where
c
i
·
n
.If
b
R
:=
H
(
id
)
. Then set
g
:=
(
d
i
+
2
r
)
mod
n
and compute
b
:=
=
1
then output 0 and if
b
=−
1, then output 1.
Let us now prove the correctness of the scheme:
3
Recall here that
J
n
denotes the subset of the elements of
Z
n
with Jacobi symbol modulo
n
equal
to
n
is the intersection of
J
n
with the set of quadratic non-residues modulo
n
.
+
1and
QN
