Electronics Guide

Shor's Algorithm and Public-Key Cryptography

The primary quantum threat to current cryptographic systems comes from Shor's algorithm, developed by mathematician Peter Shor in 1994. This quantum algorithm can efficiently solve the mathematical problems that underpin most widely-used public-key cryptography, specifically integer factorization and the discrete logarithm problem.

RSA encryption relies on the difficulty of factoring large composite numbers into their prime factors. Classical computers require exponential time to solve this problem for sufficiently large numbers, but a quantum computer running Shor's algorithm can accomplish this in polynomial time. Similarly, elliptic curve cryptography (ECC), which bases its security on the elliptic curve discrete logarithm problem, is equally vulnerable to quantum attack.

This means that RSA, ECC, Diffie-Hellman key exchange, and related algorithms will become insecure once sufficiently powerful quantum computers exist. For embedded systems with long deployment cycles, data encrypted today could be stored and decrypted in the future when quantum computers become available, a threat model known as "harvest now, decrypt later."

Grover's Algorithm and Symmetric Cryptography

Grover's algorithm provides a quadratic speedup for searching unstructured databases, which translates to effectively halving the security level of symmetric cryptographic algorithms and hash functions. A 256-bit AES key, for example, would provide only 128 bits of security against a quantum adversary.

The mitigation for symmetric cryptography is relatively straightforward: doubling key sizes maintains the original security level. AES-256 remains secure against quantum attacks when 128-bit security is acceptable. Hash functions like SHA-256 may need to be replaced with SHA-384 or SHA-512 for applications requiring higher security margins.

Timeline Considerations

While large-scale fault-tolerant quantum computers capable of breaking current cryptography do not yet exist, the timeline for their development is uncertain. Estimates range from 10 to 30 years, but the long certification cycles, deployment timelines, and operational lifespans of embedded systems mean that migration to quantum-resistant cryptography must begin now.

Critical infrastructure, automotive systems, industrial control systems, and medical devices designed today may still be in operation when cryptographically relevant quantum computers become available. The transition to post-quantum cryptography requires careful planning, testing, and phased deployment that can take many years to complete.

Standardization Process

The National Institute of Standards and Technology (NIST) initiated a post-quantum cryptography standardization process in 2016, evaluating candidate algorithms through multiple rounds of public scrutiny and cryptanalysis. In 2024, NIST released the first set of finalized post-quantum cryptographic standards, providing a foundation for widespread adoption.

The standardization process considered not only cryptographic security but also performance characteristics, implementation complexity, and suitability for various deployment scenarios including resource-constrained embedded systems.

ML-KEM (Kyber)

ML-KEM, derived from the CRYSTALS-Kyber algorithm, is the primary standard for key encapsulation mechanisms (KEMs). It is based on the Module Learning With Errors (MLWE) problem, a variant of lattice-based cryptography that offers strong security guarantees and efficient implementation.

Key characteristics of ML-KEM include relatively compact key and ciphertext sizes compared to other post-quantum alternatives, fast key generation and encapsulation operations, and straightforward constant-time implementation. The algorithm is well-suited for embedded systems, with implementations requiring modest memory and computational resources.

ML-KEM is available in three security levels: ML-KEM-512, ML-KEM-768, and ML-KEM-1024, corresponding approximately to AES-128, AES-192, and AES-256 security levels respectively. For most embedded applications, ML-KEM-768 provides an appropriate balance of security and performance.

ML-DSA (Dilithium)

ML-DSA, based on the CRYSTALS-Dilithium algorithm, is the primary standard for digital signatures. Like ML-KEM, it relies on lattice-based cryptography, specifically the Module Learning With Errors problem combined with the Short Integer Solution problem.

ML-DSA signatures are larger than classical ECDSA signatures but remain practical for most applications. The algorithm offers fast signing and verification operations, making it suitable for embedded systems that require digital signature functionality for firmware updates, secure boot, or authenticated communications.

