Boneh–Franklin scheme

Groups and parameters

As the scheme bases upon pairings, all computations are performed in two groups, G 1 and G 2 :

For G 1 , let p be prime, p ≡ 2 mod 3 and consider the elliptic curve E : y 2 = x 3 + 1 over Z / p Z . Note that this curve is not singular as 4 a 3 + 27 b 2 = 27 = 3 3 only equals 0 for the case p = 3 which is excluded by the additional constraint.

Let q > 3 be a prime factor of p + 1 (which is the order of E ) and find a point P ∈ E of order q . G 1 is the set of points generated by P : { n P ∥ n ∈ { 0 , … , q − 1 } }

G 2 is the subgroup of order q of G F ( p 2 ) ∗ . We do not need to construct this group explicitly (this is done by the pairing) and thus don't have to find a generator.

Setup

The private key generator (PKG) chooses:

1. the public groups G 1 (with generator P ) and G 2 as stated above, with the size of q depending on security parameter k ,
2. the corresponding pairing e ,
3. a random private master-key K m = s ∈ Z q ∗ ,
4. a public key K p u b = s P ,
5. a public hash function H 1 : { 0 , 1 } ∗ → G 1 ∗ ,
6. a public hash function H 2 : G 2 → { 0 , 1 } n for some fixed n and
7. the message space and the cipher space M = { 0 , 1 } n , C = G 1 ∗ × { 0 , 1 } n

Extraction

To create the public key for I D ∈ { 0 , 1 } ∗ , the PKG computes

1. Q I D = H 1 ( I D ) and
2. the private key d I D = s Q I D which is given to the user.

Encryption

Given m ∈ M , the ciphertext c is obtained as follows:

1. Q I D = H 1 ( I D ) ∈ G 1 ∗ ,
2. choose random r ∈ Z q ∗ ,
3. compute g I D = e ( Q I D , K p u b ) ∈ G 2 and
4. set c = ( r P , m ⊕ H 2 ( g I D r ) ) .

Note that K p u b is the PKG's public key and thus independent of the recipient's ID.

Decryption

Given c = ( u , v ) ∈ C , the plaintext can be retrieved using the private key:

m = v ⊕ H 2 ( e ( d I D , u ) )

Correctness

The primary step in both encryption and decryption is to employ the pairing and H 2 to generate a mask (like a symmetric key) that is xor'ed with the plaintext. So in order to verify correctness of the protocol, one has to verify that an honest sender and recipient end up with the same values here.

The encrypting entity uses H 2 ( g I D r ) , while for decryption, H 2 ( e ( d I D , u ) ) is applied. Due to the properties of pairings, it follows that:

H 2 ( e ( d I D , u ) ) = H 2 ( e ( s Q I D , r P ) ) = H 2 ( e ( Q I D , P ) r s ) = H 2 ( e ( Q I D , s P ) r ) = H 2 ( e ( Q I D , K p u b ) r ) = H 2 ( g I D r )

Security

The security of the scheme depends on the hardness of the bilinear Diffie-Hellman problem (BDH) for the groups used. It has been proved that in a random-oracle model, the protocol is semantically secure under the BDH assumption.

Improvements

BasicIdent is not chosen ciphertext secure. However, there is a universal transformation method due to Fujisaki and Okamoto that allows for conversion to a scheme having this property called FullIdent.