Identity-Based Cryptography - Security for Wireless Sensor Networks Using Identity-Based Cryptography - page 71

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 .