Lightweight Authenticated Key Exchange

[John Mattsson]

Hi,

As preparation for an upcoming IETF Lightweight Authenticated Key Exchange (LAKE) WG interim meeting on post-quantum cryptography, I compiled a comparison of various quantum-resistant options, including some algorithms that are not (yet) standardized. For the NIST signature ramp-on, I selected the smallest multivariate- and isogeny-based signatures. The table presents the approximate total message size (in bytes) required to achieve mutual authentication with ephemeral key exchange. It assumes that both parties use the same authentication method and that the credentials for mutual authentication are referenced rather than transmitted.

	Auth API	Mutual Authentication Algorithm	Ephemeral Key Exchange Algorithm	Total Message Size (bytes)
Classical	Signature	Ed25519	X25519	220
	NIKE	X25519	X25519	120
	PSK	PSK	X25519	120
NIST PQC	Signature	ML-DSA-44	ML-KEM-512	6440
	KEM	ML-KEM-512	ML-KEM-512	3140
	Signature	FN-DSA-512	ML-KEM-512	2930
	PSK	PSK	ML-KEM-512	1630
Research	KEM	DAWN-β-512	DAWN-β-512	1890
	Signature	SQISign-I	DAWN-β-512	1280
	Signature	UOV Is	DAWN-β-512	1180
	PSK	PSK	DAWN-β-512	1020
	Signature	SQISign-I	CSIDH-2048	830
	Signature	UOV Is	CSIDH-2048	730
	NIKE	CSIDH-2048	CSIDH-2048	570

Note that “total message size” is only one of many relevant factors. KEM-based authentication requires more flights, KEM- and NIKE-based authentication benefit from requiring only a single asymmetric primitive, whereas signature-based authentication require two, schemes such as UOV, DAWN, and CSIDH are not standardized and may never be, and while UOV offers small signatures, this comes at the cost of very large public keys.

The results highlight that the large message sizes of ML-KEM and ML-DSA, and the lack of NIKE for authentication, are significant concerns for lightweight use cases such as deep space communication and terrestrial LPWAN. It also highlights the importance of evaluating the total size of an AKE, rather than focusing solely on the size of individual algorithms. LAKE/EDHOC provide a strong framework for benchmarking lightweight post-quantum algorithms, as it supports signature-, and NIKE-based authentication, with ongoing work covering PSK and KEM-based authentication as well.

PSK authentication is not an optimal solution, as key management is complex and often fragile in practice. While NIST is making strong progress on more compact post-quantum signatures, comparable advances in quantum-resistant key exchange are also critical. With 2035 only nine years away, there is a clear need for a similar standardization effort focused on smaller, more efficient post-quantum key exchange mechanisms (both KEM and NIKE).

Comments appreciated. Did I miss any important research algorithms?

Cheers,

John Preuß Mattsson

[Bo Lin]

Hi, John,

Hope you're well!

Thanks for the summary!

Shall the HQC be included as well? It is a NIST selected KEM. Although HQC has a bigger PK size and a bigger ciphertext size than the ML-KEM's, because both scheme's sizes are quite significant, application limitations may be no big difference. That is, an application is suitable for ML-KEM, it is expected to suitable for HQC.

As you mentioned the PK size is not included. If you have chance to update the table, it would be ideal to have PK size in. The total size would help to estimate time budget when an application is given. For some applications that have "user experience" requirements, time budget for a cryptographical protocol is quite constrained.

Best regards,

Bo LIN

--
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/AS5PR07MB1059621D57011CCA91DFDA62B8949A%40AS5PR07MB10596.eurprd07.prod.outlook.com.

[John Mattsson]

Hi Bo,

Thanks for your feedback! I hope you are well. Below is an updated table including HQC-KEM, Classic McEliece, MAYO, and the authentication public key size (the ephemeral key exchange public key size was already included in the total message bytes). I also received a question about CSIDH with PSK authentication, so I added that as well to show that the number of bytes is the same for NIKE and PSK authentication.

The reason I did not include HQC-KEM in the first version was feedback from people in the IETF LAKE WG that the approximately 3000–6000 bytes required for an AKE using ML-KEM, ML-DSA, or FN-DSA is too large and, in very constrained environments, could take many hours or days to transmit. I therefore focused on algorithms with the potential to reduce the total number of bytes. As you say, it may be that most applications can either support both ML-KEM and HQC-KEM, or neither of them.

