0
$\begingroup$

Can Crystal Kyber and Classic McEliece be used as public key encryption (PKE) algorithms?. Is there any problem with using these KEM algorithms as PKE for some reason, e.g., doing some holomorphic operations?

$\endgroup$
7
  • $\begingroup$ Why not? What prevents public key cryptosystems to be used as KEM? Kyber is already designed for KEM and McEliece can be turned into KEM, encrypt random then use a KDF on the decryption, done. $\endgroup$
    – kelalaka
    Commented May 8 at 8:47
  • 2
    $\begingroup$ Seeing "holomorphic operation" coming up alongside "PKE", I suspect you've confused something. Key Exchange, Public-Key Encryption, and Key Encapsulation Mechanism are functionally equivalent, and can be converted from/to one another, barring semantic security difference. But "holomorphism" doesn't come into the picture. $\endgroup$
    – DannyNiu
    Commented May 8 at 9:09
  • $\begingroup$ @DannyNiu Your comment was interesting. I had a question, is it possible to design an KEM that does not need a public key (same as Diffie-Hellman key exchange). Clearly, do we always need to have a public key plan for design KEM, and it is not possible to design a plan KEM independent of the public key like plan Diffie-Hellman. In fact, the KEM schemes of the third round of NIST are all based on a public key scheme. $\endgroup$
    – Amin235
    Commented May 8 at 11:54
  • $\begingroup$ Diffie-Hellman key exchange doesn't use a public key? Where did you see that? $\endgroup$
    – kelalaka
    Commented May 8 at 14:48
  • $\begingroup$ @kelalaka I know that Diffie-Hellman key exchange doesn't use a public key. I said is there a KEM such that doesn't use a public key (similar to Diffie-Hellman)? In fact, Kyber, Forodo, Bike,...use public key in order to key encapsulation mechanism. $\endgroup$
    – Amin235
    Commented May 8 at 19:18

1 Answer 1

3
$\begingroup$

Yes and no.

Kyber and Classic McEliece refer to specific protocols which are KEMs, so in an obvious and boring sense neither one works as a PKE since a KEM does not take a message as an input.

But, could you take the underlying scheme and make a PKE out of either one? As you point out, both Kyber and Classic McEliece start with PKEs and build KEMs out of them. However, in both cases these starting points are vulnerable to chosen ciphertext attacks, so generally, using them as a "direct" PKE is a very bad idea.

Instead, you could (for example) take the Kyber PKE (Kyber.CPAPKE from the specification) and apply the Fujisaki-Okomoto transform to obtain a CCA-secure PKE. You could similarly do this to the McEliece scheme. Note that the FO transform used in the Kyber specification is a variant that produces a KEM, not a PKE, so you would need to use the original FO transform.

Or, you could take the KEM, and use the key that it produces to encrypt a message with a symmetric cipher (i.e., what's actually done in practice).

I'm not sure what you mean by saying that Diffie-Hellman does not use a public-key. What you might be interested in is a non-interactive key exchange. These are harder to build from post-quantum assumptions, though here's an example: https://eprint.iacr.org/2023/271

$\endgroup$
1
  • $\begingroup$ Thanks Sam for this deep answer. $\endgroup$
    – Anas Ahmad
    Commented May 12 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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