Re: [CFRG] Chempat: Generic Instantiated PQ/T Hybrid Key Encapsulation Mechanisms

["D. J. Bernstein" <[e-mail]>]

Aron Wussler writes:
> SHA3-256(counter | ct_DHKEM | ss_DHKEM | ct_PQKEM | ss_PQKEM | ctx)
> only valid with fixed-size artifacts. Simpler structure.

It's shorter, but a closer look shows that it unnecessarily triggers
security concerns and efficiency concerns:

   * Omitting public keys makes security reviewers worry about the
     security questions raised in https://eprint.iacr.org/2021/708 and
     https://eprint.iacr.org/2021/1351.

   * Not having the internal H() wrappers around the hybrid public key
     and the hybrid ciphertext makes people worry about memory usage on
     small devices (as we saw in earlier messages).

These are weak arguments, but I think it's better to just get rid of
them. The CPU-cycles counterargument doesn't stand up to examination:
hashing the data is orders of magnitude cheaper than transmitting it.

> - Does not make security analysis simpler (you still need to argue
> about artifact size)

Reviewing "Just use fixed-size primitives" is easier than reviewing
rlen() implementations. Since you mention RSA: fixed-size RSA encodings
are easier than variable-size RSA encodings.

More importantly, a combiner that simply asks for IND-CCA2 KEMs is
easier to review than a combiner that makes ad-hoc assumptions about
KEMs, such as the QSF combiner inside X-Wing.

Even more importantly, N different combiners mean N things that need
security review, so we should be trying to end up with N as small as
possible. There's a clear argument that this shouldn't be N=0 (see
https://blog.cr.yp.to/20240102-hybrid.html) but I don't know why N=1
shouldn't be achievable. Allowing something like X-Wing is going to
force N upwards.

> - Could be replaced with a practical instantiation in
> draft-ounsworth-cfrg-kem-combiners instead of making a 5th draft.

Looks to me like trying to do something like chempat-00 as diffs to
kem-combiners-05 would take more space than chempat-00 does, so having
it as a separate document seems reasonable.

---D. J. Bernstein