Earlier discussions in the IETF LAKE WG have generally been that the total number of message bytes is the most important factor, since for small frame sizes it is approximately proportional to the number of frames and round trips. However, memory and code size can also be highly constrained.

The Total Message Size is calculated as the sum of 26 bytes of LAKE/EDHOC protocol overhead, the key exchange ephemeral public key, the key exchange ciphertext, and twice the Verification size. Here, Verification size is defined as the signature size for signature-based authentication, the ciphertext size plus 16 bytes for KEM-based authentication, and 16 bytes for both NIKE- and PSK-based authentication.

 

Cheers,

John Preuß Mattsson

Auth API

Mutual Authentication Algorithm

Ephemeral Key Exchange Algorithm

Total Message Size (bytes)

Authentication Public Key Size (bytes)
Traditional	Signature	Ed25519	X25519	220	32
	NIKE	X25519	X25519	120	32
	PSK	PSK	X25519	120	16
NIST PQC	KEM	HQC-KEM-512	HQC-KEM-128	15800	2249
	Signature	ML-DSA-44	HQC-KEM-128	11610	1312
	Signature	FN-DSA-512	HQC-KEM-128	8100	897
	PSK	PSK	HQC-KEM-128	6800	16
	Signature	ML-DSA-44	ML-KEM-512	6430	1312
	KEM	ML-KEM-512	ML-KEM-512	3160	800
	Signature	FN-DSA-512	ML-KEM-512	2930	897
	PSK	PSK	ML-KEM-512	1630	16
Other PQC / Research	Signature	FN-DSA-512	DAWN-β-512	2320	897
	KEM	DAWN-β-512	DAWN-β-512	1920	514
	KEM	mceliece348864	ML-KEM-512	1820	261120
	Signature	Mayo 1	DAWN-β-512	1630	1168
	Signature	Mayo 2	DAWN-β-512	1350	5488
	Signature	SQISign-I	DAWN-β-512	1290	65
	KEM	mceliece348864	DAWN-β-512	1210	261120

Signature

UOV Is

DAWN-β-512

1180

66576
	PSK	PSK	DAWN-β-512	1020	16
	Signature	Mayo 2	CSIDH-2048	900	5488
	Signature	SQISign-I	CSIDH-2048	830	65

Signature

UOV Is

CSIDH-2048

730

66576
	NIKE	CSIDH-2048	CSIDH-2048	570	256
	PSK	PSK	CSIDH-2048	570	16

[赵运磊]

Hi John:

We may refer you  to our work  https://eprint.iacr.org/2026/248

Specifically, a light-weight KEM was proposed, with light-weight AKE implementations  for 8-bit AVR sensor nodes.

 

The experience justifies your consideration: Besides  the most important bandwidth factor, memory and code size can also be highly constrained, particularly for low-power devices: AVR nodes, smart-cards, etc.

 

Yunlei

Yunlei 

-----原始邮件-----
发件人: "'John Mattsson' via pqc-forum" <pqc-...@list.nist.gov>
发送时间: 2026-04-05 18:47:31 (星期日)

收件人: "Bo Lin" <boli...@gmail.com>
抄送: "pqc-...@list.nist.gov" <pqc-...@list.nist.gov>
主题: [SPAM] Re: [pqc-forum] Lightweight Authenticated Key Exchange

--
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/AS5PR07MB1059694254E8F0D70D3316841895CA%40AS5PR07MB10596.eurprd07.prod.outlook.com.

[赵运磊]

For highly constrained devices like AVR sensor node or smart-card, I may suggest memory/code size is as important as bandwidth. For these light-weight applications, most of the PQ signature standards may be too bulky.

 

Cheers

Yunlei

-----原始邮件-----
发件人: "'赵运磊' via pqc-forum" <pqc-...@list.nist.gov>
发送时间: 2026-04-05 22:53:24 (星期日)

收件人: "John Mattsson" <john.m...@ericsson.com>
抄送: "Bo Lin" <boli...@gmail.com>, "pqc-...@list.nist.gov" <pqc-...@list.nist.gov>
主题: Re: [SPAM] Re: [pqc-forum] Lightweight Authenticated Key Exchange

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/656620a5.5cb9.19d5e225f60.Coremail.ylzhao%40fudan.edu.cn.

