Post-quantum Cryptography

The Need for Post-Quantum Cryptography

Recent advancements in quantum computing indicate an inevitable future of functional and widely accessible quantum computer systems. Progress has been notable in developing more stable and scalable qubits, the fundamental units of quantum information, using technologies such as superconducting circuits, trapped ions, and photonic qubits. Companies such as IBM, Google, Rigetti, and IonQ have been pivotal in advancing qubit counts and reducing error rates.

Initiatives like the European Quantum Communication Infrastructure (EuroQCI) and the National Quantum Initiative in the United States underscore the global commitment to advancing quantum technologies. Concurrently, there have been significant strides in quantum algorithms, particularly in areas like quantum simulation, optimization, and cryptography. Researchers are actively exploring how quantum computers can efficiently tackle NP-hard problems that are challenging for classical computers.

While promising a substantial increase in computational power, capable of solving complex problems efficiently, quantum computing also presents new cybersecurity challenges. Quantum algorithms capable of swiftly solving problems such as integer factorization and discrete logarithms threaten the security of classical cryptosystems like RSA, ECC, and ElGamal, which rely on these problems for their cryptographic strength. Consequently, there is an urgent need to reassess and potentially replace these classical cryptosystems with a new generation of post-quantum algorithms and cryptographic techniques, currently under active research and development.

NIST's PQC Standardization Efforts

The National Institute of Standards and Technology (NIST) has been leading standardization efforts in post-quantum cryptography (PQC) to address the cryptographic vulnerabilities posed by quantum computers. NIST launched its Post-Quantum Cryptography Standardization project in 2016 to solicit, evaluate, and standardize quantum-resistant cryptographic algorithms. The goal is to develop standards that can protect sensitive information against attacks from both classical and quantum computers.

Lattice-based cryptography has gained attention as a potential candidate for post-quantum cryptography. Lattice-based cryptographic schemes are believed to be resistant to attacks from both classical and quantum computers. The security relies on the difficulty of solving lattice problems, which are believed to be hard even for quantum computers due to the quantum algorithms known so far. Lattice-based cryptography has several advantages, including its strong theoretical foundation, efficient algorithms for certain operations, and resistance against quantum attacks. It also offers a good balance between security and performance, making it suitable for various practical applications.

Code-based cryptography has also been considered as one of the candidates for post-quantum cryptography. Code-based cryptography is a form of cryptography that relies on error-correcting codes rather than number theory for its security properties. The security of code-based schemes is based on the hardness of the McEliece cryptosystem, which involves the difficulty of finding a decoding error vector in a random linear code. This problem is believed to be resistant to attacks from both classical and quantum computers. One major advantage of code-based cryptography is its proven security against quantum attacks. The algorithms used are based on well-established mathematical principles in coding theory, providing a strong foundation for security guarantees and have withstood the test of time.

Lattice-based Cryptography

Lattice-based cryptography is a branch of cryptography that relies on the complexity of certain mathematical problems related to lattices in high-dimensional spaces. Lattices are geometric structures formed by points arranged in a regular pattern in multiple dimensions. In lattice-based cryptography, security is based on the hardness of certain lattice problems, such as the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem. These problems involve finding short vectors in a lattice or distinguishing random noise from lattice points. Lattice-based cryptography offers a wide range of cryptographic primitives, including encryption (e.g., Ring-LWE encryption), digital signatures (e.g., BLISS and NTRU), key exchange protocols (e.g., NewHope), and other cryptographic primitives like homomorphic encryption and secure multi-party computation.

Implementing lattice-based cryptographic schemes efficiently can be challenging, especially in terms of key sizes and computational overhead. However, ongoing research aims to address these challenges and improve the practicality of lattice-based cryptography.

Code-based Cryptography

Code-based cryptography uses mathematical coding theory, specifically error-correcting codes, as the basis for its security. The security of code-based cryptography relies on the difficulty of decoding linear error-correcting codes. Code-based cryptography provides cryptographic primitives such as encryption (e.g., the McEliece cryptosystem), digital signatures (e.g., the Niederreiter cryptosystem), and key exchange protocols. Code-based cryptography faces challenges in terms of efficiency and key size. Key sizes tend to be larger compared to some other cryptographic schemes, which can impact performance and memory requirements. However, ongoing research aims to optimize these aspects.

Back to Blogs