Finding an efficient and secure identity based protocol has been an open problem for a long time. At CRYPTO 2001, D. Boneh and M. Franklin [Lect. Notes Comput. Sci. 2139, 213–229 (2001; Zbl 1002.94023)] proposed a scheme based on bilinear maps. As a realization they proposed to use supersingular elliptic curves and the Weil respectively Tate pairing over such curves defined over a finite field.
In the present paper the authors give the full proofs and further improvements and applications. These two papers have led to many further inventions in the area of cryptography. Important concepts are the computational bilinear Diffie-Hellman (CBDH) problem, namely the problem of computing \(\hat{e}(P,P)^{abc}\) given \(P, aP, bP, cP\), where \(\hat{e}\) is a known bilinear map, and the decisional bilinear Diffie-Hellman (DBDH) problem, which is to decide whether for \(P, aP, bP, cP\) and \(h\in \langle\hat{e}(P,P)\rangle\) one has \(\hat{e}(P,P)^{abc}=h\). The ID-based protocol requires a trusted authority (TA) to generate the private keys of the users; accordingly it can decrypt any message sent via the system. The system can easily be applied for key-escrow.
The protocol works as follows: the TA chooses two cyclic groups \(G_1=\langle P \rangle, G_2\) of equal order in which one can efficiently compute, the discrete logarithm problem is hard, and there is an efficient pairing \(\hat{e}:G_1\times G_1\to G_2\). He publishes the descriptions together with \(P\) and \(Q=sP\) for a secretly chosen integer \(s\), which is the master key. Additionally a hash function \(H:\{0,1\}^*\to G_1\) from arbitrary bit strings to the first group is needed. If someone wants to send a message \(m\) to a user \(U\) with identity \(ID\) he computes \(H(ID)\in G_1\), picks a random \(r\), and sends \(R=rP\) and \(c=m\oplus \hat{e}(Q,H(ID))^r\) to user \(U\), where \(\oplus\) is some function which is easy to invert by \(\ominus\). To decrypt, \(U\) receives \(sH(ID)\) from the TA from which he can compute \(c\ominus \hat{e}(R,sH(ID))=c\ominus \hat{e}(rP,sH(ID))=c\ominus \hat{e}(Q,H(ID))^r=m\).
The paper gives a careful study of the security, proving the basic scheme to be semantically secure. Then the authors convert the scheme to a chosen ciphertext secure one. They also deal with implementation issues and propose concrete parameters.