PQ Key Sizes: What Infrastructure Teams Must Know

Post-quantum cryptography is not a theory exercise anymore. NIST finalized the first three PQ standards in August 2024: ML-KEM (FIPS 203) for key encapsulation, ML-DSA (FIPS 204) for digital signatures, and SLH-DSA (FIPS 205) for stateless hash-based signatures. FALCON was standardized as FN-DSA in early 2025. Federal agencies have a 2035 mandate to migrate. Most cloud providers and browser vendors have already begun integrating PQ algorithms into their TLS stacks.

The cryptographic migration is well-documented. What is not well-documented is the infrastructure impact. Post-quantum keys and signatures are dramatically larger than their classical counterparts. An RSA-2048 public key is 256 bytes. An ML-KEM-1024 public key is 1,568 bytes. An ECDSA-P256 signature is 64 bytes. An ML-DSA-65 signature is 3,309 bytes. An SLH-DSA-SHA2-256f signature is 49,856 bytes. These are not incremental increases. They are 6x to 780x increases in the size of cryptographic material that your infrastructure stores, caches, transmits, and verifies millions of times per day.

This post is the reference for infrastructure teams. Not cryptographic theory -- infrastructure impact. The exact byte sizes for every NIST PQ algorithm versus its classical equivalent, the math for five infrastructure components at three scales, and the cache architecture decision that determines whether PQ migration breaks your system or strengthens it.

The Size Comparison Table

This table lists every NIST-standardized post-quantum algorithm alongside its closest classical equivalent. Sizes are exact, taken from the NIST standards documents. The "Multiplier" column shows how many times larger the PQ artifact is compared to its classical counterpart.

Three patterns emerge. First, lattice-based signatures (ML-DSA, FN-DSA) have large keys and large signatures, but the sizes are manageable -- single-digit kilobytes. Second, hash-based signatures (SLH-DSA) have small keys but enormous signatures -- 17 KB to 49 KB. Third, key encapsulation (ML-KEM) has the most reasonable size increase -- 800 to 1,568 bytes for public keys, which is large compared to ECDH but small compared to signature schemes.

Infrastructure Component 1: Session Stores

A session store holds authentication state for active users. Each session entry typically contains a session ID, user ID, authentication timestamp, expiration timestamp, and the cryptographic material used to authenticate the session -- either a signature that proves the session was issued by a trusted authority, or a public key for client certificate authentication.

With classical cryptography, a session entry containing an ECDSA-P256 signature and public key is approximately 96 bytes of cryptographic material (64-byte signature + 32-byte key hash or 64-byte compressed public key). The total session entry, including metadata, is approximately 200 bytes. With PQ signatures using ML-DSA-65, the same session entry contains 3,309 bytes of signature and 1,952 bytes of public key -- 5,261 bytes of cryptographic material. The total session entry becomes approximately 5,400 bytes.

That is a 27x increase per session entry. At scale, this is the difference between an infrastructure that fits in a small cache and one that requires redesign.

At 100,000 sessions, the PQ session store fits in a single r7g.xlarge ElastiCache node (26 GB). At 1 million sessions, you need multiple nodes or a larger instance type. At 10 million sessions, you need a dedicated cluster with significant memory, and the cross-AZ data transfer for session lookups becomes a material cost driver because each session lookup now transfers 5.4 KB instead of 200 bytes.

The session store is the infrastructure component most impacted by PQ migration because sessions are read frequently (every authenticated request), the cryptographic material must be present in the session entry for verification, and the number of concurrent sessions scales directly with your user base. A SaaS application with 10 million active sessions that migrates from ECDSA to ML-DSA-65 will see its session store grow from 1.9 GB to 51.5 GB overnight.

Infrastructure Component 2: TLS Session Tickets

TLS session tickets allow clients to resume a TLS session without performing a full handshake. The ticket contains the session state, including the negotiated cipher suite, the session key material, and the server's certificate chain. With classical TLS 1.3, a session ticket is typically 200-300 bytes. The cryptographic contribution is modest: a 32-byte session key, a 64-byte signature, and some metadata.

