Certificateless cryptography is a variant of ID-based cryptography intended to prevent the key escrow problem. Ordinarily, keys are generated by a certificate authority or a key generation center (KGC) who is given complete power and is implicitly trusted. To prevent a complete breakdown of the system in the case of a compromised KGC, the key generation process is split between the KGC and the user. The KGC first generates a key pair, where the private key is now the partial private key of the system. The remainder of the key is a random value generated by the user, and is never revealed to anyone, not even the KGC. All cryptographic operations by the user are performed by using a complete private key which involves both the KGC's partial key, and the user's random secret value.
One disadvantage of this is that the identity information no longer forms the entire public key. Meaning, the user's public key is not discoverable from only the user's identity string and the KGC's public key. Thus, the user's public key must be published or otherwise obtained by other users. One advantage of the system, is that it is possible to verify that any such obtained public key belongs to the stated identity string. (In other words, the method of distributing the user's public key does not have to be secure.) The identity string and the KGC's public key can be used to verify that the obtained public key belongs to the identity string. (It can be verified that the obtained public key was generated from the identity string, the KGC's private key and some unknown value). Note that multiple public / private key pairs can be generated for any identity string, but attackers would not have access to the KGC's private key in the creation process.
To encrypt a message to another user, three pieces of information are needed: 1) the recipient's public key and 2) identity string, and also 3) the KGC's public information (public key). The identity string and the KGC's public key are used to verify that the recipient's public key belongs to the recipient (was generated from the identity string and the KGC's public key). To decrypt, a user just needs to use their private key.
For tight security, a certificateless system has to prove its security against two types of adversaries. Type 1 Adversary- Refers to any third party who can fake the user's public keys, corresponding to obtaining the user's random secret value. Type 2 Adversary- Refers to a compromised or malicious KGC, who has access to the partial public and private keys of all users.
- Sattam S. Al-Riyami and Kenneth G. Paterson, Certificateless Public Key Cryptography, Lecture Notes in Computer Science, pp. 452 – 473, 2003 .