ALGORITHM ENGINEERING

Why replacing an elliptic curve is a protocol and systems problem.

The first post-quantum standards are ready to implement. NIST published ML-KEM for key establishment and ML-DSA and SLH-DSA for digital signatures in 2024. The cryptographic question is no longer only which candidates may survive standardisation.

The engineering question is where they fit.

In a server environment, larger keys and signatures may be absorbed by existing networks and memory budgets. At the edge, the same change can cross boundaries that shaped the original system: one QR code, one NFC exchange, one APDU, a fixed record, a small secure element, a validator response time or a firmware image that already fills available flash.

Post-quantum migration changes more than the primitive. It changes the geometry of the protocol.

The first visible cost is size

Elliptic-curve systems made compact public-key cryptography normal. Post-quantum constructions often use much larger public values and outputs.

The standard parameter sets illustrate the change:

Algorithm

Public key

Ciphertext or signature

Function

ML-KEM-512

800 bytes

768-byte ciphertext

Key establishment

ML-KEM-768

1,184 bytes

1,088-byte ciphertext

Key establishment

ML-KEM-1024

1,568 bytes

1,568-byte ciphertext

Key establishment

ML-DSA-44

1,312 bytes

2,420-byte signature

Digital signature

ML-DSA-65

1,952 bytes

3,309-byte signature

Digital signature

ML-DSA-87

2,592 bytes

4,627-byte signature

Digital signature

These are only the cryptographic objects. A deployed message also carries protocol headers, algorithm identifiers, key identifiers, certificates, payloads and transport framing.

A 2,420-byte signature may be acceptable on an IP connection and still dominate a QR payload or require several exchanges over a proximity channel. A certificate chain built around larger public keys and signatures can grow more than the end-entity object alone suggests.

The correct unit of analysis is therefore the complete transaction, not the algorithm output in isolation.

KEMs and signatures solve different problems

ML-KEM establishes a shared secret. ML-DSA and SLH-DSA authenticate signed data. They are not interchangeable replacements for a generic "public-key algorithm."

An existing elliptic-curve key may currently be used for signing, key agreement or both. A post-quantum design may need distinct keys and protocol paths for those purposes. That affects provisioning, certificates, identifiers and secure storage.

Key establishment can sometimes tolerate a larger initial exchange because the derived symmetric key protects many later messages. Signatures may appear on every offline credential, firmware package or transaction. The dominant cost depends on the system's message pattern.

Before selecting a parameter set, the design must state which cryptographic property is being replaced and how often the corresponding object moves through the system.

Transport limits become protocol decisions

Edge protocols inherit limits from physical and logical carriers.

QR

A QR code has a finite capacity that falls as error correction increases. Dense codes are harder to scan on small or damaged displays. Adding a post-quantum signature can force a larger symbol, a lower error-correction level, a segmented presentation or a change in what the code carries.

The right comparison includes the final encoded form. Base64 or base45 expands binary data. CBOR can reduce structural overhead, but it cannot make a multi-kilobyte signature disappear.

One architectural response is to place only a session invitation or reference in the QR code and complete authentication over another channel. That changes offline behaviour and privacy assumptions, so it is not a free optimisation.

NFC and smart-card commands

Contactless exchanges are sensitive to framing, round trips and field stability. A cryptographic object that does not fit in one command must be chained or fragmented. Each additional exchange creates state, timeout and error-handling requirements.

If the secure element performs the operation internally, its command interface still has to accept inputs and return outputs. Existing APDU profiles, buffer sizes and middleware may encode assumptions inherited from RSA or elliptic curves.

Bluetooth and constrained links

Larger handshake messages can exceed a link-layer payload and trigger fragmentation. Packet loss then affects more fragments, and retransmission increases latency and energy use. A benchmark on a reliable local socket does not reveal this behaviour.

Protocol traces from the intended carrier are more informative than an isolated operations-per-second figure.

Memory is not one number

An implementation may advertise a small key size while requiring substantially more working memory during generation, signing, encapsulation or decapsulation.

Edge evaluation should separate:

• persistent storage for keys and trust material;
• flash occupied by code and constant tables;
• stack use;
• heap use and allocation patterns;
• temporary buffers for encoded messages;
• peak memory during the cryptographic operation;
• memory required by the surrounding protocol parser.

