Boneh–Franklin scheme

The Boneh–Franklin scheme is an identity-based encryption system proposed by Dan Boneh and Matthew K. Franklin in 2001.[1] This article refers to the protocol version called BasicIdent. It is an application of pairings (Weil pairing) over elliptic curves and finite fields.

Groups and parameters

edit

As the scheme is based upon pairings, all computations are performed in two groups,   and  :

For  , let   be prime,   and consider the elliptic curve   over  . Note that this curve is not singular as   only equals   for the case   which is excluded by the additional constraint.

Let   be a prime factor of   (which is the order of  ) and find a point   of order  .   is the set of points generated by  :  

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

  is considered an additive group, being a subgroup of the additive group of points of  , while   is considered a multiplicative group, being a subgroup of the multiplicative group of the finite field  .

Protocol description

edit

Setup

edit

The public key generator (PKG) chooses:

  1. the public groups   (with generator  ) and   as stated above, with the size of   depending on security parameter  ,
  2. the corresponding pairing  ,
  3. a random private master-key  ,
  4. a public key  ,
  5. a public hash function  ,
  6. a public hash function   for some fixed   and
  7. the message space and the cipher space  

Extraction

edit

To create the public key for  , the PKG computes

  1.   and
  2. the private key   which is given to the user.

Encryption

edit

Given  , the ciphertext   is obtained as follows:

  1.  ,
  2. choose random  ,
  3. compute   and
  4. set  .

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

Decryption

edit

Given  , the plaintext can be retrieved using the private key:

 

Correctness

edit

The primary step in both encryption and decryption is to employ the pairing and   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  , while for decryption,   is applied. Due to the properties of pairings, it follows that:

 

Security

edit

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

edit

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

References

edit
  1. ^ Dan Boneh, Matthew K. Franklin, "Identity-Based Encryption from the Weil Pairing", Advances in Cryptology – Proceedings of CRYPTO 2001 (2001)
  2. ^ Eiichiro Fujisaki, Tatsuaki Okamoto, "Secure Integration of Asymmetric and Symmetric Encryption Schemes", Advances in Cryptology – Proceedings of CRYPTO 99 (1999). Full version appeared in J. Cryptol. (2013) 26: 80–101
edit