Re: [lamps] Which PQC KEMs can be used for composite encryption?

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

To flesh out the below idea, here is what the encryption/decryption procedure would look like:

Generation Procedure:

   1. If recipient public key is of type id-composite-or-key, determine the
      index of the last recipient public key to be encrypted for
        i_last := index of last Pi to be encrypted for
      Else,
        i_last = n
     Set K to a supported Key Derivation Function listed in the public key.  If no such Key Derivation Function in the list, return FAILURE

   2. To generate secret keys Sn, compute the following

      C := emptyOctetString
      for i := 1 to n

        a. If id-composite-or-key and Pi is to be skipped
          Ei := emptyOctetString
          continue to next i

        b. If Ai is a public key encryption scheme
            S := random_bits(SIZE)
            Ei = encrypt(S, Pi, Ai)
            C := C || S
          Else /* Ai is a key exchange method */,
            Ei, S := kem_generate(Pi, Ai)
            C := C || S

   3. Compute CEK := K( C, nonce )    /* The nonce is passed in by the caller */

   4. Output CEK and E1, E2, .., En

Decryption Procedure:
   1. C := emptyOctetString
       K := KDF selected in the ciphertext
        for i := 1 to n
          if Ei != emptyOctetString
            If Ai is a public key encryption scheme
              C := C || decrypt(Ei, SKi)
           Else
              C := C || kem_receive( Ei, Ski )

   3. Compute CEK := K( C, nonce )

   4. Output CEK

Obvious things to work out (assuming that you are willing to entertain such a change):

- I mention SIZE during the encryption process - what is that?

- I don't know if there is an existing IANA registry for KDFs that we could use - would we have to define it?

- I have heard of a complaint that if the KDF was based on a non-collision-resistant hash function, then (because we're using concatenation before the KDF) in some attack models, he could learn the initial byte or two of the next secret.  Is this an issue we should try to address?

-----Original Message-----
From: Scott Fluhrer (sfluhrer) 
Sent: Thursday, September 16, 2021 9:58 AM
To: Ilari Liusvaara <[e-mail]>; Bruckert, Leonie <[e-mail]>
Cc: [e-mail]
Subject: RE: [lamps] Which PQC KEMs can be used for composite encryption?

> So my question is: Do we know any PQC KEM that can be used with this 
> mode?

I think we agree that we want something that can be used with any reasonable encryption or KEM primitive (even ones that haven't been invented yet), hence the requirement that this draft places on KEMs is too restrictive (even ignoring the valid points that Leonie brings up).

One obvious modification we could place on the draft is to send the output of any KEMs through a KDF.  Actually, sending everything through a KEM would mean that, even if only public key encryption algorithms are used, neither side could set the CEK to an arbitrary value.  The implicit API in the Generation Procedure doesn't support that (it assumes the CEK comes from the caller, that is, someone selects the value) - would it be an issue to change that?

Of course, the problem with specifying a KEM (apart from the added complexity) is that both sides need to agree on it.  One approach would be to have the public key contain a list of KDFs that the decryptor supports, and have the ciphertext include the KDF that the encryptor used.

Would this be a reasonable (if somewhat radical) change to the draft?