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

--