With PQ TLS (hybrid mode, which is the deployment model recommended by NIST and implemented by most browsers), a session ticket includes both classical and PQ key material. The PQ contribution adds ML-KEM-768 ephemeral public keys (1,184 bytes) and ML-DSA-65 signature fragments (3,309 bytes) to the ticket. The total TLS session ticket grows from approximately 256 bytes to approximately 1,344 bytes -- a 5.25x increase.

TLS session ticket caches are typically implemented as in-memory stores on the TLS termination layer (load balancers, reverse proxies, or application servers). A load balancer caching 500,000 TLS session tickets with classical cryptography uses approximately 128 MB. With PQ hybrid tickets, the same cache requires 672 MB. This is still manageable on modern hardware, but it changes the capacity planning for your TLS termination tier.

The larger concern is not the cache size but the ticket transmission size. Every TLS resumption sends the full ticket from the client to the server. At 1,344 bytes per ticket, a server handling 50,000 TLS resumptions per second receives 67 MB/sec of session ticket data alone. This consumes NIC bandwidth and increases the baseline network load on your TLS termination tier.

Infrastructure Component 3: JWT Verification Caches

JSON Web Tokens (JWTs) are self-contained authentication tokens that include a header, a payload, and a signature. The signature is the largest component when using PQ algorithms. A JWT signed with ECDSA-P256 has a 64-byte signature, making the total JWT typically 300-500 bytes depending on the payload. A JWT signed with ML-DSA-65 has a 3,309-byte signature, making the total JWT 3,600-3,800 bytes.

JWT verification caches store the verification result of recently seen tokens to avoid re-verifying the signature on every request. The cache entry is typically the JWT's jti (JWT ID) as the key and the verification result plus decoded claims as the value. With classical JWTs, the value is small (200-300 bytes for decoded claims). With PQ JWTs, teams often cache the full token alongside the decoded claims to support token forwarding to downstream services. This increases the cache entry from approximately 500 bytes to approximately 4,000 bytes.

The 8x increase per cache entry is more moderate than the session store impact because the JWT payload (not just the signature) contributes to the baseline size. But the absolute numbers are still significant. A service that currently caches 1 million JWTs in 477 MB will need 3.8 GB after PQ migration. If that cache is on ElastiCache, the instance cost roughly doubles (from a single r7g.large to a r7g.xlarge or two r7g.large nodes). If the cache is in-process, the application's memory footprint grows by 3.3 GB per instance.

The more subtle impact is on JWT verification performance. ML-DSA-65 verification takes approximately 150 microseconds on server hardware, compared to approximately 15 microseconds for ECDSA-P256. This makes JWT verification caching ten times more valuable than it was with classical algorithms. The cost of a cache miss is 10x higher, so the savings from a cache hit are 10x greater. Teams that skipped JWT verification caching because ECDSA was "fast enough" will need to add caching after PQ migration to avoid a 10x increase in verification CPU.

Infrastructure Component 4: Certificate Chains

A TLS certificate chain typically contains three certificates: an end-entity certificate, an intermediate CA certificate, and a root CA certificate (often omitted because clients already have it). With classical RSA-2048 or ECDSA-P256, a certificate is approximately 700-1,200 bytes. A full chain is approximately 2-3.5 KB.

With PQ certificates, the size depends heavily on the signature algorithm. ML-DSA-65 certificates are approximately 5-7 KB each (1,952-byte public key + 3,309-byte signature + certificate metadata). A full chain of three ML-DSA-65 certificates is approximately 15-21 KB. SLH-DSA certificates are much larger: an SLH-DSA-SHA2-128f certificate is approximately 18-20 KB (32-byte public key + 17,088-byte signature + metadata). A full chain of three SLH-DSA-SHA2-128f certificates is approximately 54-60 KB. SLH-DSA-SHA2-256f chains reach 150 KB or more.

During the transition period, many deployments will use hybrid certificates that include both classical and PQ signatures. This further increases the chain size. A hybrid chain with ECDSA + ML-DSA-65 certificates is approximately 18-25 KB. A hybrid chain with ECDSA + SLH-DSA-SHA2-128f certificates is approximately 56-65 KB.

