# Certificateless cryptography

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.

## History

The authors, Al-Riyami and Paterson, aimed to address the issue of key custody in the identity-based model, specifically targeting the encryption protocol developed by Boneh and Franklin (2003). Their proposed approach, Certificate-Based Public Key Cryptography (CL-PKC), seeks to enhance two existing models. Compared to traditional Public Key Cryptography (PKC), CL-PKC simplifies the structure by eliminating the need for digital certificates. In contrast to the identity-based model (ID-PKC), it improves security by removing the requirement for key escrow. To develop this hybrid model, which lies between identity-based systems and conventional PKC with digital certificates, Al-Riyami and Paterson drew inspiration from Girault’s self-certified public key model (1991) and Boneh and Franklin’s identity-based scheme (2001).

## Key Distribution

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.

## Encryption and Decryption

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.

## Security

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.