I'm looking at alternatives to PKI and I'm having trouble understanding exactly how certificateless public key algorithms (e.g. Al-Riyami and Paterson, Liu et al) work in practice. It seems like the "partial private key" generated by the KGC in these systems is not actually confidential information (which would be awfully convenient for practical use of the system), but if it isn't, then I don't understand why the KGC and its master secret are necessary.

(I hope this isn't too "practical" a question for this site.)

  • $\begingroup$ Since tags beginning with cs are being reorganized to remove the cs prefix (meta.cstheory.stackexchange.com/questions/340/…), the correct tag to use here is [cr.crypto-security]. Since no questions were given the [cr.crypto-security] tag before this one, you might have received some weird error message (or you might not, I do not know how the system of this website works). $\endgroup$ Sep 20, 2010 at 23:56
  • $\begingroup$ It was saying that I didn't have enough reputation points to create the tag [cr.crypto-security], which was completely baffling, but I think I understand now. Thanks for fixing it. $\endgroup$
    – zwol
    Sep 21, 2010 at 0:45

2 Answers 2


The best way to answer this is to look at the security model in that paper. If the adversary is allowed to request the partial private key for the target identity (i.e. the one it uses in the left-right query during the attack), then partial-private-keys are not meant to be kept secret. If the adversary is not allowed to do so, then they must remain confidential.

After scanning their model, it seems that all partial private keys are readily supplied to adversary via Extract-Partial-Private-Key-of-A queries. This means they don't need to be kept secret.

I've got to run now, but I'll edit later if I've gotten this wrong.

  • $\begingroup$ I saw that, and I thought that that's what it meant, but if that's true I don't understand what the KGC is needed for - couldn't it be replaced with "generate a random number"? $\endgroup$
    – zwol
    Sep 21, 2010 at 0:47
  • $\begingroup$ Interestingly, the paper directly contradicts what I said above: "The process of supplying partial private keys should take place confidentially and authentically: the KGC must ensure that the partial private keys are delivered securely to the correct entities." The model does not represent this, at least in my reading of it. $\endgroup$
    – David Cash
    Sep 21, 2010 at 1:51
  • $\begingroup$ Apparently the edits to comment above were lost. I was adding that the KGC provides some sort of authenticity - without an authority, there is no way to distinguish real keys from fake keys. I'm not sure what type of authenticity they provide. (Sorry for the vague answer - crypto questions don't get much attention on here, so I'm doing my best without having read all of the CL-PKE papers...) $\endgroup$
    – David Cash
    Sep 21, 2010 at 2:08
  • $\begingroup$ So what I'm really wondering is if it would be possible to use a public signature that exists for some other reason (like, it's the DNSSEC signature for the apex of your zone) as the partial private key. I'm not sure that is better than just signing the complete public key, except that it might let you derive a whole bunch of keys from one signature without further involvement by the trusted third party. $\endgroup$
    – zwol
    Sep 22, 2010 at 17:40
  • $\begingroup$ Extract-Partial-Private-Key-of-A queries must be authenticated somehow. That method is the basis of the trust that the KGC is giving for its users. If any adversary can just get a partial private key, the KGC brings no new trust over just self-signed certificates in the traditional model. $\endgroup$
    – Nakedible
    Dec 19, 2010 at 21:33

In certificateless public key cryptography, the partial private keys are confidential information. Namely:

  • If an adversary has access to party A's partial private key $D_a$, it can publish a false public key $P_a'$, and is able to decrypt any communication addressed to it and able to create signatures with it

The only thing keeping this from happening (that is, the only thing that is authenticating the user) is that it has possession of $D_a$ - the secret part that the user has is only used to prevent message decryption and signing by other parties except the user, but it obviously plays no part in authentication, as anybody can create such a secret part.

If the server is compromised, the server can fake any key for anybody any way they wish - just like in identity based cryptography - the only special sauce that certificateless public key cryptography adds is that on server compromise, the adversary still can not decrypt any messages for the user or fake any signatures for the old published public key.

  • Even if an adversary gains access to $D_a$, the only thing lost is authentication, as the adversary can publish a new key $P_a'$, but confidentiality or non-repudiation for messages with the old public key $P_a$ are not lost

A simple way to think about certificateless public key cryptography:

  • KGC creates a keypair for you and sends it to you
  • You create a keypair by yourself
  • Possession of the KGC generated private key certifies that the KGC trusts you
  • Possession of your own private key certifies yourself, so the KGC can't fake you
  • When signing a message, you sign it with both keypairs, proving that the KGC trusts you, and that you are indeed you
  • When somebody verifies your signature, they need both public keys to be convinced that both conditions hold

From this, it should be obvious that both keypairs need to be proper keypairs with public and private parts, and that the private parts need to be kept secret for the authentication to have meaning.

Obviously this is a crude simplification, as the real method combines the two keypairs and uses identity based cryptography for the KGC keypair - but the basic idea applies.

  • $\begingroup$ I think I get this, but could you comment particularly on the scenario I mentioned in my comments on David's answer, where instead of a KGC, you use a public signature that exists for some other reason as the partial private key? $\endgroup$
    – zwol
    Dec 20, 2010 at 19:26
  • $\begingroup$ If the public signature for some other reason is really that, public, then anybody who has access to that can use that as a partial private key, create a keypair, and publish their own public key - and there would be no way to tell your correct key apart from the false key that other party has published. If that signature, on the other hand, is only available to you, then no outsider can verify the signature and you don't still gain anything beneficial. $\endgroup$
    – Nakedible
    Dec 20, 2010 at 20:59

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.