Certificate chain caches on reverse proxies and load balancers are affected proportionally. More importantly, the TLS handshake itself is affected. A classical TLS 1.3 handshake sends approximately 4-5 KB of data. A PQ hybrid handshake with ML-DSA-65 certificates sends approximately 20-30 KB. This increases TLS handshake latency, especially on high-latency connections (mobile, satellite, international). It also increases the rate of TCP packet retransmissions because larger handshakes are more likely to exceed the TCP initial congestion window (typically 10 segments, or about 14 KB).

Infrastructure Component 5: API Credential Caches

API credentials -- API keys, service-to-service tokens, mTLS client certificates -- are cached at API gateways and service mesh proxies for fast authentication. A classical API credential cache entry contains a key hash (32 bytes), an ECDSA public key or certificate (64-700 bytes), access control metadata (100-200 bytes), and a TTL. The total entry is approximately 300-900 bytes.

With PQ API credentials, the entry grows significantly. An ML-KEM-1024 public key for key agreement is 1,568 bytes. An ML-DSA-65 public key for signature verification is 1,952 bytes. A hybrid credential containing both classical and PQ keys is 2,016-2,616 bytes of key material alone. Adding metadata and access control, the total entry is approximately 2,500-3,500 bytes -- a 4-10x increase over classical entries.

API gateways that cache 50,000 active credentials see their cache grow from approximately 45 MB (classical) to approximately 175 MB (PQ hybrid). This is manageable per-instance, but the aggregate impact across a fleet of 20 gateway instances is a 2.6 GB increase in total memory consumption. For organizations running API gateways on memory-constrained instances (t3.medium, t3.large), this may require an instance type upgrade.

The more significant impact is on credential cache throughput. When API credentials are cached on a network cache (ElastiCache, Memcached), every authentication lookup transfers the credential over the network. A 300-byte classical credential generates negligible network load. A 3,500-byte PQ credential generates 10x the network load per lookup. At 100,000 credential lookups per second on a network cache, the data transfer increases from approximately 30 MB/sec to 350 MB/sec. This can saturate the NIC on smaller ElastiCache instances and introduces measurable latency variance.

The Cache Architecture Decision

The size increases from PQ cryptography create a forcing function on cache architecture. With classical key sizes, network caches (ElastiCache, Redis, Memcached) worked well for all five infrastructure components described above. The values were small (64-900 bytes), the network overhead per lookup was negligible, and even large-scale deployments fit within modest cache clusters.

With PQ key sizes, network caches degrade. The degradation is linear with value size, and PQ values are 8-52x larger than classical values. Here is how the key metrics change.

The last row is the critical one. A 1 Gbps network link can serve approximately 416,000 classical cache lookups per second (at 300 bytes per lookup including protocol overhead). The same link can serve only 29,700 PQ cache lookups per second (at 4,200 bytes per lookup). If your current cache throughput is anywhere near 100,000 lookups per second, PQ migration will saturate your network link.

In-process caches do not have this problem. An in-process cache serves lookups via memory pointer dereference. There is no serialization, no network transfer, and no NIC bottleneck. The lookup cost is 31 nanoseconds regardless of value size. A 4,000-byte PQ credential and a 200-byte classical credential both resolve in 31 nanoseconds from in-process cache. The only cost that scales with value size is memory, and memory is cheap compared to network bandwidth.

The Math at Scale

Let us calculate the total infrastructure impact for a mid-size SaaS application migrating from classical ECDSA-P256 to PQ ML-DSA-65. The application has 1 million active sessions, 500,000 cached JWTs, 50,000 API credentials, and handles 200,000 TLS handshakes per hour.

The total cache memory requirement increases from 529 MB to 7.51 GB -- a 14.2x increase. If this is all on ElastiCache, you need to upgrade from a single r7g.large node (13 GB) to a larger instance or multi-node cluster. The cross-AZ data transfer for these cache lookups increases proportionally with value size, adding thousands of dollars per month to the hidden costs described in our ElastiCache cost analysis.

