Post-quantum cryptography is an evolving field that aims to develop cryptographic algorithms that remain secure even in the face of attacks using quantum computers, most notably Shor’s algorithm. Shor’s algorithm has the potential to efficiently factorize large numbers and solve discrete logarithm problems, which are fundamental to many widely used cryptographic algorithms like RSA and some elliptic curve-based schemes.
Objective:
Post-quantum cryptography focuses on developing cryptographic algorithms and systems that remain secure even in the presence of powerful quantum computers. It aims to replace current cryptographic standards that may be broken by quantum algorithms, such as Shor’s algorithm for factoring large numbers and solving discrete logarithm problems.
Underlying Assumptions:
Post-quantum cryptographic algorithms are designed based on mathematical problems that are believed to be hard for both classical and quantum computers. These problems, such as lattice-based problems, multivariate polynomials, and hash functions, form the foundation of post-quantum algorithms.
Resistance to Quantum Attacks:
Post-quantum cryptographic algorithms are designed to resist attacks performed using a quantum computer, including Shor’s algorithm. The complexity of the mathematical problems they are based on is assumed to remain high even when solved by quantum algorithms.
Examples of Post-Quantum Algorithms:
- Lattice-based cryptography (e.g., Ring Learning With Errors)
- Code-based cryptography (e.g., McEliece cryptosystem)
- Hash-based cryptography (e.g., Merkle Tree-based hash functions)
- Isogeny-based cryptography (e.g., Supersingular Isogeny Diffie-Hellman)
- Multivariate polynomial-based cryptography (e.g., Unbalanced Oil and Vinegar)
Lattice-based cryptography :
Lattice-based cryptography is a fundamental area of research in modern cryptography and is considered a promising approach for achieving post-quantum security. It’s based on mathematical structures called lattices, which are essentially regular repeating patterns of points in space. Lattice problems form the basis for creating cryptographic algorithms that are believed to be resistant to attacks from quantum computers.
Mathematical Foundation:
- Lattices are mathematical structures that consist of a set of points in n-dimensional space with certain geometric properties. The foundation of lattice-based cryptography lies in the hardness of certain computational problems associated with lattices.
Lattice Problems:
- Shortest Vector Problem (SVP): Given a lattice, find the shortest non-zero vector within the lattice. This problem is known to be NP-hard (non-deterministic polynomial-time hard), forming the basis for lattice-based cryptography.
- Learning With Errors (LWE): LWE is another key lattice problem that is believed to be hard to solve. It involves finding a hidden vector multiplied by a random matrix, rounded to the nearest multiple of a small noise value, and given some additional noise values.
Cryptography Based on Lattices:
- Ring Learning With Errors : A central lattice-based problem used in constructing cryptographic primitives like public-key encryption, digital signatures, and key exchange.
- Lattice-Based Encryption Schemes: Lattice-based encryption schemes, such as NTRU, use the hardness of lattice problems like LWE to create secure encryption algorithms.
- Lattice-Based Digital Signatures: Lattice-based signatures, like BLISS and Dilithium, use lattice problems as the underlying hard computational task to design secure digital signature schemes.
- Lattice-Based Key Exchange: Cryptographic key exchange protocols like the NewHope protocol use lattice-based techniques to enable secure key exchange between parties.