Three security levels are specified: ML-DSA-44, ML-DSA-65, and ML-DSA-87. The middle variant, ML-DSA-65, is recommended for most applications requiring strong security without excessive signature sizes.

SLH-DSA (SPHINCS+)

SLH-DSA, derived from SPHINCS+, provides a hash-based digital signature scheme that serves as a conservative alternative to lattice-based signatures. Its security relies solely on the properties of cryptographic hash functions, which are well-understood and have been extensively analyzed.

The primary trade-off with SLH-DSA is significantly larger signature sizes compared to ML-DSA. However, for applications where long-term security assurance is paramount and signature size is less critical, SLH-DSA offers a conservative choice with security guarantees that do not depend on the hardness of lattice problems.

SLH-DSA is particularly valuable for root-of-trust applications, certificate authorities, and firmware signing where the conservative security posture outweighs the size overhead.

Memory Requirements

Post-quantum cryptographic algorithms generally require more memory than their classical counterparts. Public keys, private keys, ciphertexts, and signatures are all larger, and the algorithms themselves often require substantial working memory for intermediate computations.

For ML-KEM-768, public keys are approximately 1,184 bytes and ciphertexts are 1,088 bytes, compared to 32-64 bytes for ECC equivalents. ML-DSA-65 signatures are approximately 3,293 bytes, significantly larger than 64-byte ECDSA signatures. These increased sizes affect storage requirements, transmission bandwidth, and RAM usage during cryptographic operations.

Embedded systems with limited RAM must carefully manage memory allocation during cryptographic operations. Some implementations use stack allocation that may exceed default stack sizes, requiring careful configuration. Flash storage for keys and certificates may need to be increased to accommodate larger post-quantum credentials.

Computational Performance

While post-quantum algorithms are generally more computationally intensive than classical alternatives, the performance impact varies significantly by algorithm and operation. ML-KEM and ML-DSA are designed to be efficient and perform well even on resource-constrained microcontrollers.

On a typical ARM Cortex-M4 microcontroller, ML-KEM-768 key generation and encapsulation complete in tens of milliseconds, comparable to or faster than RSA-2048 operations. ML-DSA signing and verification are similarly practical, though somewhat slower than optimized ECC implementations.

The specific performance characteristics depend heavily on implementation optimization. Leveraging hardware acceleration for arithmetic operations, carefully optimizing memory access patterns, and using platform-specific instructions can significantly improve performance.

Side-Channel Resistance

Embedded systems are often deployed in environments where attackers may have physical access, making resistance to side-channel attacks essential. Post-quantum algorithms introduce new attack surfaces that require careful mitigation.

Timing attacks exploit variations in execution time that depend on secret data. Constant-time implementations that avoid data-dependent branches and memory accesses are essential. The lattice-based algorithms in ML-KEM and ML-DSA include operations that must be carefully implemented to avoid timing leaks.

Power analysis attacks measure the power consumption of a device during cryptographic operations to extract secret information. Countermeasures include masking, shuffling operations, and adding random delays. The polynomial arithmetic in lattice-based cryptography requires specific countermeasures different from those used for classical algorithms.

Electromagnetic emanation attacks and fault injection attacks also pose threats. Comprehensive side-channel protection requires a layered approach combining algorithmic, implementation, and hardware countermeasures.

Random Number Generation

Post-quantum algorithms have stringent requirements for random number generation. Poor-quality randomness can catastrophically compromise security, making the implementation of robust random number generators critical.

Hardware random number generators (HRNGs) provide entropy from physical sources, but their output must be properly conditioned and health-tested. Deterministic random bit generators (DRBGs) expand limited entropy into larger quantities of pseudorandom output, with NIST-approved algorithms like HMAC-DRBG or CTR-DRBG commonly used.

For resource-constrained embedded systems, accumulating sufficient entropy can be challenging. Careful design must ensure that random number generators are properly seeded at boot time and that entropy is maintained across power cycles when necessary.

liboqs