With an L1 tier absorbing 90% of reads, the ElastiCache requirements drop to approximately 750 MB of active working set (10% of reads hitting L2), which fits on the smallest ElastiCache node type. The L1 memory cost is distributed across application instances: if you have 10 application instances, each one holds approximately 750 MB of L1 cache (its share of the hot working set). This is a modest increase in per-instance memory that avoids the 14x increase in network cache costs.

Planning the Migration

Post-quantum migration is not optional. The timeline varies by industry -- federal contractors face a 2027-2030 mandate for sensitive systems, financial services firms are targeting 2028-2030 for customer-facing systems, and the broader industry will follow as browser and OS defaults change. But the infrastructure impact is the same regardless of timeline: your cryptographic material will grow by 8-50x, and your caching layer must absorb that growth.

The migration plan has three phases. Phase 1 is inventory: catalog every infrastructure component that stores, caches, or transmits cryptographic material. This includes session stores, JWT caches, certificate caches, API credential stores, TLS session ticket caches, CRL/OCSP response caches, and key management system caches. For each component, record the current entry count, entry size, total memory, and access rate.

Phase 2 is capacity planning: for each component, calculate the PQ entry size using the table in this post, multiply by entry count, and compare to your current capacity. Identify which components exceed their current cache allocation after PQ migration. These are the components that need architectural changes (adding an L1 tier or upgrading instance types) before the cryptographic migration begins.

Phase 3 is architecture: for each component that exceeds capacity, decide between two options. Option A is to add an in-process L1 cache tier (recommended for read-heavy workloads with hot-key patterns). Option B is to upgrade your network cache capacity (appropriate for shared-state workloads where L1 is not applicable). In most cases, Option A is both cheaper and faster to implement. An L1 tier with CacheeLFU admission absorbs 80-95% of reads, reducing the network cache requirement to 5-20% of the PQ total -- often less than the classical total before migration.

The infrastructure teams that plan this migration proactively will experience PQ as a manageable capacity upgrade. The teams that discover the impact during a production rollout will experience PQ as an outage caused by cache memory exhaustion, network saturation, or latency degradation at the worst possible moment -- during a security upgrade that cannot be rolled back.

Reference Numbers

For quick reference during capacity planning, here are the per-entry sizes for the most common PQ cache workloads. Use these numbers to estimate your PQ cache requirements by multiplying by your entry count.

# Per-entry cache sizes for capacity planning

Session entry (ML-DSA-65):          5,400 bytes
Session entry (FN-DSA-512):         2,100 bytes
JWT cache entry (ML-DSA-65):        4,000 bytes
JWT cache entry (FN-DSA-512):       1,500 bytes
API credential (ML-DSA-65 hybrid):  3,500 bytes
API credential (FN-DSA-512 hybrid): 2,000 bytes
TLS session ticket (ML-KEM-768):    1,344 bytes
Certificate chain (ML-DSA-65):      18,000 bytes
Certificate chain (FN-DSA-512):     7,500 bytes
Certificate chain (SLH-DSA-128f):   57,000 bytes

# Quick estimation formula:
# Total PQ cache = entries * per_entry_bytes * 1.1 (overhead)
# L1 memory needed = Total PQ cache * 0.15 (hot working set)

FN-DSA-512 (FALCON-512) consistently produces the smallest PQ entries across all infrastructure components because its signatures (666 bytes) and public keys (897 bytes) are the most compact of the lattice-based signature schemes. If cache memory is your primary constraint, FN-DSA-512 is the most infrastructure-friendly PQ signature algorithm. ML-DSA-65 is the more conservative choice (NIST's primary recommendation), but its 3,309-byte signatures create larger infrastructure footprints.

SLH-DSA (hash-based) should be reserved for use cases where stateless hash-based security is explicitly required (long-term document signing, certificate authority roots). Its 17-49 KB signatures make it impractical for high-frequency cache workloads like session stores and JWT verification. A session store with 1 million SLH-DSA-SHA2-128f sessions would require approximately 18 GB for signatures alone.