[Bo Lin]

Thanks, John! That's very nice of you to provide such an extensive list,

Best regards,

Bo Lin

[Natalia]

Hi John,

Thank you for this. It's been a little while since I've seen a table comparison. 

You said, "With 2035 only nine years away, there is a clear need for a similar standardization effort focused on smaller, more efficient post-quantum key exchange mechanisms (both KEM and NIKE)."

Yes, I agree. This is important to look at as well. 

You pointed out that "The results highlight that the large message sizes of ML-KEM and ML-DSA, and the lack of NIKE for authentication, are significant concerns for lightweight use cases such as deep space communication and terrestrial LPWAN. It also highlights the importance of evaluating the total size of an AKE, rather than focusing solely on the size of individual algorithms."

It looks like there needs to be more attention on this as we work towards figuring out the larger framework. Was it just "deep space communication and terrestrial LPWAN" that your looking to use this system on? Wouldn't there be potential holes in the security? 

You said, "LAKE/EDHOC provide a strong framework for benchmarking lightweight post-quantum algorithms, as it supports signature-, and NIKE-based authentication, with ongoing work covering PSK and KEM-based authentication as well."

Do you have in mind an idea of the percent of systems that would utilize this framework and would this be for systems requiring less security? Is your aim speed or data load? Both?

You said, "While NIST is making strong progress on more compact post-quantum signatures, comparable advances in quantum-resistant key exchange are also critical. With 2035 only nine years away, there is a clear need for a similar standardization effort focused on smaller, more efficient post-quantum key exchange mechanisms (both KEM and NIKE).

I agree that we don't have much time to figure this out, assuming that we're even going in the right direction. 

Regarding "comparable advances in quantum-resistant key exchanges", do you have anything more specific in mind regarding "smaller, more efficient post-quantum key exchange mechanisms (both KEM and NIKE)" as far as standardization is concerned? Also, do you have an idea, percentage wise, of how many systems and more specifically what types of industries could utilize each framework? Are you proposing two standards or a main standard with substandards? I'm just trying to gauge how much attention should be placed on this and if NIST has the bandwidth for it or if they are going to need more resources to study it. I know they're working tirelessly on this, as are many people in this community. 

I don't know if we've addressed this issue before. I can't seem to recall when, if we did. 

Thanks for bringing this up. I'm looking forward to the comments. 

Cheers!

Natalia D'Onofrio, FRP, MBA

Affinity Ventures, LLC  |  Founder

P.O. Box 2059

Palm Beach, FL 33480

Tel: (561) 501-1033

 

--
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/AS5PR07MB1059621D57011CCA91DFDA62B8949A%40AS5PR07MB10596.eurprd07.prod.outlook.com.

[alex miranda]

Hi John, Bo, Yunlei, this is a very valuable comparison—especially in highlighting total message size across AKE constructions—but I would like to extend the discussion by questioning whether “total message size” is actually the dominant optimization variable for lightweight PQ AKE, or if we are instead facing a multi-dimensional constraint problem not fully captured here; in highly constrained environments like LPWAN, deep space, or AVR-class devices, the relevant cost function likely includes not only bandwidth (bytes) but also round trips (latency/reliability), memory footprint (RAM/flash), computational cost, and energy per authenticated session, which suggests that total message size is just a projection of a higher-dimensional trade-off surface; for instance, KEM-based approaches may increase protocol flights, signature-based ones increase size but reduce interaction complexity, and NIKE-based ones minimize primitives but depend heavily on parameter sizes, so it may be more appropriate to define a normalized cost model (e.g., cost = α·bytes + β·rounds + γ·RAM + δ·CPU + ε·energy) and evaluate schemes based on Pareto efficiency across these dimensions, potentially identifying application-specific optimal zones (LPWAN vs smart cards vs satellite), since some “larger” schemes might actually be optimal when minimizing retransmissions or energy per bit in unreliable channels; this could also guide standardization toward selecting algorithms based on constraint vectors rather than size alone, and I’m curious whether LAKE/EDHOC benchmarking could evolve in that direction.

Alex Miranda

CM quantum 

Santiago de Chile