The Open Quantum Safe (OQS) project provides liboqs, an open-source library implementing a variety of post-quantum algorithms including the NIST-standardized algorithms. While primarily targeting desktop and server environments, liboqs can be adapted for embedded use with appropriate optimizations.

The library provides a consistent API across different algorithms, simplifying the development of crypto-agile applications that can switch between algorithms as standards evolve or vulnerabilities are discovered.

pqcrypto

The pqcrypto library offers optimized implementations of post-quantum algorithms specifically designed for performance on various platforms. It includes platform-specific optimizations for ARM processors commonly used in embedded systems.

Embedded-Focused Implementations

Several implementations target embedded systems specifically. PQClean provides clean, portable reference implementations suitable as a starting point for embedded ports. The pqm4 project provides optimized implementations for ARM Cortex-M4 microcontrollers, demonstrating practical performance on resource-constrained devices.

Vendors of secure microcontrollers and security ICs are increasingly providing post-quantum algorithm support in their firmware libraries and hardware accelerators. These implementations often include side-channel countermeasures and certification for security standards.

TLS and Protocol Integration

Post-quantum algorithms are being integrated into security protocols like TLS. Hybrid key exchange mechanisms combine classical and post-quantum algorithms to provide security against both classical and quantum adversaries during the transition period.

For embedded systems using TLS for secure communications, libraries like wolfSSL and Mbed TLS are adding post-quantum support. The increased handshake sizes and computational requirements may require protocol-level optimizations such as session resumption to minimize overhead.

Arithmetic Accelerators

The core operations in lattice-based cryptography involve polynomial arithmetic, particularly the Number Theoretic Transform (NTT) used for efficient polynomial multiplication. Hardware accelerators for NTT computation can significantly improve performance while reducing energy consumption.

Some modern microcontrollers include DSP instructions and SIMD capabilities that can be leveraged for polynomial arithmetic. Dedicated cryptographic coprocessors are emerging that provide hardware acceleration for post-quantum algorithms.

Hash Function Acceleration

Post-quantum algorithms make extensive use of hash functions, particularly SHA-3 (Keccak) and SHAKE variants. Hardware acceleration for these hash functions, available in some security-focused microcontrollers, provides significant performance benefits.

The SHAKE extendable-output functions are particularly important for ML-KEM and ML-DSA, where they are used for key generation, sampling, and other operations. Efficient SHAKE implementation or acceleration directly impacts overall algorithm performance.

Secure Elements and HSMs

Hardware Security Modules (HSMs) and secure elements provide isolated environments for cryptographic operations with built-in side-channel protections. These devices are increasingly adding support for post-quantum algorithms.

For embedded systems requiring high security assurance, offloading post-quantum cryptography to dedicated secure hardware provides both performance benefits and security advantages. The secure element handles key storage, random number generation, and cryptographic operations in a protected environment.

Cryptographic Agility

Cryptographic agility, the ability to change cryptographic algorithms without significant redesign, is essential for long-lived embedded systems. Systems should be designed to allow algorithm updates through firmware updates or configuration changes.

This requires abstracting cryptographic operations behind well-defined interfaces, allocating sufficient resources for larger algorithm requirements, and establishing secure update mechanisms. Protocol negotiation mechanisms should allow endpoints to select mutually-supported algorithms.

Hybrid Approaches

During the transition period, hybrid cryptographic schemes that combine classical and post-quantum algorithms provide defense-in-depth. If either the classical or post-quantum algorithm is broken, the combined scheme remains secure.

For key encapsulation, hybrid schemes concatenate the shared secrets from both classical and post-quantum KEMs. For signatures, hybrid schemes may use dual signatures or combined signature schemes. These approaches add overhead but provide insurance against both algorithm-specific vulnerabilities and potential weaknesses in new post-quantum algorithms.

Phased Deployment

Migration to post-quantum cryptography should follow a phased approach. Initial phases focus on inventory and assessment, identifying all cryptographic assets and their quantum vulnerability. Subsequent phases involve implementing cryptographic agility, testing post-quantum algorithms, and gradually deploying hybrid and pure post-quantum solutions.

