Boneh/Franklin scheme

From Wikipedia, the free encyclopedia

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.

1 Groups and parameters
2 Protocol description
3 Security
4 Improvements
5 External Links
6 References

[edit] Groups and parameters

As the scheme bases upon pairings, all computations are performed in two groups $\textstyle G_1$ and $\textstyle G_2$ :

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

Let $\textstyle q > 3$ be a prime factor of $\textstyle p + 1$ (which is the order of $\textstyle E$ ) and find a point $\textstyle P \in E$ of order $\textstyle q$ . $\textstyle G_1$ is the set of points generated by $\textstyle P$ : $\textstyle \left\{nP \| n \in \left\{0,\ldots,q-1\right\} \right\}$

$\textstyle G_2$ is the subgroup of order $\textstyle q$ of $\textstyle 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.

[edit] Protocol description

[edit] Setup

The PKG chooses

the public groups $\textstyle G_1$ (with generator $\textstyle P$ ) and $\textstyle G_2$ as stated above, with the size of $\textstyle q$ depending on security parameter $\textstyle k$ ,
the corresponding pairing $\textstyle e$ ,
a random private master-key $\textstyle K_m = s \in \mathbb{Z}_q^*$ ,
a public key $\textstyle K_{pub} = sP$ ,
a public hash function $\textstyle H_1: \left\{0,1\right\}^* \rightarrow G_1^*$ ,
a public hash function $\textstyle H_2: G_2 \rightarrow \left\{0,1\right\}^n$ for some fixed $\textstyle n$ and
the message space and the cipher space $\textstyle \mathcal{M} = \left\{0,1\right\}^n, \mathcal{C} = G_1^* \times \left\{0,1\right\}^n$

[edit] Extract

To create the public key for $\textstyle ID \in \left\{0,1\right\}^*$ , the PKG computes

$\textstyle Q_{ID} = H_1\left(ID\right)$ and
the private key $\textstyle d_{ID} = sQ_{ID}$ which is given to the user.

[edit] Encrypt

Given $\textstyle m \in \mathcal{M}$ , the ciphertext $\textstyle c$ is obtained as follows:

$\textstyle Q_{ID} = H_1\left(ID\right) \in G_1^*$ ,
choose random $\textstyle r \in \mathbb{Z}_q^*$ ,
compute $\textstyle g_{ID} = e\left(Q_{ID}, K_{pub}\right) \in G_2$ and
set $\textstyle c = \left(rP, m \oplus H_2\left(g_{ID}^r\right)\right)$ .

Note that $\textstyle K_{pub}$ is the PKG's public key and thus independent of the recipient's ID.

[edit] Decrypt

Given $\textstyle c = \left(u, v\right) \in \mathcal{C}$ , the plaintext can be retrieved using the private key:

$\textstyle m = v \oplus H_2\left(e\left(d_{ID}, u\right)\right)$

[edit] Correctness

The primary step in both en- and decryption is to employ the pairing and $\textstyle 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 a honest sender and recipient end up with the same values here.

The encrypting entity uses $\textstyle H_2\left(g_{ID}^r\right)$ , while for decryption, $\textstyle 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_{ID}^r \right) \\ \end{align}$

[edit] 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.

[edit] Improvements

BasicIdent is 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.

[edit] External Links

[edit] References

^ Dan Boneh, Matthew K. Franklin, Identity-Based Encryption from the Weil Pairing Advances in Cryptology - Proceedings of CRYPTO 2001 (2001)

Categories: Cryptography