16

Recently we have seen a lot of papers on Post-quantum key-establishment (key encapsulation mechanism or Key-exchange), largely due to the standardization call of NIST for PQ-protocols. However, most of the work for example : Kyber, NTRU-prime, NTRU-KEM focuses on key-encapsulation rather than Key exchange. Now my questions are as follows :

  1. KEM is a unilateral protocol whereas key-exchange is a bilateral protocol. i.e key is chosen by the client and server gets the key via decryption. Intuitively bilateral protocols (FRODO and NewHope) looks better than the unilateral (KEM) protocols. As both the parties participate in choosing the key. Then why there is more focus on KEM?

  2. Consider this scenario, if we assume that Key exchange establishes a random key on both sides then Client can pick up a random string XOR with the key and send the XOR'ed value to the server. Since, server has the same key, server can easily retrieve the random string of client. Hence, a key exchange can work as PKE (as ElGamal from DH) and subsequently as a KEM. This scheme will be CPA secure as by assumption the established key is random. Hence, Key-exchange can is more flexible than KEM. Is it correct?

  3. I understand that the current key-exchange schemes have a very high failure probabilities than KEMs. And, Hence they can be converted to CCA secure schemes by well known BLack-box transformations for key re-usability. But if we can come up with Key-exchange schemes with similar failure probabilities as KEMs and able to convert them to CCA secure schemes then should we favour Key-exchange schemes more than KEMs?

I appreciate your help.

Lery
  • 7,679
  • 1
  • 26
  • 46
Rick
  • 1,265
  • 8
  • 17
  • 3
    KEM is sometimes easier to design. For example, RSA-KEM: pick 1024-bit primes $p < q$ with $2^{2047} < n = pq$ uniformly at random, and publish $n$ as public key; to encrypt message, pick $x \in \mathbb{Z}/n\mathbb{Z}$ uniformly at random, use $H(x)$ as secret key, and transmit $x^3 \bmod n$ alongside ciphertext. Contrast with, e.g., the complexity of RSAES-OAEP. But KEM can always be built out of key agreement using an ephemeral key pair whose public part is transmitted along with the message. For example, all DH-based public-key encryption, e.g. ECIES, is built out of KEM made that way. – Squeamish Ossifrage Aug 22 '17 at 17:36
  • @SqueamishOssifrage Correct me if I am wrong. So you mean KEM is easier to build than KEX. So, if I can build a KEX with very low failure probability (as it occurs in Lattice based systems) I can use that as a PKE system as well as a KEM. – Rick Aug 23 '17 at 08:57
  • 1
    KEM is sometimes easier to build than KEX—it's easy to make a KEM out of the RSA trapdoor permutation, McEliece naturally lends itself to KEM, etc., and generic KEM-out-of-KEX construction is simple, whereas KEX-out-of-KEM is complicated. That said, I should have clarified that KEM can always be built out of reusable KEX like X25519. For a counterexample, last I checked, current SIDH KEX proposals did not allow reusing key material, so they're unfit for KEM with a long-term public key. [citation needed], etc., sorry—not enough time to make this a properly cited answer at the moment. – Squeamish Ossifrage Aug 23 '17 at 13:35
  • @SqueamishOssifrage Please consider writing an answer. Have put a cherry on top. – Maarten Bodewes Oct 19 '17 at 09:50
  • @MaartenBodewes: Sorry, I took a crypto.se vacation and it looks like K.G. answered it quite well anyway! (Could maybe use some more concrete examples, but otherwise better than I would have written.) – Squeamish Ossifrage Nov 03 '17 at 01:49

1 Answers1

17

First, some definitions.

  • A public key encryption scheme (PKE) is a scheme with public and private keys, where we can encrypt a message using the public key and decrypt using the private key.

  • A key encapsulation method (KEM) is a scheme with public and private keys, where we can use the public key to create a ciphertext (encapsulation) containing a randomly chosen symmetric key. We can decrypt the ciphertext using the private key.

  • A key exchange protocol (KEX) is a protocol that allows Alice and Bob to agree on a shared symmetric key. A two-move KEX is a protocol where Alice sends a single message to Bob, Bob replies with a single message to Alice, and afterwards they both have the same symmetric key.

Next, some context.

  • Any PKE with sufficiently large plaintext space can be trivially turned into a KEM.

  • Any KEM can be turned into a PKE by adding some symmetric encryption. (This is often called hybrid encryption.)

  • Any CPA-secure KEM can be turned into a passively secure KEX. (Alice runs KEX key generation and sends the public key to Bob. Bob creates a ciphertext containing a randomly chosen symmetric key and sends it back to Alice. Alice decrypts the ciphertext and gets the symmetric key.)

  • Some passively secure two-move KEX can be turned into a CPA-secure KEM. (The process that leads to Alice's message is key generation. The public key is Alice's message. Alice's state after sending the message is the private key. The process that leads to Bob's message and the shared symmetric key (in response to Alice's message, that is, the public key) is key encapsulation, and Bob's message is the public key.)

  • A passively secure two-move KEX can be turned into an actively secure three-move KEX using digital signatures. (Bob signs both messages and sends the signature as part of his message. Alice signs everything and sends the signature as the third message.)

In other words, these notions are tightly related. (There are lots of details and simplifications in the above, but morally, it should be roughly correct.)

Now to your actual questions (which are a bit unclear, but let's make an attempt at answers).

  1. Compared to traditional PKEs like RSA-OAEP, designing a KEM and proving it secure is often easier. Likewise, compared to traditional key exchange schemes, designing a KEM and proving it secure is often easier. Then we can turn the KEM into a PKE using hybrid encryption, and we can turn it into a KEX with a standard conversion theorem. This is why KEMs are attractive objects to design and study.

  2. Your sketch seems fundamentally similar to the above two-move KEX => KEM argument. However, that doesn't mean that a KEX is easier to design and analyse (from scratch). Experience suggests otherwise.

  3. The traditional definitions of PKE, KEM and KEX doesn't allow the process to fail in the usual case. For traditional schemes, this has always been easy to guarantee. For newer schemes, this does not seem to be the case. Typically, there's some probability that things will go wrong (decryption failures). This makes analysis much more difficult, but not impossible (as NTRU shows us). Still, I don't think the presence of decryption failures changes the fact that KEM design and analysis seems to be easier than KEX design and analysis.

K.G.
  • 4,617
  • 16
  • 32
  • @Rick if possible could you indicate if this answers the question? It's some time ago, but it would be nice to have some confirmation from the org. author of the question. It certainly looks good to me... – Maarten Bodewes Oct 21 '17 at 19:54
  • @MaartenBodewesSorry, I was little busy for some time. I think this answer is very good. I have marked the answer. Thank you all. :-) – Rick Nov 07 '17 at 15:06
  • @K.G. Could you give some references for the transformation from 2-pass KEX to CPA-secure KEM? I've been looking for that recently :) – cygnusv Dec 08 '17 at 21:55
  • @cygnusv Sorry, I don't have any. It does not mean that there aren't any. I certainly don't claim that it's my original idea. – K.G. Dec 09 '17 at 14:43