For embedded systems, the update mechanisms themselves must be secured with quantum-resistant cryptography. Secure boot chains, firmware signing, and update authentication should transition early to prevent attackers from compromising update mechanisms and blocking future migrations.

Secure Boot and Firmware Updates

Secure boot implementations should transition to post-quantum signature verification to ensure that only authorized firmware can execute. Root keys stored in immutable memory should use post-quantum algorithms, potentially with hybrid schemes for additional assurance.

Firmware update mechanisms must accommodate larger signatures and potentially longer verification times. Update image sizes may increase due to larger signatures, affecting storage and transmission requirements.

Device Authentication

Device identity and authentication mechanisms using public-key cryptography require migration to post-quantum alternatives. Certificate chains will be larger, and the verification process may require more memory and time.

For constrained IoT devices, lightweight authentication protocols designed specifically for post-quantum settings may be preferable to adapting full certificate-based authentication.

Secure Communications

TLS connections using post-quantum key exchange will have larger handshake messages. Network protocols may need adjustment to accommodate increased packet sizes, and connection establishment may take longer.

Session resumption and connection persistence become more important to amortize the increased handshake overhead. Pre-shared key modes with post-quantum key establishment can reduce per-connection overhead.

Long-Term Data Protection

Data that must remain confidential for extended periods should be protected with post-quantum encryption now, even if the threat from quantum computers is years away. The harvest-now-decrypt-later threat model makes immediate action necessary for sensitive data.

Key management systems should plan for algorithm transitions, ensuring that encrypted data can be re-encrypted with new algorithms as needed while maintaining access throughout the transition.

Functional Testing

Post-quantum implementations require thorough functional testing using known-answer tests (KATs) provided by algorithm specifications and reference implementations. Interoperability testing with other implementations ensures correct protocol behavior.

Edge cases and error conditions must be carefully tested. Invalid inputs, truncated messages, and malformed keys should be handled gracefully without revealing sensitive information through error messages or timing differences.

Performance Benchmarking

Comprehensive performance benchmarking on target hardware is essential for understanding the impact of post-quantum cryptography on system performance. Measurements should include operation latency, throughput, memory usage, and energy consumption.

Performance testing should cover representative use cases, including cold-start scenarios, sustained operation, and peak-load conditions. The results inform capacity planning and help identify optimization opportunities.

Security Evaluation

Side-channel analysis should be performed on implementations before deployment. This includes timing analysis, power analysis, and electromagnetic analysis to identify information leakage. Specialized equipment and expertise are required for comprehensive side-channel evaluation.

Fault injection testing verifies that implementations behave safely under abnormal conditions. Voltage glitching, clock manipulation, and laser fault injection can reveal vulnerabilities in security-critical code paths.

Additional Standardization

NIST and other standards bodies continue to evaluate additional post-quantum algorithms. Signature schemes based on different mathematical foundations provide diversity and backup options if lattice-based schemes prove vulnerable.

Code-based cryptography, isogeny-based cryptography, and multivariate cryptography offer alternative foundations. While current standards focus on lattice-based and hash-based schemes, the cryptographic landscape may evolve as research continues.

Hardware Evolution

Semiconductor vendors are developing dedicated hardware acceleration for post-quantum algorithms. Future microcontrollers will likely include built-in support for ML-KEM, ML-DSA, and related algorithms, making implementation more straightforward and efficient.

Emerging secure microcontrollers combine ARM Cortex-M cores with cryptographic accelerators, secure storage, and side-channel countermeasures specifically designed for post-quantum security.

Protocol Standards

Standard protocols like TLS, IPsec, SSH, and others are being updated to support post-quantum algorithms. These updates will propagate to embedded protocol stacks, enabling transparent post-quantum security for networked embedded systems.

Industry-specific protocols in automotive, industrial, and medical domains are also beginning to address quantum resistance, often with extended timelines reflecting the long certification and deployment cycles in these sectors.