Use cases for small signatures and keys

[Watson Ladd]

Dear NIST,

It's great to see the third round proposals come out. I would like to
shed light on some cases where we need very small keys+signature, and
can afford some CPU time, so SQISign would be of great interest.

One is Roughtime. Recently an RFC, this specification tries to address
bootstrapping of nodes without real time clocks in a secure way. For
ecosystem reasons it requires the use of a single signature algorithm
by all servers, and uses two keys, one a long lasting key, the other
rotating. It also transmits a very small amount of data, and has
mechanisms for batching signatures together via Merkel trees. If we
were to use ML-DSA, we would have a tremendous expansion of the size
of packets, that would likely force the use of a TCP transport to
authenticate what is just 64 bits of data. Most protocols don't have
these rather stringent constraints.

Sincerely,
Watson

[Demi Marie Obenour]

DNSSEC is another case where very small signatures and keys are
important. SQISign level I is smaller than RSA-2048, and SQISign
level V is smaller than RSA-4096. DNSSEC signing can be done offline,
though it is sometimes done online. However, verification performance
might well be a serious problem.

DNS is increasingly being transported over TLS, HTTPS, or QUIC for
privacy reasons. Those transports don't have an MTU limit. Therefore,
connection-oriented transports for DNS provide a serious alternative.
This is especially the case for end-user devices, which can maintain
a long-lived connection to a public recursive resolver.
--
Sincerely,
Demi Marie Obenour (she/her/hers)

[Ondřej Surý]

Hi,

let me react to the DNSSEC part of this as this is exactly the reason

why I joined the list—to ask for a guidance from the crypto community

as the DNSSEC is currently without a solid path ahead.

On Saturday, 16 May 2026 at 05:30:34 UTC+2 Demi Marie Obenour wrote:

On 5/15/26 18:33, Watson Ladd wrote:
> Dear NIST,
>
> It's great to see the third round proposals come out. I would like to
> shed light on some cases where we need very small keys+signature, and
> can afford some CPU time, so SQISign would be of great interest.
>
> One is Roughtime. Recently an RFC, this specification tries to address
> bootstrapping of nodes without real time clocks in a secure way. For
> ecosystem reasons it requires the use of a single signature algorithm
> by all servers, and uses two keys, one a long lasting key, the other
> rotating. It also transmits a very small amount of data, and has
> mechanisms for batching signatures together via Merkel trees. If we
> were to use ML-DSA, we would have a tremendous expansion of the size
> of packets, that would likely force the use of a TCP transport to
> authenticate what is just 64 bits of data. Most protocols don't have
> these rather stringent constraints.
>
> Sincerely,
> Watson

DNSSEC is another case where very small signatures and keys are
important. SQISign level I is smaller than RSA-2048, and SQISign
level V is smaller than RSA-4096. DNSSEC signing can be done offline,
though it is sometimes done online. However, verification performance
might well be a serious problem.

SQISign is unusable for DNSSEC for performance reasons. Unfortunately,

the verification is two magnitudes slower than RSA and ECC. This would

make DNSSEC susceptible to various CPU-exhaustion attacks. Personally,

I wish SQISign was usable, but it really isn't.

DNS is increasingly being transported over TLS, HTTPS, or QUIC for
privacy reasons. Those transports don't have an MTU limit. Therefore,
connection-oriented transports for DNS provide a serious alternative.
This is especially the case for end-user devices, which can maintain
a long-lived connection to a public recursive resolver.

There are couple of misconceptions included here.

1. Although TCP-based transports don't have the MTU limit, there is still hard

limit on the DNS message size—16-bit. This means that there is still limit albeit

a larger limit than MTU.

2. According to my best DNS knowledge, the connection-oriented transport for

DNS is not a serious alternative at all. The resiliency and speed of the DNS

heavily relies on UDP and the current DNS infrastructure would not survive

the complete switch to TCP-based transports. For on-the-wire privacy, DoQ

might be viable alternative, but the core DNS infrastructure is not ready for

anything like this.

I did very rudimentary testing of couple Round 2 ADSS algorithms in my

