Managing Larger Key
Sizes in Post-Quantum Cryptography

One of the most significant practical challenges of post-quantum cryptography is increased key and signature sizes. While the security benefits are clear — particularly for government and defense applications requiring NIST FIPS compliance — these larger sizes require careful consideration in system design. This guide covers strategies for managing PQC overhead effectively.

Size Comparison

Let's compare sizes between classical and post-quantum algorithms:

The pattern is clear: post-quantum public keys are 18-60x larger than their elliptic-curve counterparts, and signatures range from 10x (FALCON) to 50x (Dilithium) the size of an Ed25519 signature. These are not theoretical numbers; they are the byte costs of every handshake, every signed API response, and every certificate in a chain.

Bandwidth Optimization

For network-constrained applications, raw key and signature sizes translate directly into higher latency and increased data transfer costs. Several techniques can mitigate this:

• Key caching: Cache public keys locally instead of transmitting with each request. A single Dilithium3 public key is 1,952 bytes; if you are verifying 100 signatures per second from the same signer, caching eliminates ~190 KB/s of redundant transfer.
• Compression: PQC keys compress moderately well (~10-20% reduction with zstd or brotli) because lattice-based keys contain structured polynomial coefficients rather than incompressible random bytes.
• FALCON for signatures: When signature size is critical, FALCON offers 5x smaller signatures than Dilithium at the cost of more complex constant-time implementation and floating-point sampling.
• Batch operations: Amortize key transmission overhead across multiple operations. H33 batches 32 users into a single BFV ciphertext (N=4096, 128 dimensions per biometric template), so a single Dilithium signature covers an entire batch attestation rather than signing individually.

// Key caching example — avoids re-fetching 1,952-byte Dilithium public keys
const keyCache = new Map();

async function verifyWithCache(userId, signature, data) {
  let publicKey = keyCache.get(userId);
  if (!publicKey) {
    publicKey = await fetchPublicKey(userId);
    keyCache.set(userId, publicKey);  // ~1.9 KB cached per user
  }
  return h33.quantum.verify({ data, signature, publicKey });
}

Storage Considerations

Database and storage planning for PQC requires rethinking column widths, index strategies, and capacity projections:

• Column sizing: Update VARCHAR/BLOB columns to accommodate larger keys. A BYTEA column holding ECDSA public keys (64 bytes) now needs to hold 1,952 bytes for Dilithium3 or 1,184 bytes for Kyber-768.
• Index efficiency: Larger keys degrade B-tree index fanout. A PostgreSQL page (8 KB) fits ~120 ECDSA keys but only ~4 Dilithium keys. Consider indexing on a SHA3-256 hash of the key rather than the key itself.
• Backup size: Expect 10-50x increase in key-related storage. For 1 million users storing Dilithium3 public keys, that is approximately 1.86 GB compared to ~61 MB for ECDSA P-256.
• Key versioning: Store algorithm identifiers (OIDs or string tags) alongside every key to support future migrations. NIST may standardize additional algorithms, and your schema should not assume a single key type forever.

Protocol Design

When designing protocols around PQC, the goal is to minimize the number of times large keys traverse the wire while still maintaining cryptographic guarantees:

• Separate key exchange from data: Don't embed large keys in every message. Establish a shared secret via ML-KEM once, then use AES-256-GCM or ChaCha20-Poly1305 for all subsequent data. The KEM ciphertext (1,088 bytes for ML-KEM-768) is a one-time cost per session.
• Session establishment: Use PQC for session keys, then symmetric crypto for data. This is exactly how TLS 1.3 with hybrid key exchange works -- the lattice-based KEM adds bytes only to the initial handshake.
• Certificate chains: Be mindful of certificate size in TLS. Each certificate in the chain carries a signature and a public key. A three-certificate Dilithium chain adds roughly 15 KB compared to ~600 bytes for ECDSA. This matters for connection-heavy workloads like CDNs and mobile APIs.

Mobile and IoT Considerations

Resource-constrained devices face particular challenges with post-quantum key sizes, but the situation is more nuanced than simple "bigger is worse":

• Memory: Dilithium3 key generation requires approximately 60 KB of working memory. This is fine for smartphones but may be tight on microcontrollers with 128 KB of total SRAM. FALCON's memory footprint is higher (~80 KB) due to its FFT-based sampling.
• Processing: Lattice-based signing and verification are generally fast -- Dilithium3 verification takes under 250 microseconds on a modern ARM core. The computational cost is rarely the bottleneck; bandwidth and storage are.
• Bandwidth: Mobile networks may see noticeable impact from larger handshakes, especially on high-latency connections. A 4G connection with 50 ms RTT and 10 Mbps throughput adds roughly 14 ms per handshake for the extra PQC bytes.
• Battery: Slightly increased computation may affect battery life on devices performing thousands of operations per day. However, the symmetric-key phase (which dominates data transfer) is unchanged, so the impact is limited to connection establishment.

Real-World Impact

In practice, the overhead is often acceptable when measured against realistic traffic patterns:

The security benefits of quantum resistance far outweigh these modest increases for most applications. The question is not whether to migrate, but how to architect the migration so that size overhead stays contained to the edges of your system.

H33's Approach

At H33, we handle size optimization internally so that PQC complexity never leaks into your application layer:

• Batch attestation: A single Dilithium signature covers a batch of 32 users packed into one BFV ciphertext (N=4096). This reduces the per-user Dilithium overhead from 3,293 bytes to roughly 103 bytes -- a 31x reduction in signature cost per authentication.
• Server-side FHE: Our Full Stack Auth endpoint handles all cryptographic operations server-side. Biometric templates are encrypted under BFV FHE, compared in the encrypted domain, and attested with Dilithium -- your client never touches a lattice key.
• Single API call: Only the final result (proof and signature) needs to be transmitted. The entire pipeline -- FHE inner product, ZKP lookup, and Dilithium attestation -- completes in approximately 42 microseconds per authentication, sustaining 1.595 million authentications per second in production.
• Pre-computed NTT-form keys: Public keys and enrolled templates are stored in NTT (Number Theoretic Transform) form, eliminating redundant forward transforms at authentication time and reducing per-batch latency to approximately 1,109 microseconds for 32 users.

This abstracts the complexity of PQC key management from your application. You send biometric data; you receive a quantum-secure proof. The key sizes, NTT transforms, and Dilithium signatures are implementation details that stay behind our API boundary.

Larger key sizes are a manageable trade-off for quantum security. With thoughtful design -- caching, batching, algorithm selection, and server-side abstraction -- you can minimize their impact while gaining protection against future quantum threats. The migration cost is measured in kilobytes; the security gain is measured in decades.