Peak memory matters most. Two components that each fit independently may fail when message decoding, certificate validation and cryptographic computation overlap.

Constant-time and side-channel-resistant implementations can also have different memory and performance characteristics from reference code. Measurements should use the implementation intended for deployment, with its protections enabled.

Latency belongs to the user interaction

A raw benchmark might report key generation, encapsulation, signing or verification time. A field system experiences a sequence:

1. wake or activate the device;
2. negotiate the transport;
3. transfer keys and messages;
4. parse the structures;
5. perform cryptographic operations;
6. evaluate certificates and policy;
7. return a result;
8. record the transaction.

If a validator must respond while a person passes through a gate, the relevant metric is end-to-end decision time and its worst-case distribution. A faster primitive with a much larger message may lose its advantage over a slow link. A compact algorithm with difficult implementation characteristics may create other costs.

Benchmarks should report median and tail latency, not only an average. They should include cold starts, fragmented messages, invalid inputs and retries.

Hybrid operation multiplies structures

During transition, systems may combine a classical and a post-quantum mechanism. Hybrid key establishment can derive a final secret from both contributions. Composite or dual signatures can protect an artifact under more than one assumption.

This can reduce reliance on a single new construction during an adoption period. It also carries both costs.

Messages contain additional keys, ciphertexts or signatures. The protocol must define how results are combined, which failures are fatal and whether an intermediary can remove one component. Certificates and algorithm identifiers need unambiguous profiles. Implementations must avoid accepting the hybrid object as valid when only the weaker component was actually checked.

At the edge, hybrid migration may be the largest format the system will ever need to carry. Designing only for the expected final algorithm can leave no path through the transition.

Secure hardware may decide the schedule

Keys at the edge often live in HSMs, SAMs, secure elements, smart cards or platform-backed keystores. Their supported algorithms, object models and command sets determine what can be deployed.

Questions include:

• Does the device implement the selected standard and parameter set?
• Can its random-number generator support the required operations?
• Is there enough protected storage for the private material?
• Can keys be generated internally, or must they be imported?
• Can the command interface carry the necessary objects?
• Are firmware and applet updates possible after issuance?
• What side-channel protections have been evaluated?
• What happens to devices that cannot be upgraded?

Software emulation can prove protocol logic but cannot answer all of these questions. The migration schedule may ultimately be constrained by silicon availability, certification, personalisation capacity and field replacement.

Benchmark the protocol envelope

A useful edge benchmark records more than primitive timing.

For each candidate construction, measure:

The test matrix should include the weakest realistic device and the least favourable supported carrier. A desktop benchmark is useful for comparison, but it is not an edge deployment result.

Architecture can absorb some of the cost

Not every component has to perform every post-quantum operation.

A design can separate long-lived issuer signatures from short-lived session authentication, cache validated public material, keep large certificate chains out of repeated exchanges or move a bootstrap value through the constrained channel and continue over a higher-capacity link.

These choices redistribute trust and connectivity requirements. Moving verification to a server may simplify an edge device while eliminating offline operation. Preloading keys may reduce transaction size while increasing provisioning complexity. Caching improves latency but introduces freshness and invalidation rules.

The best result is not necessarily the smallest message or fastest primitive. It is an architecture whose compromises are explicit and whose security properties survive the operational environment.

Migration begins with measurements

Post-quantum standards provide algorithms and parameter sets. They do not determine whether a credential fits in a code, whether a reader can carry the signature, whether a secure element can store the key or whether a field transaction completes on time.

Those are implementation questions, but they are not secondary. If the environment cannot carry the cryptographic construction reliably, the intended security property is not deployable.

At the edge, the cost of post-quantum migration is measured in bytes, buffers, round trips, update paths and human waiting time. The useful design begins by making each of them visible.

References

1. NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard
2. NIST FIPS 204: Module-Lattice-Based Digital Signature Standard
3. NIST FIPS 205: Stateless Hash-Based Digital Signature Standard
4. NIST Post-Quantum Cryptography Project
5. NIST SP 800-227: Recommendations for Key-Encapsulation Mechanisms
6. NIST NCCoE: Migration to Post-Quantum Cryptography
7. Open Quantum Safe