thesis (and in a paper that's looking for a home :) ) and I am continuing

to work on this topic as part of my job and part of my PhD.

Currently, I am working on testing what would happen if the DNS resolvers

switched to TCP to download the public keys (published as DNSKEY) and

to expand my testing to cover the corner cases – pseudorandom subdomain

attacks, long chains of names, etc...

The TL;DR part is that any PQC algorithm chosen for DNSSEC must be optimized

for the worst. Miscreants regularly use DNS to attack both DNS and other protocols

alike.

Additionally, the requirements for the algorithm suitable for DNSSEC are different

from the general PQC algorithms. The DNSSEC doesn't require confidentiality, its

signatures are generally short-lived, a lot of effort has been put into key rollovers.

This means that we (the DNS community) mostly don't care about long-term storage,

there's no harvest-now decrypt-later attack surface, etc.

Cheers,

Ondrej, ISC

[Patrick Patterson]

Hi all,

PQC Algorithms that work in severely constrained environments is also a topic that I have high interest in. I work with a lot of folks where DTLS with EC-256 keys is already a difficult implementation to make work. The main constraints are:

- Communication link speeds as low as 2400 bps.

- Client devices with very limited processing and memory capability.

- Tens of Thousands of global client endpoints, and thousands of server endpoints, controlled by hundreds of different entities that all have to interop.

- Maximum of a couple of seconds to authenticate and establish the secure link.

- No, symmetric keys don't work - have to use at least some variant of PK for identity management due to the number of organizations involved.

- Short-lived communications sessions, so almost no harvest-now, decrypt later scenario is in play, 

The last point is what will keep this system using EC keys until a CRQC gets to a point of breaking EC in real time.

Longer term, so far, none of the PQC algorithms come even close to being usable under these kinds of conditions, so any work in this area is of high interest.

Patrick.

--
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/c20c222b-6cd6-4712-aae7-c6ad1840fa49n%40list.nist.gov.

--

Personal Mail from Patrick Patterson
No company affiliation

[Demi Marie Obenour]

What is your plan for when a CRQC *is* able to break EC in real time?

--
Sincerely,
Demi Marie Obenour (she/her/hers)

[Patrick Patterson]

Before that happens, I hope that the math folks have found a PQC algorithm that is able to be used given the constraints. And, unfortunately, physics and environment preclude the use of any higher bandwidth links.

[Derek Atkins]

Patrick,

Can you go into more details about why a system like Kerberos wouldn't work?  You say "do to the number of organizations involved", but do you really have a situation where anything can talk to anyone directly without gateways, translators, or other hops?   How many communicating-orgs are we talking about? Nothing against PQC PK, but sometimes a shared-secret-based solution like Kerberos really IS the right solution.

Thanks,

-derek

On Sun, 2026-06-28 at 11:24 -0400, Patrick Patterson wrote:

- No, symmetric keys don't work - have to use at least some variant of PK for identity management due to the number of organizations involved.

-- 

Derek Atkins
Chief Technology Officer

Veridify Security - Securing the Internet of Things®​

Office: 203.227.3151  x1343
Direct: 617.623.3745
Mobile: 617.290.5355
Email: DAt...@Veridify.com

This email message may contain confidential, proprietary and / or legally privileged information and intended only for the use of the intended recipient(s) and others specifically authorized. Any disclosure, dissemination, copying, distribution or use of the information contained in this email message, including any attachments, to or by anyone other than the intended recipient is strictly prohibited.  If you received this in error, please immediately advise the sender by reply email or at the telephone number above, and then delete, shred, or otherwise dispose of this message.

[Brent Kimberley]

Does Kerberos have built-in MFA capabilities out of the box? Let’s not even mention multi channel authentication.

 

From: 'Derek Atkins' via pqc-forum <pqc-...@list.nist.gov>
Sent: June 29, 2026 8:45 AM
To: ppat...@gmail.com; ond...@sury.org
Cc: pqc-...@list.nist.gov; watso...@gmail.com; demio...@gmail.com
Subject: Re: [pqc-forum] Use cases for small signatures and keys

 

⚠️CAUTION: This email is from an external source. Verify sender before opening links and attachments.⚠️

 

--

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/9edbab470e19f1c6013b1fc3fd5a3f42a6a5e912.camel%40Veridify.com.

[Derek Atkins]

MFA: yes.  There are several different pre-auth mechanisms.

Could you please define what you mean by "multi-channel authentication"?

-derek

[Simo Sorce]

Yes, you can use FAST for channel protection and then pre-
authentication with a wide variety of MFA option. One of those options
is PKINIT which allows you to use PKI for those hosts that have enough
b/w and CPU if you prefer.

Kerberos has trust relationships, so you can have multiple entities
control their devices and yet each entity from one side can talk to the
other side, and many other features.

Krb5 is a bit old, so it may be worth starting a new working group for
a modern Key Distribution system approach if there are structural
issues in your scenario. But you should be able to use it as sis in
most cases, the client can be really simple or as complicated as you
want.

Technically krb5 depends on a stable DNS name for certain operations,
but it is all implementation dependent really so alternative naming
systems would work just as well and as easily as long as one peer can
resolve the other peer name (this can easily be KDC assisted to).

Best,
Simo.

On Mon, 2026-06-29 at 13:01 +0000, 'Brent Kimberley' via pqc-forum
wrote:

> Does Kerberos have built-in MFA capabilities out of the box? Let’s not even mention multi channel authentication.
>
> From: 'Derek Atkins' via pqc-forum <pqc-...@list.nist.gov>
> Sent: June 29, 2026 8:45 AM
> To: ppat...@gmail.com; ond...@sury.org
> Cc: pqc-...@list.nist.gov; watso...@gmail.com; demio...@gmail.com
> Subject: Re: [pqc-forum] Use cases for small signatures and keys
>
>
> ⚠️CAUTION: This email is from an external source. Verify sender before opening links and attachments.⚠️
>
> Patrick,
>
> Can you go into more details about why a system like Kerberos wouldn't work? You say "do to the number of organizations involved", but do you really have a situation where anything can talk to anyone directly without gateways, translators, or other hops? How many communicating-orgs are we talking about? Nothing against PQC PK, but sometimes a shared-secret-based solution like Kerberos really IS the right solution.
>
> Thanks,
>
> -derek
>
> On Sun, 2026-06-28 at 11:24 -0400, Patrick Patterson wrote:
> - No, symmetric keys don't work - have to use at least some variant of PK for identity management due to the number of organizations involved.
>
>
> --
> Derek Atkins
> Chief Technology Officer
> Veridify Security - Securing the Internet of Things®​
>
> Office: 203.227.3151 x1343
> Direct: 617.623.3745
> Mobile: 617.290.5355
> Email: DAt...@Veridify.com

> <mailto:DAt...@SecureRF.com>

> This email message may contain confidential, proprietary and / or legally privileged information and intended only for the use of the intended recipient(s) and others specifically authorized. Any disclosure, dissemination, copying, distribution or use of the information contained in this email message, including any attachments, to or by anyone other than the intended recipient is strictly prohibited. If you received this in error, please immediately advise the sender by reply email or at the telephone number above, and then delete, shred, or otherwise dispose of this message.
> --
> 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<mailto:pqc-forum+...@list.nist.gov>.
> To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9edbab470e19f1c6013b1fc3fd5a3f42a6a5e912.camel%40Veridify.com<https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/9edbab470e19f1c6013b1fc3fd5a3f42a6a5e912.camel%40Veridify.com?utm_medium=email&utm_source=footer>.

--
Simo Sorce
Distinguished Engineer
RHEL Crypto Team
Red Hat, Inc

[Brent Kimberley]

We are getting into the realm of Von Neumann vs Harvard architecture.

Von Neumann uses a single, shared memory space for both program instructions and data.

Harvard uses physically separate memory units and buses for instructions and data

 

To my knowledge, Windows NT 3.5 was the last OS which used a multi-channel event queue.  

[Derek Atkins]

Brent,

Let me take a step back and ask you how you would solve your MFA and Multii-channel problems using ECDSA (or ML-DSA)?  I'm asking that, because we're just talking about crypto primitives (and relatively low-level protocol).  I would posit that any MFA or MCA architecture you would build for your PK-based system would also apply to Kerberos.

Thanks!

-derek

[Brent Kimberley]

For a given channel, I would have a minimum of two layers

• An asymmetric plane
• A symmetric plane:
• chacha20 or AES
• decide if SCA/FIA are relevant; and,
• verify key length (Shor’s algorithm.)
• Decide if an RAS/WAS/interlock plane is required

[Derek Atkins]

Brent -- Where's your MFA (Multi-Factor Authentication) solution?  Or even your MCA (separating your code from data)?  I don't see any of that here.

BUT, what I do see here is a solution without stating a problem.  So let me fix that for you:

For a given channel, I would have:

  * a key-distribution layer (so both sides wind up with a shared secret)

  * an authentication layer (so the endpoints can identify cryptographically who they are talking to)

     - This can be single-side or mutual authentication

  * a data encryption layer (so the endpoints can transmit bulk data)

  * At every point we can "decide if SCA/FIA are relevant", verify key lengths, and "decide if an RAS/WAS/interlock plane is required". 

Note that I did NOT specify the TYPE of cryptography in use anywhere here.  Given this architecture, you can clearly plug in an asymmetric + symmetric solution like you proposed.  HOWEVER, you can ALSO plug in a Kerberos-style (symmetric-only) solution, and it fits just as correctly.

Thanks!

-derek

PS: you need to be cognizant of both Shor AND Grover for key lengths.  Shor only applies to RSA, ECC, etc.  But if you have a 64-bits of entropy into ChaCha, Grover will apply.  So you need to check that, too.

[Brent Kimberley]

>> HOWEVER, you can ALSO plug in a Kerberos-style (symmetric-only) solution, and it fits just as correctly.

Affirmative. 

Pre-shared keys work wonders. 

Squirt in the key(s), tag it, slap on some tamper proof tape, a squirt a dab of epoxy, et voila!

               Auditors rejoice everywhere!

                              Until an asset goes walkabout – say the Dever airport parking lot.

[Derek Atkins]

Brent,

You have the exact same issue with an embedded asymmetric private key.

In either case, if you think the device's key is compromised you need to disable the device.  For a PK system you need to use an out-of-band CRL; in a Kerberos-style system you disable the device in the KDC. 

-derek

[Simo Sorce]

On Mon, 2026-06-29 at 15:26 +0000, 'Derek Atkins' via pqc-forum wrote:
> Brent,
>
> You have the exact same issue with an embedded asymmetric private key.
>
> In either case, if you think the device's key is compromised you need to disable the device. For a PK system you need to use an out-of-band CRL; in a Kerberos-style system you disable the device in the KDC.

And from a mgmt pov this is SO MUCH easier. Most devices have a hard
time downloading and managing CRLs (esp given the network speeds in the
premise).

Additionally with kerberos you can actually rotate keys regularly (if
you fancy doing so) straight from the device, so you can deal with
silent (but not persistent) stealing of credentials, and with a
protocol that is much simpler than a full x509 request, even with ACME.

Finally you can use a (properly derived locally) kerberos ticket key as
a PSK for TLS connections, so you can retain most of the well know
stack for secure channel communication and replace only the
authentication part.

[Hugo Vincent]

Hi Patrick & all,

When talking about future-looking crypto standards (such as the on-ramp candidates), remember these things take time (many years to perhaps even decades) to develop, specify, standardize, gain confidence in implementations, and see adoption; and during that time, hardware capabilities change. For the sake of argument, let's assume the rest of your requirements are unmalleable, and that you're willing to risk leaving a PQC migration until a credible CRQC emerges (some time in the 2030s?). If we take this requirement:

> - Client devices with very limited processing and memory capability.

Let's consider SQIsign as an example of something that seemingly meets most of your requirements, except this one. Imagine SQIsign withstands the analysis and succeeds as one of the final standards from the current on-ramp process; perhaps a final standard emerges by 2030. Given you're talking about what sounds like a quite constrained embedded application, perhaps it takes a further 3-4 years until a well optimized embedded implementation emerges and confidence is gained in its implementation security (functional correctness, side channels, etc) and all the other moving pieces you need to make the system work. Now we're imaging a system to be deployed in the mid 2030s. 

Further, let's assume that Moore's Law is alive and well (...) and we continue to see doubling in hardware capability per unit cost every 1.5 years. Now, at the time of deployment (8 years from now), for the same relative cost, hardware will be 2^(8/1.5) -> 40x more capable than today. Using the numbers from PQShield's signature zoo [1], SQIsign level 1 takes ~5.1M cycles to verify, and ECDSA-P256 takes ~106k cycles (~48x faster than SQIsign). SQIsign on hardware 8 years from now (40x more capable -> 128k (5.1M / 40) in 2026-equivalent cycles) might only be 20% slower than ECDSA is on today's comparable hardware. 

This argument hand-waves over a lot of things, and you can certainly dispute many of my assumptions. But on the other hand, over the best part of a decade, we're bound to also see other improvements (novel optimizations, hardware acceleration approaches, etc) to standardized PQC DSAs and KEMs, which are after all still rather new and under-explored. 

Specifying future systems assuming the performance of today's hardware is not a sensible approach when you have compounding exponentials and deployment timescales measured in decades. 

Cheers,

Hugo

[1] https://pqshield.github.io/nist-sigs-zoo/

[D. J. Bernstein]

Patrick Patterson writes:
> - Communication link speeds as low as 2400 bps.

[ ... ]

> - Maximum of a couple of seconds to authenticate and establish the
> secure link.

That doesn't sound like a problem for, e.g., 208-byte high-security
mceliece6688128 ciphertexts on top of 32-byte X25519 ciphertexts (total
240 bytes = 1920 bits). Using a KEM can handle authentication and
encryption simultaneously; are you sure you need signatures? How are the
client and/or server currently authenticated? A pointer to a full system
description might let cryptographic designers optimize things in a way
that meets your constraints.

> - Client devices with very limited processing and memory capability.

Can you say more specifically what CPUs, and what the memory limits are?
https://tches.iacr.org/index.php/TCHES/article/view/8970/8548 reports
7.4 million cycles for mceliece6688128 dec on a Cortex-M4 at 24MHz, and
https://eprint.iacr.org/2025/523 adds 0.4 million cycles for the X25519
part, so about 1/3 second overall for client dec.

---D. J. Bernstein

[Joshua Holden]

Patrick:  I would not place much hope in that.  "Attacks only get better, never worse."  Also, TANSTAAFL.

----Josh

--

[anonymous]

Hello everyone!
When it comes to cryptography, I found an interesting project . This project implements multivariate cryptographic algorithms including UOV and Rainbow(while it has been cryptanalytically broken, I believe the attacks only apply to parameters of specific security levels and do not compromise its overall security).It is well known that MQ is distinguished by short signatures, fast verification speeds, and extremely large public keys. However, this project adopts some patented technologies called as public key indexing technologies ,which drastically reduce the size of the public key of MQ. Attached is its open-source code： https://github.com/abcmint/abcmint
Sincerely,
Kerry

To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/32cc03ae-2ed4-4852-9f9b-66a32650bbc1n%40list.nist.gov.

[Demi Marie Obenour]

I would not be surprised if these devices cannot hold a McEliece public
key, whether in RAM or in nonvolatile storage. Streaming across the
network is out of the question at those speeds.

Something like the Renesas RAOE2 would fall into this category.

[Brent Kimberley]

This thread probably traces back to question 47. https://docs.fcc.gov/public/attachments/FCC-26-38A1.pdf

[Patrick Patterson]

Actually, my queries/comments relate to the ICAO / Civil Aviation transition to ATN-IPS, but I can see how the referenced FCC system could also face some similar constraints.

So - comm speeds as low 2.4kbps over an HF link, 32kbps when over VHF, transmission of time sensitive and potentially safety critical information. And the above commenter was correct - McEliece keys would be size prohibitive for both on-board avionics to handle, and completely infeasible for OTA transmission.

Patrick.

--
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/YT2PR01MB577454D41CD1F5F503770C89FAF72%40YT2PR01MB5774.CANPRD01.PROD.OUTLOOK.COM.

[Demi Marie Obenour]

On 6/30/26 16:59, Patrick Patterson wrote:
> Actually, my queries/comments relate to the ICAO / Civil Aviation
> transition to ATN-IPS, but I can see how the referenced FCC system could
> also face some similar constraints.
>
> So - comm speeds as low 2.4kbps over an HF link, 32kbps when over VHF,
> transmission of time sensitive and potentially safety critical information.
> And the above commenter was correct - McEliece keys would be size
> prohibitive for both on-board avionics to handle, and completely infeasible
> for OTA transmission.

This is going to be a hard problem. A very hard problem.

I agree with Patrick that pure symmetric cryptography is not viable.
Kerberos requires that if A wants to establish a secure session with
B, both A's KDC and B's KDC must be online. In this application, at
least the aircraft's KDC is very likely to be physically distant from
the aircraft and the endpoint it wants to communicate with. Since some
of this information may be safety critical, the connection to this KDC
is thus a safety risk that I suspect cannot be adequately mitigated.

The only recommendations I can think of are:

1. Drop support for HF links unless you can tolerate insecure
transmission. 2.4kbps isn't enough.
2. Use NIST security level I.
3. Use static KEM keys (no forward secrecy).
4. Use BAT as the KEM, which has much smaller public keys (521 bytes)
and ciphertexts (473 bytes).
5. If certificates need to be transmitted, use FN-DSA when the public
key must be transmitted online, and UOV otherwise.
6. Most importantly, hire a team of smart cryptographers to figure
out the best solution. I'm just an amateur!

[D. J. Bernstein]

Demi Marie Obenour writes:
> I would not be surprised if these devices cannot hold a McEliece public
> key, whether in RAM or in nonvolatile storage. Streaming across the
> network is out of the question at those speeds.

I said "client dec"; the small client device's storage is then holding
only the private key, which is 13932 bytes for mceliece6688128, not a
public key.

The communication to set up each client-server session is just a
ciphertext, not a public key; e.g., 208 bytes for mceliece6688128, as I
said.

The client device is provisioned at setup time with the private key by a
trusted device that then spreads knowledge of the public key being
associated with that client. It's also possible to have the client
device generate its own private key and public key, even in highly
limited storage, to avoid having a separate device ever see the private
key; this has more setup-time communication, but the public key would
still never be communicated during a session.

Servers remember client public keys (e.g., keys for 20000 clients would
be 20GB overall). To start a secure session, a server does enc to a
client's public key to establish the session and then switches over to
an authenticated cipher under that session key. The first client
response convinces the server that it's talking to the right client.

There are also many options for cheaply authenticating the server (it's
typically sufficient to use symmetric crypto for that part, in much the
same way that TLS clients can be securely authenticated to servers using
long client passwords rather than client certificates), but details here
would depend on the security model; hence my question about how clients
and/or servers are currently authenticated.

---D. J. Bernstein

[Bo Lin]

One application for signature, which is very common, is "offline" identification. The "offline' here does not mean it is not connected to a network. It means that the device is not online with its owner in real time.

A day-to-day example is our credit cards. A credit card decides a payment does *not* always ask for permission from its issuing bank. It decides by itself. "Tap-and-go" is a typical case. Paying in France with a US bank card is another. 

This kind of applications need a scheme with high-performance, short public key, and short signature is desired.

Payment card application is an example that we are familiar with. There are other applications such as a temporary access system for an organisation in remote area. A device needs to be identified immediately to get ready locally and further processing can be postponed for a while.

For always online services, key size and signature/ciphertext size can be managed one way or another.

Having said that, if we find a scheme which is it deal for offline applications, that's great. Otherwise, we have to adapt because we have to deal with the threat of a cryptographically relevant quantum computer.

--
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/20260701075443.151069.qmail%40cr.yp.to.

[Derek Atkins]

AHA!   We are talking about Broadcast systems -- a requirement that was not presented earlier.

Yes, I, too, agree that Kerberos won't work well for broadcast systems, especially if you require sender authentication*.  This is a reason why requirements need to be stated up front (rather than just saying a technology won't work).  This was only assumed in this thread, not stated.

