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

[Ilari Liusvaara <[e-mail]>]

On Wed, Sep 15, 2021 at 10:23:06AM +0000, Bruckert, Leonie wrote:
> 
> I recently looked into the composite encryption described in
> draft-ounsworth-pq-composite-encryption, in particular option 2
> (encryption and KEMs).
> 
> If I understood correctly, the data encryption key is split into at
> least two shares, each being encrypted/encapsulated under the
> respective component public key.
> 
> I was wondering which PQC KEMs can be used with this mode. A
> requirement mentioned in the draft is that
> 
> "all component KEMs MUST produce a shared secret whose bits
> are independent and uniformly distributed (aka "uniformly IID"
> or "uniformly random" or "full entropy") and therefore the shared
> secret is safe to use directly as a symmetric key."
> 
> As far as I know, the NIST candidates are IND-CCA secure KEMs where
> the value being encapsulated is not directly used as shared secret.
> Instead it is fed into a hash function together with some other values
> (e.g. the public key) in order to receive the shared secret. Thus, I
> would conclude that these KEMs are not qualified.
> 
> So my question is: Do we know any PQC KEM that can be used with this
> mode?

There are some other problems with this:

- Some KEMs produce shared secrets that are not the usual 256 bits.
  E.g., NISTPQC altenates FrodoKEM and SIKE can produce 128- or 192-bit
  shared secrets. And even if KEM drives its shared secret output
  directly off a XOF (e.g., NISTPQC finalist Kyber), allowing any output
  length, most implementations will not support that.

  And it is not just PQ KEMs, it is also what classical KEMs produce
  (I think at least some of those drive output from some hash function
  or XOF). And I do not have a handy list of classical KEMs.

- Some encryption modes are not safe with deterministic nonces (e.g.,
  GCM mode, especially with 128-bit keys). Which means either stuffing
  randomly generated nonce into the encrypted message, or coping with odd
  key lengths no KEM is going to be able to produce in practice.




-Ilari