Cryptography Reference
In-Depth Information
4.3.1.3 Gap Diffi e-Hellman Group
If
G
is a cyclic group whose order is prime, it is said to be a
gap Diffie Hellman group
(GDHG) if the DDHP can be solved in polynomial time but no probabilistic algo-
rithm can solve the CDHP with non-negligible advantage within the polynomial time
(Okamoto and Pointcheval 2001).
4.3.1.4 Bilinear Diffi e-Hellman Group
The
bilinear Diffie-Hellman group
(BDHG) generalizes the CDHP to groups with a
pairing. This problem states that given
P
,
aP
,
bP
,
cP
, calculate
e
(
P
,
P
)
abc
, where
a
,
b
,
c
Z
q
. Note that an additive notation is used instead of a multiplicative notation, because
the setting of the BDHP is typically an elliptic curve group. In the case of pairing, let
us assume
´
1
eG G G
. Solving the problem of bilinear Diffie-Hellman is no
more difficult than calculating discrete logarithms in either
G
1
or
G
T
. Hence, if we
can find the value of
c
by calculating the discrete logarithm of
cP
in
G
1
, then we can
calculate
e
(
aP
,
bP
)
c
= (
e
(
P
,
P
)
ab
)
c
=
e
(
P
,
P
)
abc
, or we can find the value of
c
by calculating
the discrete logarithm of
e
(
P
,
cP
) =
e
(
P
,
P
)
c
in
G
2
. Then we can also calculate
e
(
P
,
P
)
abc
in a similar way.
:
2
T
4.3.2 Identity-Based Encryption Schemes
Four probabilistic polynomial time algorithms, Set-up, Key-Gen, Encrypt, and
Decrypt, define identity-based encryption schemes.
Set-up
: This algorithm takes the security parameter
k
and returns the master key
M
s
and system parameters
PP
.
PP
includes a brief description of a finite message
space
M
and cipher text
C
. Intuitively, the master secret key
M
s
is generated by
PKG while the
PP
is publicly known to end users. Let
id
I
(a set of identities).
Key-Gen
: This algorithm takes the user's identity id
I
along with PP and the
master secret
M
s
, and returns the corresponding user's private key did.
Encrypt
: This takes the identity
id
I
,
m
M
, and public parameters
PP
and
generates the cipher text
c
C
.
Decrypt
: This algorithm takes the identity
id
I
, cipher text
c
C
, and a private
key
d
id
corresponding
id
I
and returns the message
m
M
or an error message.
Since the PKG generates the private keys corresponding to public keys, it can decrypt
any message encrypted using the identity
id
I
. This inherent property in identity-
based cryptography is referred to as the
key escrow property
.
Search WWH ::
Custom Search