Certificateless cryptography with KGC trust level 3

A normal certificateless cryptosystem can only achieve KGC trust level 2 according to the trust hierarchy defined by Girault. Although in the seminal paper introducing certificateless cryptography, Al-Riyami and Paterson introduced a binding technique to lift the KGC trust level of their certificateless schemes to level 3, many subsequent work on certificateless cryptography just focused on the constructions of normal certificateless schemes, and a formal study on the general applicability of the binding technique to these existing schemes is still missing. In this paper, to address the KGC trust level issue, we introduce the notion of Key Dependent Certificateless Cryptography (KD-CLC). Compared with conventional certificateless cryptography, KD-CLC can achieve stronger security, and more importantly, KGC trust level 3. We then study generic techniques for transforming conventional CLC to KD-CLC. We start with the binding technique by Al-Riyami and Paterson, and show that there are some technical difficulties in proving that the binding technique is generally applicable. However, we show that a slightly modified version of the binding technique indeed can be proved to work under the random oracle assumption. Finally, we show how to perform the transformation using a standard cryptographic primitive instead of a random oracle.