Boneh–Franklin scheme explained

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

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

style G _{1} and style G _{2} :

For

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

Let

style q > 3 be a prime factor of style p + 1 (which is the order of style E ) and find a point style P \in E of order style q . style G _{1} is the set of points generated by style P : style \left\{nP \| n \in \left\{ 0 ,\ldots,q -1 \right\} \right\} style G _{2} is the subgroup of order style q of style GF\left(p ^{2\right)} ^{*} . We do not need to construct this group explicitly (this is done by the pairing) and thus don't have to find a generator.style G _{1} is considered an additive group, being a subgroup of the additive group of points of style E , while style G _{2} is considered a multiplicative group, being a subgroup of the multiplicative group of the finite field style GF(p ^{2)} ^{*} .

Protocol description

Setup

The public key generator (PKG) chooses:

1. the public groups

style G _{1} (with generator style P ) and style G _{2} as stated above, with the size of style q depending on security parameter style k ,

1. the corresponding pairing

style e ,

1. a random private master-key

style K _{m} = s \in Z ^{*} _{q} ,

1. a public key

style K _{pub} = sP ,

1. a public hash function

style H _{1:} \left\{ 0 , 1 \right\} ^{*} → G ^{*} _{1} ,

1. a public hash function

style H _{2:} G _{2} → \left\{ 0 , 1 \right\} ^{n} for some fixed style n andstyle l{M} = \left\{ 0 , 1 \right\} ^{n,} l{C} = G ^{*} _{1} x \left\{ 0 , 1 \right\} ^{n}

Extraction

To create the public key for

style ID \in \left\{ 0 , 1 \right\} ^{*} , the PKG computes style Q _{ID} = H _{1\left(ID\right)} and

1. the private key

style d _{ID} = sQ _{ID} which is given to the user.

Encryption

Given

style m \in l{M} , the ciphertext style c is obtained as follows: style Q _{ID} = H _{1\left(ID\right)} \in G ^{*} _{1} ,

1. choose random

style r \in Z ^{*} _{q} ,

1. compute

style g _{ID} = e\left(Q _{ID} , K _{pub} \right) \in G _{2} and

1. set

style c = \left(rP, m ⊕ H _{2\left(g} ^{r\right)\right)} ^{ID} .

Note that

style K _{pub} is the PKG's public key and thus independent of the recipient's ID.

Decryption

Given

style c = \left(u, v\right) \in l{C} , the plaintext can be retrieved using the private key:style m = v ⊕ H _{2\left(e\left(d} _{ID} , u\right)\right)

Correctness

The primary step in both encryption and decryption is to employ the pairing and

style 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

style H _{2\left(g} ^{r\right)} ^{ID} , while for decryption, style H _{2\left(} e\left(d _{ID} , u\right) \right) is applied. Due to the properties of pairings, it follows that:\begin{align} H _{2\left(} e\left(d _{ID} , u\right) \right) & = H _{2\left(} e\left(sQ _{ID} , rP\right) \right) \\ & = H _{2\left(} e\left(Q _{ID} , P\right) ^{rs} \right) \\ & = H _{2\left(} e\left(Q _{ID} , sP\right) ^{r} \right) \\ & = H _{2\left(} e\left(Q _{ID} , K _{pub} \right) ^{r} \right) \\ & = H _{2\left(} g ^{r} _{ID} \right) \\ \end{align}

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^[2] that allows for conversion to a scheme having this property called FullIdent.

References

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

External links

• Seminar 'Cryptography and Security in Banking'/'Alternative Cryptology', Ruhr University Bochum
• P(airing) B(ased) C(ryptography) library, designed by Ben Lynn et al.