While reading "Certificateless Public Key Cryptography" by Author Sattam S. Al-Riyami and Kenneth G. Paterson, they have considered generation of private keys by a Key Generation Center (KGC). If the KGC gets compromised it will break security, so why should a KGC generate private keys.

Will it be possible that user will generate pair of public and private keys and for authenticity of public key only, we will use some trusted center?


2 Answers 2


If the KGC gets compromised it will break security, so why should a KGC generate private keys.

Certificateless crypto tries to overcome the problem which exists in identity based crypto, i.e., that the KCG generates all the private keys of the users (that is necessary in IBE, see below) and thus knows all the private keys of users (which in turn enables the KCG to decrypt all the ciphertexts intended to it's users). Certificateless crypto is similar to IBE (thus requires a KCG), but does not reveal the entire private key to the KCG.

However, if the KCG in certificateless crypto gets compromised, then you have a problem which also exists with certification authorities (CAs) in public key crypto. In particular, someone who gets the private key of the KCG in certificateless crypto or of the CA in context of public key crypto can incorporate all users he would like to. Essentially, due to fact that he can issue "fake" keys on behalf of users and pretending that they are authentic keys. However, in IBE a compromise is much more devastating than in certificateless crypto or public key crypto, since in the latter two cases the adversary may only issue new "fake" keys but is not able to regenerate all the previous keys as it is the case with IBE (which allows him to decrypt all the previous ciphertexts intended to registered users).

Will it be possible that user will generate pair of public and private keys and for authenticity of public key only, we will use some trusted center?

That is the case in public key crypto (but as said above, that will not help against a compromised CA which certifies the keys) and in part the case with certificateless crypto.

If we do not assume a compromise of the CA/KCG but that the KCG works as it is supposed to work, then one can subsume the three different concepts as follows. I'll try to give you the big picture and hope it helps you to understand the idea of certificateless public key cryptography.

We have three basic approaches in the field of public key cryptography:

  1. In traditional public key cryptography, a user $A$ generates a private/public key pair $(sk_A,pk_A)$ locally and since this key pair has absolutely no indication to which indentity (user $A$) it belongs, it is necessary to certify the public key, i.e., bind the public key $pk_A$ to the user $A$'s identity. This is commonly done by letting some trusted authority, a certification authority (CA), sign $pk_A$ with additional identifying information of user $A$ after user $A$ proves by some means that he really is user $A$ (the result is what is called a certificate). To encrypt some message for users you have to obtain an authentic public key of the CA and for every user.

  2. Identity-based cryptography aims at letting the users public key be its identity (e.g., the email address) and so to remove the requirement for certificates. In ID based cryptography a user $A$ uses his identity (e.g., his email address) as public key. Now, however, since this identity could be used by anybody to compute the respective private key, it is clear, that there needs to be some other entity involved in generating the respective private key (To see the requirement for such an entity, think of the fact that I could use your email to compute a private key for your identity otherwise). We require a trusted authority (the KCG) owning some secret master key to compute the private key $sk_A$ that corresponds to the public identity string $ID_A$ and this trusted authority has to check whether $ID_A$ (e.g., the email address) indeed corresponds to $A$ and then issues the private key $sk_A$ corresponding to the identity $ID_A$. The advantage is, that you only need the parameters (corresponding to the master secret) of the KCG in an authentic fashion but no longer any authentic key of the users. Now, however, the KCG knows your private key and may use this private key to decrypt your messages, so it needs to be fully trusted. That's an inherent problem of identity based cryptography, although one may implement multiple KCGs (each having a share of the master secret) who compute the private keys for identities in a distributed fashion, so that neither gets to know the entire private key of a user. But it is questionable if this is really practical.

  3. Certificateless public key cryptography is inbetween these two approaches. It aims to get rid of the problem that the KCG gets to know the entire private keys of all users. Having said that, in this approach the KCG only computes a partial private key of user $A$ based on the identity $ID_A$ (clearly, also here user $A$ has to prove by some means that $ID_A$ is associated to him) and the user then combines this partial private key with some secret information (only known to him). Consequently, the KCG no longer gets to know the entire private keys of the users. Then a user, however, needs to take the parameters of the KCG and needs to combine the user chosen secret with this parameter to obtain an additional user public key. So, to encrypt a message for a user the identity string plus this public key is required. The advantage here, however, is that this public key does no longer need to be certified, since it contains the identity $ID_A$ of user $A$ and if the KCG is trusted (and the parameters of the KCG are authentic) one can assume that the user associated to $ID_A$ really corresponds to $A$ and holds the corresponding private key.
  • $\begingroup$ Thank u sir for reply.. Consider the following scenario. There are two users.. $\endgroup$
    – Ravi
    Nov 7, 2013 at 11:55
  • $\begingroup$ @Ravi, if you are simply talking about a two user system, it's possible for the two users to meet and simply exchange public keys; or they could even exchange a secret key and skip all the public key work. In this case, the two parties establish and validate their identities independent of the cryptography; from there, continued possession of the other's key serves as your authentication. In general, public key cryptography looks for ways to avoid establishing individual trust connections, in order to minimize cost or maximize flexibility. But that means all parties must trust a third party. $\endgroup$ Dec 12, 2013 at 21:46
  • $\begingroup$ since the public key used in certificateless cryptography is not certified, then there is scenario that someone will replace this public key for malicious use. $\endgroup$
    – T.B
    Mar 7, 2014 at 0:53
  • $\begingroup$ @Alex indeed, an adversary may replace the public key oft a user. However, he will still not be able to decrypt a message encrypted with respect to the identity oft the attacked user and the malicious public key. Essentially this would result in something like a denial of service. $\endgroup$
    – DrLecter
    Mar 7, 2014 at 6:34
  • $\begingroup$ @DrLecter reading on Wikipedia (en.wikipedia.org/wiki/Certificateless_cryptography) I read that: 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. Why is it possible to generate multiple public/private key for the same ID? How can is possible to do that? $\endgroup$
    – CipherX
    Mar 19, 2019 at 8:10

In Kerberos, if the Key Distribution Center is compromised then all the stored keys are exposed. In PKI, if a Certificate Authority is compromised then certificates may be forged. So, I guess we typically assume that the "trusted" third party will not be compromised so easily? Because either method you choose, there are still some inherent risks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.