Demi provides a good list of suggestions for possible solutions.  I would add: can we adjust requirements somewhat?

For example, do we need require sender authentication of broadcasts, or is it okay that we only know that a sender is one of many authorized devices in a given period of time and space?  For example, in an ADB-B deployment do we need to know a broadcast (cryptograpically) came from a specific aircraft, or just that it's from one of the aircraft that is currently authorized to be in the air in a specific airspace?  IFF we don't care about sender authentication then we could use a Kerberos-like system to distribute a broadcast key that gets used for these broadcasts during a specific time / location.  And those keys can be rolled frequently (and acquired pre-emptively).   Of course, this relaxing of the requirements may not be acceptable.

But I agree with Demi, this IS a hard problem.

Thanks,

-derek

* With sender authentication you know that a transmission came from source A vs source B; without it, you know it came from someone who has the current broadcast key (authenticated via a MAC), but you don't know (cryptographically) who sent it.  You can include the claimed source in the message, but there is no crypto to authenticate that.  For /some/ systems, this may be good enough.

[Patrick Patterson]

Hi all,

Thanks for all of the feedback on this - my original intent was to highlight that there are systems that do not appear to have gotten very much thought as to how PQC could work in constrained environments. While I agree that the focus should be on where we get the most "bang for the buck", (i.e.: assume modern processors, memory, and storage, along with relatively high bandwidth communications), I haven't really heard of anyone putting a lot of work into a standardized implementation that will work in applications such as ATN-IPS.

