[lamps] Re: [EXTERNAL] No security proof for replacing curves with RSA in composite KEMs

[Deirdre Connolly <[e-mail]>]

Thanks for the thread pointer, that's helpful background.

> isn't it true that if RSA-OAEP is IND-CCA while ECDH is not, then
RSA-OAEP is a stronger component, and you should be able to swap out ECDH
for RSA-OAEP without reducing security?

That's not how security proofs work. One _may possibly_ be able to write a
_new_ proof of IND-CCA of the hybrid construction under new assumptions of
the components, but smashing together the IND-CCA proof from "KEM
Combiners" and the one from "X-Wing" doesn't necessarily imply an IND-CCA
construction, you have to actually construct the new proof. I think that's
what Stavros' last message was getting at:

[image: image.png]

I do not read that as 'sure just swap out RSA-OAEP for ECDH in QSF, the
proof(s) let you do that': I read that as 'one can probably write a _new_
proof that makes a new argument from the ideas in both KEM Combiners and
X-Wing'.

Either way we need to fix the text in the document regarding its claims
about the QSF proofs applying, removing the line about 'extending QSF'
completely is one way.



On Tue, Aug 12, 2025 at 9:05 AM Mike Ounsworth <[e-mail]>
wrote:

> Hi Deirdre,
>
> Yes, it's true that this sentence is rather weak, I would welcome
> suggestions for improving it.
>
> Super informally, isn't it true that if RSA-OAEP is IND-CCA while ECDH is
> not, then RSA-OAEP is a stronger component, and you should be able to swap
> out ECDH for RSA-OAEP without reducing security?
>
> After years of iterating this design, I don't think there is any better
> way to integrate the RSA-OAEP component, but I would welcome contributions
> for text that more accurately reflects the security properties of this
> construction.
>
> For context, here is the github issue that shows how this text got the way
> it is now:
> https://github.com/lamps-wg/draft-composite-kem/issues/54
> <https://github.com/lamps-wg/draft-composite-kem/issues/54>
> Issue #54 · lamps-wg/draft-composite-kem - GitHub
> <https://github.com/lamps-wg/draft-composite-kem/issues/54>
> johngray-dev commented Aug 1, 2024 For a security proof of the ML-KEM +
> ECDH combos, we can point to the X-Wing paper. We should have a similar
> proof for the RSA-OAEP combos. Not sure how to go about attracting someone
> to help with this, or if we should attempt proof-writing ourselves. The
> text was updated successfully, but these errors were encountered:
> github.com
>
>
> ---
>
> *Mike* Ounsworth
>
>
> ------------------------------
> *From:* Deirdre Connolly <[e-mail]>
> *Sent:* Monday, August 11, 2025 7:36 PM
> *To:* LAMPS <[e-mail]>
> *Subject:* [EXTERNAL] [lamps] No security proof for replacing curves with
> RSA in composite KEMs
>
> I just noticed this bit in -composite-kem-07¹: > The QSF framework
> presented in [X-Wing] is extended to cover RSA-OAEP as the traditional
> algorithm in place of DH by noting that RSA-OAEP is also IND-CCA secure
> [RFC8017]. The X-Wing proofs²
> I just noticed this bit in -composite-kem-07¹:
>
> > The QSF framework presented in [X-Wing] is extended to cover RSA-OAEP as
> the traditional algorithm in place of DH by noting that RSA-OAEP is also
> IND-CCA secure [RFC8017].
>
> The X-Wing proofs² rely on SDH security of the curves as nominal groups in
> the ROM model and the IND-CCA security of ML-KEM in the standard model
> (among other things such as C2PRI and PRF security). There is _no_
> consideration of the IND-CCA-ness of the traditional components of the
> hybrid KEM construction in these proofs.
>
> Have there been new proofs of the IND-CCA-ness of this construction using
> RSA instead of nominal groups?
>
> Cheers,
> Deirdre
>
> ¹
> https://www.ietf.org/archive/id/draft-ietf-lamps-pq-composite-kem-07.html#section-10.2.1-3
> <https://urldefense.com/v3/__https://www.ietf.org/archive/id/draft-ietf-lamps-pq-composite-kem-07.html*section-10.2.1-3__;Iw!!FJ-Y8qCqXTj2!e2rvU9IXq7WNRQ0ozZSLNRHsXXPKkidI1aVbqRVuSUk2FRh_tSIYIr8IGbcV57RzSN_FozWH-mlAAiuPmhqI9QOPuq7qLNNyzaw$>
> ² https://eprint.iacr.org/2024/039.pdf
> <https://urldefense.com/v3/__https://eprint.iacr.org/2024/039.pdf__;!!FJ-Y8qCqXTj2!e2rvU9IXq7WNRQ0ozZSLNRHsXXPKkidI1aVbqRVuSUk2FRh_tSIYIr8IGbcV57RzSN_FozWH-mlAAiuPmhqI9QOPuq7qwblbE_o$>
>
> *Any email and files/attachments transmitted with it are intended solely
> for the use of the individual or entity to whom they are addressed. If this
> message has been sent to you in error, you must not copy, distribute or
> disclose of the information it contains. Please notify Entrust immediately
> and delete the message from your system.*
>
>