Re: [Pqc] IND-CPA *only* KEMs

[Thom Wiggers]

Hi Demi,

The difference between IND-CCA and -CPA parameters for most of the KEMs considered in the NIST competition was comparatively pretty small. Meanwhile, admitting IND-CPA schemes “into the wild” risks significant user error as most “users” are absolutely unable to make the determination whether they can get away with CPA KEMs—or someone comes along later and makes a determination that it’s fine to just reuse ephemeral keys for a while (like in some TLS implementations).

PQ WireGuard [1] is an interesting case because they were able to use IND-CPA parameters for (tweaked) SABER to boost its security level. However, it’s a pretty unique case and WireGuard with KEMs has to give up some of the security properties on the first message due to no longer having static-static DH key agreement to provide immediate authentication. 

Cheers,

Thom Wiggers

[1] https://eprint.iacr.org/2020/379

PS: Your references are missing. Your [1] probably refers to my [1] though. 

Op 14 apr 2026, om 00:52 heeft Demi Marie Obenour <demio...@gmail.com> het volgende geschreven:

Certain applications don't require IND-CCA security, only IND-CPA.
Furthermore, some of them (like WireGuard) need to fit everything in a
single UDP packet.  If one needs to fit a Classic McEliece ciphertext
and a KEM ciphertext in a UDP packet, the only currently-standardized
algorithm that fits is ML-KEM-512.

However, browsers are currently using ML-KEM-768 for TLS, presumably
because it has more margin against advances in cryptanalysis.
Using weaker cryptography in a VPN seems rather risky.

The original post-quantum WireGuard paper [1] proposed a KEM they
called Dagger.  It's a modified Saber with a harder lattice problem
but much higher decryption failure rate.  However, decryption failures
are not a problem for UDP-based applications using ephemeral keys.
They are handled just like a dropped UDP packet.

Should there be algorithms that are designed for this purpose?  At a
minimum, an IND-1CCA version of ML-KEM is sufficient for ephemeral
keys, easy to implement [2], and faster.  Or should anything that
needs to fit in an MTU settle for a two-round handshake?  That would
be less than desirable for obvious reasons.
--
Sincerely,
Demi Marie Obenour (she/her/hers)
<OpenPGP_0xB288B55FFF9C22C1.asc>--
Pqc mailing list -- p...@ietf.org
To unsubscribe send an email to pqc-...@ietf.org

[Bas Westerbaan]

If you're happy to look at alternative KEMs, better to also look at more recent developments such as for instance BAT, SMAUG-T, NEV, and DAWN. Usual caveats apply.

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/EB7275D3-0A8C-485D-9B91-C2A909889300%40thomwiggers.nl.

[Deirdre Connolly]

Strong agree with Thom on the risks of IND-CPA KEMs escaping containment 

[Thom Wiggers]

Instead of tweaking the parameters for {M,R}LWE-schemes like Kyber and SABER or for NTRU-based schemes, where if I remember Round 2 sizes correctly it did not make a huge difference, it’s probably better to, as Bas said, look at more novel designs like BAT or NEV. These have <600 byte public keys and ciphertexts, and are CCA secure.

Regards,

Thom 

Op 14 apr 2026, om 16:20 heeft Denise L. Davis <dld...@DUIT.us> het volgende geschreven:

Thom and Demi,

The debate over IND-CPA and MTU constraints is irrelevant if the goal is compliance with CNSA 2.0. The NSA has explicitly signaled that operational efficiency will be sacrificed for cryptographic margin. By mandating ML-KEM-1024, they have accepted that 1-RTT, non-fragmented handshakes are essentially over for National Security Systems (NSS). Any attempt to "optimize" for the MTU by using IND-CPA or lower security levels (Level 1 or 3) is a non-starter for regulated environments.

However, if the goal is to standardize PQC for the broader internet, we cannot ignore the MTU bottleneck. We should not be forced to choose between the insufficient security margin of ML-KEM-512 or the overhead of 2-RTT just to satisfy a "misuse-resistance" requirement that is logically irrelevant to ephemeral, 1-RTT protocols.

To be clear, I am not merely suggesting we strip the FO transform which provides negligible size savings. I am asking if there is a path for a High-Compression/High-DFR ML-KEM profile that optimizes the internal parameter set (k, η, d_u, d_v) specifically for 1-RTT constrained networking.

The current FIPS 203 parameters are tuned for a DFR that is overkill for ephemeral use. By relaxing the DFR to a level consistent with standard UDP packet loss (e.g., 2^-30), we can achieve the ciphertext compression necessary to fit ML-KEM-768 and a classical hybrid within a 1280-byte MTU.

Does the community want to maintain the fiction that "one size fits all" for KEMs, or are we willing to define a profile that actually works for high-performance networking?

Best,

Denise L. Davis, DUIT

D.Eng. Candidate, Johns Hopkins Whiting School of Engineering 

M.S. Applied & Computational Mathematics 

Focus: Post-Quantum Cryptography & Implementation Metrology

Co-Owner | Founder | CEO

Certified ScrumMaster®

SBA certified EDWOSB/WOSB

8(a) Small Disadvantage Business Participant

GSA STARS III GWAC

 "Why wait? Let's DUIT!"

We have moved!!! NEW Address:
Address: 1730 Twin Spring Rd, Suite 211

Baltimore, MD 21227

Tel: 301.637.5411 | Fax: 301.637.5412

Cell: 301.275.1956 | Toll Free: 1.844.NOW.DUIT

Email: dld...@duit.us | Website: http://duit.us

CONFIDENTIALITY AND DISCLAIMER NOTICE:  This e-mail message and any attachment(s) from Davis Unlimited Information Technologies, Inc. (DUIT) is intended for the sole use of the recipient(s) and may contain confidential and privileged information.  Any unauthorized disclosure, reproduction, distribution or the taking of action in reliance on the contents of the information is prohibited, unless so authorized by DUIT. If you believe that you have received the message in error, please notify the sender by reply transmission and delete the message without copying or disclosing it.

---

From: Thom Wiggers <th...@thomwiggers.nl>
Sent: Tuesday, April 14, 2026 9:17 AM
To: Demi Marie Obenour <demio...@gmail.com>
Cc: pqc-...@list.nist.gov <pqc-...@list.nist.gov>; p...@ietf.org <p...@ietf.org>
Subject: [Pqc] Re: IND-CPA *only* KEMs