There are some very smart people in the aerospace world that are looking at how we can use approaches such as those already described, but I was hoping to add a voice to those calling for more work on fully standardized PQC systems that will work for constrained use cases.

However, since folks are interested in some more details:

1) The avionics components are using old platforms - I still see some boxes that are based on MIPS and PowerPC, although those are going to be replaced with slightly more modern systems - as I said above, certification times (which can be measured in years), means that the BEST we can hope for are processors and average memory from 10-15 years ago. Storage on the radios will be measurable in MB, Operating systems tend to be one of a handful of certified Real-Time Operating Systems. Ground side systems can be considered to be using modern OS, processor, memory, and storage, and have good connectivity for getting things like OCSP, CRL, etc. in a PKI scenario.

2) The main concern is the inverse of ADS-B - the aircraft needs to authenticate the sender of the message, to ascertain if it is a "good" ground station that is sending information to the aircraft. So think of an airplane from any airline, and any Air Traffic Control center worldwide. The secondary concern is for the ground to auth the aircraft.

3) Aircraft are under strict change control and maintenance, so doing things like provisioning a set of keys based on routes has already been examined, and the decision was made to try very hard to find any other solution, as that would be almost impossible to get working.

4) In the event of a failure to authenticate, one option is to fall back to voice (same thing we've been doing since we started having ATC), but increasing traffic at major hubs means that this is not at all desirable.

Thanks for everyone's comments on this....

[Simo Sorce]

Hi Patrick,
some comments inline.

On Wed, 2026-07-01 at 10:03 -0400, Patrick Patterson wrote:
> Hi all,
>
> Thanks for all of the feedback on this - my original intent was to
> highlight that there are systems that do not appear to have gotten very
> much thought as to how PQC could work in constrained environments. While I
> agree that the focus should be on where we get the most "bang for the
> buck", (i.e.: assume modern processors, memory, and storage, along with
> relatively high bandwidth communications), I haven't really heard of anyone
> putting a lot of work into a standardized implementation that will work in
> applications such as ATN-IPS.
>
> There are some very smart people in the aerospace world that are looking at
> how we can use approaches such as those already described, but I was hoping
> to add a voice to those calling for more work on fully standardized PQC
> systems that will work for constrained use cases.

