Quantum Computing and Its Impact on Cryptography

Quantum computing is an emerging field of computing that harnesses the principles of quantum mechanics to perform calculations far beyond the capabilities of classical computers. While still in its early stages of development, quantum computing has the potential to revolutionize various fields, including medicine, materials science, and artificial intelligence. However, it also poses a significant threat to modern cryptography, potentially rendering many widely used encryption algorithms insecure. This guide explores the basics of quantum computing, its potential impact on cryptography, and the steps being taken to develop quantum-resistant cryptography.

What is Quantum Computing?

Quantum computing differs fundamentally from classical computing, which is based on bits that represent either a 0 or a 1. Quantum computing utilizes qubits (quantum bits). Qubits leverage the principles of quantum mechanics, specifically:

• Superposition: Qubits can exist in a combination of states (both 0 and 1 simultaneously) until measured. Think of it like a coin spinning in the air – it's both heads and tails until it lands.
• Entanglement: Two or more qubits can be linked together in such a way that they share the same fate, even if they are physically separated. Measuring the state of one entangled qubit instantly reveals the state of the other.
• Quantum Interference: Qubits can interfere with each other, allowing for the amplification of correct answers and cancellation of incorrect answers during computation.

These quantum phenomena allow quantum computers to perform certain types of calculations exponentially faster than classical computers. This speedup is particularly relevant to problems that involve searching large spaces or factoring large numbers – problems that are fundamental to modern cryptography.

The Threat to Current Cryptography

Most of the public-key cryptography used today relies on the computational difficulty of certain mathematical problems for its security. Specifically:

• Integer Factorization Problem (RSA): RSA, a widely used public-key encryption algorithm, relies on the difficulty of factoring large numbers into their prime factors. A classical computer would take an impractically long time (potentially billions of years) to factor a very large number used in RSA encryption.
• Discrete Logarithm Problem (Diffie-Hellman, DSA): Diffie-Hellman key exchange and the Digital Signature Algorithm (DSA) rely on the difficulty of solving the discrete logarithm problem in certain mathematical groups.
• Elliptic Curve Discrete Logarithm Problem (ECC): Elliptic Curve Cryptography (ECC), which is increasingly used for its efficiency, relies on the difficulty of solving the elliptic curve discrete logarithm problem.

Shor's Algorithm: In 1994, mathematician Peter Shor developed a quantum algorithm (Shor's Algorithm) that can efficiently factor large numbers and solve the discrete logarithm problem. This means that a sufficiently powerful quantum computer could break RSA, Diffie-Hellman, DSA, and ECC, rendering much of the current public-key infrastructure insecure.

Impact on Symmetric Cryptography: While the impact on public-key cryptography is more dramatic, quantum computers also pose a threat to symmetric encryption algorithms like AES. Grover's algorithm, another quantum algorithm, can speed up the search for a key in a symmetric cipher. However, the impact is less severe:

• AES-256, for example, is considered to still offer sufficient security against quantum computers with adequate security margins. Simply doubling the key length of a symmetric cipher (e.g., from AES-128 to AES-256) can provide resistance to Grover's algorithm.

Post-Quantum Cryptography (PQC) / Quantum-Resistant Cryptography

The threat posed by quantum computing has spurred research into Post-Quantum Cryptography (PQC), also known as quantum-resistant cryptography. PQC refers to cryptographic algorithms (usually public-key algorithms) that are believed to be secure against attacks by both classical and quantum computers. These algorithms are based on mathematical problems that are believed to be difficult to solve even for quantum computers.

Main Approaches to PQC:

• Lattice-based Cryptography: Based on the difficulty of solving problems related to lattices in high-dimensional spaces. Considered a leading candidate for PQC. Examples: NTRU, Ring-LWE, Kyber.
• Code-based Cryptography: Based on the difficulty of decoding general linear codes. Example: McEliece cryptosystem.
• Multivariate Cryptography: Based on the difficulty of solving systems of multivariate polynomial equations over finite fields. Example: Rainbow.
• Hash-based Cryptography: Uses hash functions to build digital signature schemes. These are well-understood and considered secure, but have some limitations in terms of signature size and performance. Example: XMSS, SPHINCS+.
• Supersingular Isogeny Key Exchange (SIKE): *Note: SIKE was a promising candidate, but it was broken in 2022 by a classical attack. This highlights the ongoing research and development in PQC.* This emphasizes that even PQC algorithms are subject to ongoing scrutiny and potential attacks.

