Post-Quantum Cryptography

Multivariate cryptography is based on the hardness of solving systems of multivariate quadratic equations over finite fields. Security stems from the NP-completeness of the Multivariate Quadratic (MQ) problem.

• Primary Use Case: Digital signatures.
• NIST Candidate: Several algorithms like Rainbow were finalists, though none were selected for standardization in the latest round due to cryptanalytic advances.
• Key Characteristics: Can produce very small signatures and offer fast verification, but often has large public keys. Recent attacks have reduced confidence in some schemes.

Hash-based signatures derive their security solely from the cryptographic collision-resistance of an underlying hash function (like SHA-2 or SHA-3). They use few-time or stateful mechanisms to sign many messages.

• Primary Use Case: Digital signatures, especially for long-term security.
• NIST Standard: SPHINCS+ (a stateless hash-based signature selected as a backup standard).
• Key Characteristics: Security is well-understood and reduces directly to hash function security. They are conservative and considered a strong fallback option, though signature sizes are typically larger than other families.

Isogeny-based cryptography uses the mathematical theory of elliptic curves and the computational difficulty of finding an isogeny (a special kind of map) between two supersingular elliptic curves. Supersingular Isogeny Diffie-Hellman (SIDH/SIKE) was a prominent example.

• Primary Use Case: Key exchange.
• Current Status: A key recovery attack using a "glue-and-split" theorem was published in 2022, effectively breaking the SIDH/SIKE family. This highlights the relative youth and associated risks of this mathematical approach compared to more established families.

Symmetric cryptography (e.g., AES) and cryptographic hash functions (e.g., SHA-256, SHA-3) are generally considered quantum-resistant, but with reduced effective security. Grover's quantum search algorithm provides a quadratic speedup, effectively halving the security level in bits.

• Impact: A 128-bit symmetric key, secure against classical brute-force (2^128 operations), provides ~64 bits of security against a quantum adversary using Grover's algorithm (2^64 operations).
• Mitigation Strategy: The standard recommendation is to double the key size. For long-term post-quantum security, use AES-256 and SHA-384 or SHA-512.

The primary challenge is selecting which post-quantum cryptographic algorithms to adopt. The National Institute of Standards and Technology (NIST) is leading global standardization, having selected CRYSTALS-Kyber for general encryption and CRYSTALS-Dilithium, FALCON, and SPHINCS+ for digital signatures. However, final standards are still being finalized, and early implementations may require updates. Organizations must evaluate candidates based on:

• Performance characteristics (key size, speed, memory usage).
• Security assurances and resistance to both classical and quantum attacks.
• Implementation maturity and availability in common cryptographic libraries.

Cryptographic agility—the ability to seamlessly update cryptographic algorithms within systems—is a critical but often overlooked requirement. Most legacy systems have algorithms hard-coded into protocols like TLS, SSH, and IPsec. Migrating to PQC requires:

• Protocol redesign to support algorithm negotiation and hybrid modes (combining classical and PQC algorithms for transitional security).
• Extensive testing of new cryptographic suites within complex network stacks to ensure interoperability and avoid breaking changes.
• Updates to hardware security modules (HSMs) and other dedicated cryptographic hardware, which are notoriously difficult and slow to modify.

PQC algorithms generally have larger key sizes, signature sizes, and higher computational costs than their classical counterparts (e.g., RSA-2048, ECC P-256). This introduces significant operational overhead:

• Increased bandwidth and storage: Larger keys and certificates increase TLS handshake size, X.509 certificate sizes, and the storage required for signed documents.
• Higher computational latency: Slower signing/verification or encryption/decryption can impact application performance, especially in high-throughput or low-latency environments like content delivery networks or IoT devices.
• Infrastructure scaling: Systems may require more powerful processors or increased server capacity to handle the same workload, directly impacting operational costs.

The most urgent driver for PQC migration is the "Harvest Now, Decrypt Later" threat. A future cryptographically-relevant quantum computer could retroactively decrypt data that is encrypted today with classical algorithms and has been intercepted and stored by an adversary. This necessitates:

• Identifying and prioritizing "long-lived" sensitive data: Intellectual property, state secrets, medical records, and financial data with decades-long confidentiality requirements must be re-encrypted with PQC or protected with quantum-safe key encapsulation before a quantum computer arrives.
• Implementing hybrid encryption schemes in the interim, where data is protected by both a classical and a PQC algorithm, ensuring forward secrecy against the quantum threat.

Enterprises often lack a complete cryptographic inventory—a detailed map of where and how cryptography is used across thousands of applications, libraries, network devices, and embedded systems. This creates massive discovery challenges:

• Identifying cryptographic dependencies in legacy code, third-party software, and proprietary systems.
• Managing the software bill of materials (SBOM) to track vulnerable cryptographic libraries.
• Coordinating upgrades across diverse teams (development, IT, security, product) and with external partners in the supply chain. A single weak link (e.g., an un-upgraded IoT device) can compromise the entire system's security posture.

Thorough testing is paramount, as new mathematical foundations (e.g., lattice-based, hash-based, code-based) may introduce subtle bugs or side-channel vulnerabilities absent in classical crypto. Key validation steps include:

• Conformance testing against official NIST reference implementations and test vectors.
• Interoperability testing between different vendors' PQC implementations.
• Side-channel analysis to ensure implementations are resistant to timing, power, and fault injection attacks.
• Updating compliance frameworks (e.g., FIPS 140-3, Common Criteria) and internal security policies to mandate and validate PQC usage, which is a lengthy process involving accredited labs.

The technique of performing similarity search over high-dimensional vector embeddings while the data remains encrypted. This is essential for privacy-preserving RAG, where a retriever must find relevant document chunks in a private corpus without decrypting it. Techniques include:

• Homomorphic encryption for computing distances in ciphertext space.
• Searchable symmetric encryption (SSE) adapted for vector indices. It allows a query's embedding to be compared against an encrypted vector database, returning only the indices of the closest matches without revealing the database contents.