It'd be really nice to have much smaller signature/key sizes (and also
computationally efficient) and not just for aviation, but sadly it is
very hard to have a secure crypto system that also have key sizes and
ciphertext as small as ECC had... all the proposals with somewhat small
sizes turned up to be broken ... so we are left with sub-optimal sizes
for now.

> However, since folks are interested in some more details:
>
> 1) The avionics components are using old platforms - I still see some boxes
> that are based on MIPS and PowerPC, although those are going to be replaced
> with slightly more modern systems - as I said above, certification times
> (which can be measured in years), means that the BEST we can hope for are
> processors and average memory from 10-15 years ago. Storage on the radios
> will be measurable in MB, Operating systems tend to be one of a handful of
> certified Real-Time Operating Systems. Ground side systems can be
> considered to be using modern OS, processor, memory, and storage, and have
> good connectivity for getting things like OCSP, CRL, etc. in a PKI scenario.

I assume you can always stick multiple CPUs if needed (yes it means
more $$) ?

> 2) The main concern is the inverse of ADS-B - the aircraft needs to
> authenticate the sender of the message, to ascertain if it is a "good"
> ground station that is sending information to the aircraft. So think of an
> airplane from any airline, and any Air Traffic Control center worldwide.
> The secondary concern is for the ground to auth the aircraft.

Do they need to authenticate other aircraft too? (eg for collision
avoidance data?)

> 3) Aircraft are under strict change control and maintenance, so doing
> things like provisioning a set of keys based on routes has already been
> examined, and the decision was made to try very hard to find any other
> solution, as that would be almost impossible to get working.

This fails also because in emergencies you are not necessarily
following the established route and distributing keys to all the
possible alternative grounds in alternate routes becomes hard pretty
fast.