NIST Post-Quantum Cryptography Standardization Process:

The National Institute of Standards and Technology (NIST) has been running a multi-year process to standardize one or more quantum-resistant public-key cryptographic algorithms. This process involves:

• Call for proposals: NIST solicited proposals for quantum-resistant algorithms from the cryptographic community.
• Multiple rounds of evaluation: The submitted algorithms have undergone multiple rounds of rigorous analysis and evaluation by cryptographers worldwide.
• Selection of finalists: NIST has selected a number of finalist algorithms for further consideration.
• Standardization: NIST plans to publish standards for quantum-resistant algorithms in the near future (as of late 2023, some algorithms have been selected for standardization).

As of August 2024, NIST announced the first four algorithms it will standardize:

• CRYSTALS-Kyber: Selected for general encryption.
• CRYSTALS-Dilithium: Selected for digital signatures.
• FALCON: Selected for digital signatures.
• SPHINCS+: Selected for digital signatures.

NIST also announced that it is continuing to evaluate other algorithms for potential future standardization, particularly for general encryption, with a focus on algorithms that offer different security properties than Kyber. BIKE, Classic McEliece, HQC, and SIKE are in the fourth round of consideration (as of this writing, although note SIKE has since been broken).

Preparing for a Post-Quantum World

Organizations need to start preparing now for the eventual arrival of quantum computers that can break current cryptography. Here are some steps to take:

1. Assess Cryptographic Agility:
   • Inventory Cryptographic Assets: Identify all systems and applications that rely on cryptography, including specific algorithms and key lengths used.
   • Assess Agility: Determine how easily your systems can be updated to use new cryptographic algorithms. This is known as "crypto-agility."
2. Stay Informed:
   • Monitor NIST's PQC Standardization Process: Track the progress of NIST's standardization process and the development of new quantum-resistant algorithms.
   • Follow Cryptography Research: Stay informed about the latest research in quantum computing and post-quantum cryptography.
3. Plan for Migration:
   • Develop a Migration Strategy: Start planning for the eventual migration to quantum-resistant cryptography. This will be a complex and lengthy process for many organizations.
   • Prioritize: Identify the most critical systems and data that need to be protected first.
   • Test PQC Algorithms: Begin testing and evaluating candidate PQC algorithms in your environment to understand their performance and compatibility.
4. Implement Hybrid Approaches:
   • Combine Classical and Quantum-Resistant Algorithms: Consider using hybrid approaches that combine classical cryptographic algorithms with quantum-resistant algorithms to provide a transitional layer of security.
5. Advocate for Crypto-Agility:
   • Design new systems and applications with crypto-agility in mind, making it easier to switch to new cryptographic algorithms in the future.
6. Long-Term Data Protection:
   • For data that needs to remain confidential for decades, consider the risk posed by "harvest now, decrypt later" attacks, where encrypted data is stolen today and decrypted once a quantum computer is available. Apply quantum-resistant encryption to this data *now* if feasible.
7. Collaborate and Share Information:
   • Collaborate with industry peers, researchers, and government agencies to share information and best practices for preparing for the post-quantum era.
8. Increase Key Sizes (for Symmetric Ciphers):
   • For symmetric ciphers like AES, increasing the key size (e.g., from AES-128 to AES-256) can provide adequate protection against quantum attacks using Grover's algorithm.

The advent of quantum computing presents a serious long-term threat to much of the cryptography that underpins modern digital security. While large-scale, fault-tolerant quantum computers capable of breaking current encryption are not yet a reality, the potential impact is so significant that organizations must start preparing now. The development and standardization of post-quantum cryptography is a critical effort, and organizations should begin assessing their cryptographic agility, planning for migration to quantum-resistant algorithms, and staying informed about the latest developments in this rapidly evolving field. The transition to a post-quantum world will be a complex and lengthy process, but proactive planning and preparation are essential for ensuring the long-term security of our digital infrastructure.

Worried about the impact of quantum computing on your organization's IT security? Contact HelpDesk Heroes! Our security experts can help you assess your cryptographic risk, develop a plan for migrating to post-quantum cryptography, and ensure your systems are protected against the threats of the future.

Read more from our blog