Re: [CFRG] How will Kyber be added to HPKE (9180)?

[John Mattsson <[e-mail]>]

Nail wrote:
>Isn't there a straightforward generic construction of an >AKEM from a normal KEM plus a (PQ) signature scheme >that could be used here? i.e., run the KEM and then sign >the encapsulated key? Obviously this would produce quite >large encapsulations, and a "key-pair" for such an AKEM >would then be two key-pairs encoded into one (with a >covering self-signature to prevent tampering). In principle >this seems doable?

I think that is a good idea. But I think the construction should probably be:


  *   Add the recipient identity to the message.
  *   Sign the message with Dilithium
  *   Encrypt [recipient ID, message, signature] with HPKE-Kyber

That is probably a good solution for CMPv3

Cheers,
John

From: CFRG <[e-mail]> on behalf of Neil Madden <[e-mail]>
Date: Thursday, 24 November 2022 at 17:00
To: Ilari Liusvaara <[e-mail]>
Cc: [e-mail] <[e-mail]>
Subject: Re: [CFRG] How will Kyber be added to HPKE (9180)?

On 24 Nov 2022, at 15:36, Ilari Liusvaara <[e-mail]<mailto:[e-mail]>> wrote:

On Thu, Nov 24, 2022 at 02:49:33PM +0000, Mike Ounsworth wrote:

Hi CFRG!

Background: we are working to add KEM support to Certificate
Management Protocol v3 (CMPv3) (draft-ietf-lamps-cmp-updates, which
will eventually be 4210bis). We are planning to accomplish this by
supporting HPKE (RFC 9180) as a new message protection mechanism in
CMPv3 and hoping that we can inherit Kyber more-or-less for free once
HPKE supports it.

Question "how": How will Kyber be added to HPKE? I assume there will
be an equivalent to section 4.1 that defines KyberKEM with its own
Encap(pkR), Decap(enc, skR), AuthEncap(pkR, skS), and
AuthDecap(enc, skR, pkS) - ie the same interfaces as for DHKEM (4.1),
but making use of Kyber internally? The Kyber2018 paper [1] figure 3
defines an authenticated Kyber exchange that looks like it should
easily fit into the existing HPKE APIs. In other words, will
supporting 9180 now with abstractions around those 4 functions allow
for easy drop-in of Kyber later?

Kyber does not support AuthEncap/AuthDecap. The whole reason why Auth*
interfaces is optional is to allow for KEMs that do not allow non-
interactive authentication, like the post-quantum ones.

In fact, the only possibly-PQC algorithm to support AuthEncap/AuthDecap
is CSIDH (not to be confused with totally broken SIDH/SIKE), and
security of that in both classical and quantum settings is subject to
debate.

Isn't there a straightforward generic construction of an AKEM from a normal KEM plus a (PQ) signature scheme that could be used here? i.e., run the KEM and then sign the encapsulated key? Obviously this would produce quite large encapsulations, and a "key-pair" for such an AKEM would then be two key-pairs encoded into one (with a covering self-signature to prevent tampering). In principle this seems doable?

-- Neil