> 4) In the event of a failure to authenticate, one option is to fall back to
> voice (same thing we've been doing since we started having ATC), but
> increasing traffic at major hubs means that this is not at all desirable.

One option could be to consider the data not fully trusted until
confirmed via some checksum code that is generated on both sides and
confirmed by voice. That would be much faster than having the whole
communication via voice, but then again, voice is not necessarily more
trusted ...


Do you have a statement about what is this authentication protecting,
or what are the threats of un-authenticated communication?

Best,
Simo.

[Patrick Patterson]

Comments to your comments:

On Wed, Jul 1, 2026 at 10:40 AM 'Simo Sorce' via pqc-forum <pqc-...@list.nist.gov> wrote:

Hi Patrick,
some comments inline.

On Wed, 2026-07-01 at 10:03 -0400, Patrick Patterson wrote:

> However, since folks are interested in some more details:
>
> 1) The avionics components are using old platforms - I still see some boxes
> that are based on MIPS and PowerPC, although those are going to be replaced
> with slightly more modern systems - as I said above, certification times
> (which can be measured in years), means that the BEST we can hope for are
> processors and average memory from 10-15 years ago. Storage on the radios
> will be measurable in MB, Operating systems tend to be one of a handful of
> certified Real-Time Operating Systems. Ground side systems can be
> considered to be using modern OS, processor, memory, and storage, and have
> good connectivity for getting things like OCSP, CRL, etc. in a PKI scenario.

I assume you can always stick multiple CPUs if needed (yes it means
more $$) ?

Probably not - unless someone has already gone to the effort of certifying a given hardware configuration with more CPUs in them. Any modification of an existing platform is almost always considered a "new" certification, and tends to be avoided unless absolutely necessary.

 

> 2) The main concern is the inverse of ADS-B - the aircraft needs to
> authenticate the sender of the message, to ascertain if it is a "good"
> ground station that is sending information to the aircraft. So think of an
> airplane from any airline, and any Air Traffic Control center worldwide.
> The secondary concern is for the ground to auth the aircraft.

Do they need to authenticate other aircraft too? (eg for collision
avoidance data?)

The ATC radios are separate from the TACAS systems. So those have their own radios (and own identities, unfortunately). 

 

> 3) Aircraft are under strict change control and maintenance, so doing
> things like provisioning a set of keys based on routes has already been
> examined, and the decision was made to try very hard to find any other
> solution, as that would be almost impossible to get working.

This fails also because in emergencies you are not necessarily
following the established route and distributing keys to all the
possible alternative grounds in alternate routes becomes hard pretty
fast.

Amongst a host of other operational concerns, yes. 

 

> 4) In the event of a failure to authenticate, one option is to fall back to
> voice (same thing we've been doing since we started having ATC), but
> increasing traffic at major hubs means that this is not at all desirable.

One option could be to consider the data not fully trusted until
confirmed via some checksum code that is generated on both sides and
confirmed by voice. That would be much faster than having the whole
communication via voice, but then again, voice is not necessarily more
trusted ...

The entire idea behind ATN-IPS is to keep voice comms to a minimum (and eliminate them entirely if possible, except in emergencies). So having any "human in the loop" is against the design principles. Also, when you have a cyclinder moving through the air at 800+ km/h, and they receive a transmission to change altitude, the assumption is that they will do it very quickly, not call up ATC and ask for a Checksum before complying with the instruction.

 

Do you have a statement about what is this authentication protecting,
or what are the threats of un-authenticated communication?

The goal is to authenticate using modern IP based systems ATC<->Aircraft messages, and Operator<->Aircraft messages to at least the same level as currently - since this is broadcast, and everyone on the frequency can hear the voice comms, it's very easy today to catch any interloper who thinks they are being funny by broadcasting fake ground or aircraft messages. Once this moves fully to digital comms, the assurance must be the same.

[Demi Marie Obenour]

On 7/1/26 10:03, Patrick Patterson wrote:
> Hi all,
>
> Thanks for all of the feedback on this - my original intent was to
> highlight that there are systems that do not appear to have gotten very
> much thought as to how PQC could work in constrained environments. While I
> agree that the focus should be on where we get the most "bang for the
> buck", (i.e.: assume modern processors, memory, and storage, along with
> relatively high bandwidth communications), I haven't really heard of anyone
> putting a lot of work into a standardized implementation that will work in
> applications such as ATN-IPS.
>
> There are some very smart people in the aerospace world that are looking at
> how we can use approaches such as those already described, but I was hoping
> to add a voice to those calling for more work on fully standardized PQC
> systems that will work for constrained use cases.

Is this something that ICAO could hire a team of cryptographers for?
I expect that civil aviation has a sufficient budget for this to be
feasible, and a bespoke protocol is likely necessary.

> However, since folks are interested in some more details:
>
> 1) The avionics components are using old platforms - I still see some boxes
> that are based on MIPS and PowerPC, although those are going to be replaced
> with slightly more modern systems - as I said above, certification times
> (which can be measured in years), means that the BEST we can hope for are
> processors and average memory from 10-15 years ago. Storage on the radios
> will be measurable in MB, Operating systems tend to be one of a handful of
> certified Real-Time Operating Systems.


> Ground side systems can be
> considered to be using modern OS, processor, memory, and storage, and have

> good connectivity for getting things like OCSP, CRL, etc. in a PKI scenario.x

