How complex is the algorithm of post-quantum cryptography?

The algorithm complexity of post-quantum cryptography (PQC) is significantly higher than that of traditional public-key cryptography due to the need to resist attacks from quantum computers. PQC algorithms are designed to secure data against both classical and quantum threats, which requires more computational resources and advanced mathematical techniques.

Key Aspects of PQC Complexity:

1. Mathematical Foundations: PQC relies on hard problems in lattice-based cryptography, code-based cryptography, multivariate polynomial systems, hash-based signatures, and isogeny-based cryptography. These problems are harder to solve than the integer factorization or discrete logarithm problems used in RSA and ECC.

   • Example: Lattice-based schemes like CRYSTALS-Kyber (for key exchange) or CRYSTALS-Dilithium (for signatures) involve complex algebraic structures over high-dimensional lattices.

2. Key and Ciphertext Sizes: PQC algorithms typically produce larger keys and ciphertexts compared to traditional schemes, increasing storage and bandwidth requirements.

   • Example: A Kyber-768 key exchange generates a 1,184-byte public key and a 2,400-byte ciphertext, whereas RSA-2048 uses a 256-byte public key and a 256-byte ciphertext.

3. Performance Overhead: PQC operations are computationally intensive, especially for devices with limited resources like IoT devices.

   • Example: Dilithium signatures require more CPU cycles than ECDSA due to their reliance on matrix operations.

Tencent Cloud Solutions:

For businesses adopting PQC, Tencent Cloud offers Quantum-Safe Cryptography Services to help migrate to post-quantum secure solutions. These services support hybrid cryptographic schemes, combining classical and PQC algorithms to ensure backward compatibility while preparing for quantum threats. Additionally, Tencent Cloud’s Key Management System (KMS) can integrate PQC algorithms for secure key storage and management.