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?
-
$\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$– kelalakaCommented 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$– DannyNiuCommented 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$– Amin235Commented May 8 at 11:54
-
$\begingroup$ Diffie-Hellman key exchange doesn't use a public key? Where did you see that? $\endgroup$– kelalakaCommented 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$– Amin235Commented May 8 at 19:18
1 Answer
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