> 2) The main concern is the inverse of ADS-B - the aircraft needs to
> authenticate the sender of the message, to ascertain if it is a "good"
> ground station that is sending information to the aircraft. So think of an
> airplane from any airline, and any Air Traffic Control center worldwide.
> The secondary concern is for the ground to auth the aircraft.
>
> 3) Aircraft are under strict change control and maintenance, so doing
> things like provisioning a set of keys based on routes has already been
> examined, and the decision was made to try very hard to find any other
> solution, as that would be almost impossible to get working.
>
> 4) In the event of a failure to authenticate, one option is to fall back to
> voice (same thing we've been doing since we started having ATC), but
> increasing traffic at major hubs means that this is not at all desirable.
>
> Thanks for everyone's comments on this....

Is the following a reasonably accurate description?

- Confidentiality of the transmitted traffic is not important.
This means that forward secrecy is not required.
- Integrity of the traffic *is* important.
- The link is a short-range wireless link with negligible latency
(significantly less than 0.1 seconds) but very limited bandwidth.
- Because of the low latency, multiple round-trips are acceptable.
- There is some overhead for forward error correction (FEC).
- Each ground station will have a certificate issued by the local CAA.
- The number of CAAs is very small (less than 250). Therefore:
- The radio can *definitely* hold a list of CAA public key hashes.
This takes 32 * 250 = 8000 bytes.
- The radio *may* be able to hold a list of CAA public keys. For
Falcon-512, this takes 897 * 250 = 224250 bytes.
- The ground station *definitely* can hold all of the CAA public keys,
even for UOV.
- The ground station can be periodically updated with new PKI information,
but it should not need connectivity when setting up a connection.
- The ground station *might* be able to hold a Classic McEliece key for
every single radio (~1MiB * few million aircraft = few TiB).
This makes authenticating the radio much simpler, as the radio only
- Bespoke certificate formats are acceptable. It's not necessary to use
X.509.
- There is no need for security beyond NIST level I.
- Patents are not a major concern. The cost of licensing is negligible
compared to the cost of the aircraft or ground station.
- The use of algorithms with less conservative assumptions is acceptable.
It is not necessary to use a standardized algorithm.
- If the aircraft needs to generate a key, this can be done as a
low-priority background task before a connection must be established.
- Isogeny-based cryptography is too slow, even for the ground station.
- Algorithms must be guaranteed to complete promptly. Algorithms that
require too many retries are not acceptable.

>> Veridify Security - *Securing the Internet of Things®*​

>>
>> Office: 203.227.3151 x1343
>> Direct: 617.623.3745
>> Mobile: 617.290.5355
>> Email: DAt...@Veridify.com

>> <DAt...@SecureRF.com>
>> *This email message may contain confidential, proprietary and / or legally

>> privileged information and intended only for the use of the intended
>> recipient(s) and others specifically authorized. Any disclosure,
>> dissemination, copying, distribution or use of the information contained in
>> this email message, including any attachments, to or by anyone other than
>> the intended recipient is strictly prohibited. If you received this in
>> error, please immediately advise the sender by reply email or at the
>> telephone number above, and then delete, shred, or otherwise dispose of

>> this message.*

[conduition]

Hi list,

I would also like to add to the list of use-cases, decentralized cryptocurrencies.

Blockchain software typically requires at least some subset of nodes capable of storing a very large archive of past transactions, so that new nodes can bootstrap and verify the latest state of the network. This archive grows with each new block added to the chain, and each block contains hundreds or thousands of transactions, each containing one or more digital signatures.

Currently the Bitcoin blockchain requires ~900gb of storage (on my machine at least), and it grows every day as more blocks are mined.

This size is a severe limiting factor which constricts how many users can run a full archival node. To incentivize compactness and reduce space waste, transaction fees are typically priced by the number of bytes in a transaction. However, signature verification compute cost must also be accounted for, and this is typically done by limiting the number of signature verifications allowed per transaction or per block to below some sane ceiling.

To date there exists no signature scheme which permits both the fast verification and compact sizes required by blockchains, with the possible exception of stateful schemes like XMSS. My peers and I are working on a proposal to integrate semi-stateful signature schemes into Bitcoin, backed by SLH-DSA as a less-efficient stateless fallback, but we view this as a stopgap measure. Long-term we would all be very much more interested in a stateless scheme that can achieve fast verification and compact keys/signatures.

Many users and developers I know are interested in SQIsign particularly due to its key rerandomization feature [1] (a common necessity for Bitcoin), but the slow verification performance of SQIsign makes it unsuitable for now.

regards,
conduition

[1]: https://eprint.iacr.org/2026/1169

On Friday, May 15th, 2026 at 9:30 PM, Demi Marie Obenour <demio...@gmail.com> wrote:

> On 5/15/26 18:33, Watson Ladd wrote:
> > Dear NIST,
> >
> > It's great to see the third round proposals come out. I would like to
> > shed light on some cases where we need very small keys+signature, and
> > can afford some CPU time, so SQISign would be of great interest.
> >
> > One is Roughtime. Recently an RFC, this specification tries to address
> > bootstrapping of nodes without real time clocks in a secure way. For
> > ecosystem reasons it requires the use of a single signature algorithm
> > by all servers, and uses two keys, one a long lasting key, the other
> > rotating. It also transmits a very small amount of data, and has
> > mechanisms for batching signatures together via Merkel trees. If we
> > were to use ML-DSA, we would have a tremendous expansion of the size
> > of packets, that would likely force the use of a TCP transport to
> > authenticate what is just 64 bits of data. Most protocols don't have
> > these rather stringent constraints.
> >
> > Sincerely,
> > Watson
>

> DNSSEC is another case where very small signatures and keys are
> important. SQISign level I is smaller than RSA-2048, and SQISign
> level V is smaller than RSA-4096. DNSSEC signing can be done offline,
> though it is sometimes done online. However, verification performance
> might well be a serious problem.
>

> DNS is increasingly being transported over TLS, HTTPS, or QUIC for
> privacy reasons. Those transports don't have an MTU limit. Therefore,
> connection-oriented transports for DNS provide a serious alternative.
> This is especially the case for end-user devices, which can maintain
> a long-lived connection to a public recursive resolver.

> --
> Sincerely,
> Demi Marie Obenour (she/her/hers)
>

> --

> 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/388884ab-ca26-4f2d-86b6-d43ad5c442ed%40gmail.com.
>

[Patrick Patterson]

See replies inline below...

On Wed, Jul 1, 2026 at 12:53 PM Demi Marie Obenour <demio...@gmail.com> wrote:

On 7/1/26 10:03, Patrick Patterson wrote:
> Hi all,
>
> Thanks for all of the feedback on this - my original intent was to
> highlight that there are systems that do not appear to have gotten very
> much thought as to how PQC could work in constrained environments. While I
> agree that the focus should be on where we get the most "bang for the
> buck", (i.e.: assume modern processors, memory, and storage, along with
> relatively high bandwidth communications), I haven't really heard of anyone
> putting a lot of work into a standardized implementation that will work in
> applications such as ATN-IPS.
>
> There are some very smart people in the aerospace world that are looking at
> how we can use approaches such as those already described, but I was hoping
> to add a voice to those calling for more work on fully standardized PQC
> systems that will work for constrained use cases.

Is this something that ICAO could hire a team of cryptographers for?
I expect that civil aviation has a sufficient budget for this to be
feasible, and a bespoke protocol is likely necessary.

There are folks that are working on this, and, as I said, my intent was to highlight a real-life use case for the need for PQC algorithms that take into account the real-world limits that may be in place when we have to replace EC-DSA256. I wasn't looking for everyone to come up with the solution, although this is a fun thread to participate in.

Also, the industry has been using bespoke protocols for many years, and the entire idea of ATN-IPS is to stop doing that if possible and use IPv6, DTLS, and standard PKI (although we do cheat a bit for the certs), or an equivalent fully distributable, non-centralized, and standardized trusted identity scheme.

> However, since folks are interested in some more details:
>
> 1) The avionics components are using old platforms - I still see some boxes
> that are based on MIPS and PowerPC, although those are going to be replaced
> with slightly more modern systems - as I said above, certification times
> (which can be measured in years), means that the BEST we can hope for are
> processors and average memory from 10-15 years ago. Storage on the radios
> will be measurable in MB, Operating systems tend to be one of a handful of
> certified Real-Time Operating Systems.

Is the following a reasonably accurate description?

- Confidentiality of the transmitted traffic is not important.
  This means that forward secrecy is not required.

Correct. ATC messages are, by definition, public.

 

- Integrity of the traffic *is* important.

Correct.

 

- The link is a short-range wireless link with negligible latency
  (significantly less than 0.1 seconds) but very limited bandwidth.

Incorrect - the ground can be in Canada, and the aircraft can be somewhere over the Atlantic, for instance. Or we may need to make a round trip to Geo-Sync Orbit, but we can have higher bandwidth there - it's just orders of magnitude more expensive.

 

- Because of the low latency, multiple round-trips are acceptable.
- There is some overhead for forward error correction (FEC).
- Each ground station will have a certificate issued by the local CAA.

 

Maybe - depends on the state, and their model - this could be a mix of state CAA, Private or Semi-private Air Navigation Service Providers, or other service providers... So this can't be an assumption.

 

- The number of CAAs is very small (less than 250). Therefore:
  - The radio can *definitely* hold a list of CAA public key hashes.
    This takes 32 * 250 = 8000 bytes.
  - The radio *may* be able to hold a list of CAA public keys.  For
    Falcon-512, this takes 897 * 250 = 224250 bytes.
  - The ground station *definitely* can hold all of the CAA public keys,
    even for UOV.
- The ground station can be periodically updated with new PKI information,
  but it should not need connectivity when setting up a connection.
- The ground station *might* be able to hold a Classic McEliece key for
  every single radio (~1MiB * few million aircraft = few TiB).
  This makes authenticating the radio much simpler, as the radio only

Provisioning and de-provisioning keys to the aircraft is a problem - if you have a fleet of 1000 aircraft, and each aircraft is at one of a handful of maintenance facilities where they can securely provision keys only once every 2-3 years, and not all aircraft are in at the same time, and a host of other factors (not to mention how to handle in-op radios being replaced, etc.), having anything other than a static ID on the aircraft, and somehow getting the ground ID to the aircraft at communication time is not really workable.

 

- Bespoke certificate formats are acceptable.  It's not necessary to use
  X.509.

 

We're trying to use as close to standard X.509 as possible, with a few cheats along the way to reduce over the air transmission sizes.

 - There is no need for security beyond NIST level I.

That is going to be up to each State to decide.

- Patents are not a major concern.  The cost of licensing is negligible
  compared to the cost of the aircraft or ground station.

I am not an ICAO representative, but I believe that standardizing proprietary implementations without FAND in place is generally frowned upon.

 

- The use of algorithms with less conservative assumptions is acceptable.
  It is not necessary to use a standardized algorithm.

Again - the industry has been using non-standard ways of doing things for years, and is looking to stop doing that wherever possible.

 

- If the aircraft needs to generate a key, this can be done as a
  low-priority background task before a connection must be established.

Identity Key generation will probably be restricted to "on the ground, in a secure maintenance facility", due to regulatory and certification requirements.

 

- Isogeny-based cryptography is too slow, even for the ground station.
- Algorithms must be guaranteed to complete promptly.  Algorithms that
  require too many retries are not acceptable.

I'll re-iterate what I said above - I am bringing this topic up to highlight a need for standardized PQC that is workable in highly constrained environments. The aerospace industry might be unique for a commercial environment with the level of regulation and certification that it requires, but there are going to be (if not already are) other environments with IoT implications that have similar constraints.

[Derek Atkins]

Hi,

On Wed, 2026-07-01 at 14:13 -0400, Patrick Patterson wrote:

We're trying to use as close to standard X.509 as possible, with a few cheats along the way to reduce over the air transmission sizes.

This is very off-topic for the PQC list, but I would HIGHLY recommend you look at C509 in lieu of X509.  It's a CBOR-encoding of certificates that is semantically equivalent to X509, but it's probably 1/3 the size.

-derek

-- 

Derek Atkins
Chief Technology Officer

Veridify Security - Securing the Internet of Things®​

Office: 203.227.3151  x1343
Direct: 617.623.3745
Mobile: 617.290.5355
Email: DAt...@Veridify.com

[Blumenthal, Uri - 0553 - MITLL]

>> We're trying to use as close to standard X.509 as possible, with a few cheats along the way to reduce over the air transmission sizes.

> 

> This is very off-topic for the PQC list, but I would HIGHLY recommend you look 

> at C509 in lieu of X509.  It's a CBOR-encoding of certificates that is semantically

> equivalent to X509, but it's probably 1/3 the size.

Considering that the lion’s share of the PQ certificate is taken by the PQ signature and the PQ public key — the savings from changing a format would likely be fairly small. I’d expect 30-35% reduction, not reducing to 33% of the total X509 size.

If your opinion differs — please show the numbers you’d expect for X509 => C509 for, e.g., ML-DSA-87 pub key and signature. 

Here’s what Google thinks (and it makes sense to me):

Because the ML-DSA-87 signature and public key are mathematically fixed at large sizes (\(\sim \)7.2 KB combined), format optimizations cannot shrink the raw cryptographic data. However, C509 achieves its 35% overall reduction by virtually eliminating the ASN.1 framing overhead, compressing metadata by 75%, and optimizing how the massive PQ data blocks are containerized.