Lattice-based Cryptography: Basic Example
Introduction to Lattice
In lattice-based cryptography, a lattice is a regularly spaced grid of points in space. It is formed by taking integer linear combinations of a set of vectors, called the “basis”. For this example, let’s use a 2-dimensional lattice, where the lattice points are integer combinations of two vectors.
Why Can Bad Basis Be Used for Encryption, and Good Basis for Decryption?
The core issue lies in lattice-based encryption, where information is mapped to a lattice, encrypted using the public key (Bad Basis), and finally decrypted using the private key (Good Basis). The key point here is the geometric properties of Good Basis and Bad Basis.
Encryption Process (Using Bad Basis as Public Key):
In the encryption process, the dense lattice structure generated by Bad Basis maps the message to a lattice point.
Suppose we want to encrypt a message. First, we choose a random error (noise) and then add some randomness to the message so that the encrypted message can be represented as a point in the lattice. Since the lattice structure of Bad Basis is very dense and hard to manipulate, attackers cannot directly recover the original message from the encrypted one.
Decryption Process (Using Good Basis as Private Key):
During decryption, the private key uses Good Basis. Since the basis vectors of Good Basis are orthogonal, the lattice structure is clearer and easier to manipulate, making it possible to recover the information using Good Basis.
Specifically, using Good Basis, we can find the closest lattice point (i.e., recover the original message using the decryption formula). Because the lattice structure generated by Good Basis is simple, decryption becomes very easy.
Why Can We Use Bad Basis for Encryption and Good Basis for Decryption?
The key lies in the relationship between Bad Basis and Good Basis:
Good Basis and Bad Basis are mathematically related, as they belong to the same lattice. Although the lattice structure generated by Bad Basis is more complex and dense, it is still a different representation of the lattice defined by Good Basis. Through mathematical operations, we can convert Bad Basis into Good Basis and recover information from it.
In fact, the relationship between Bad Basis and Good Basis can be obtained through matrix operations. Using specific algorithms, such as Babai’s rounding algorithm, we can use the information from Bad Basis to find the closest Good Basis point. Since the structure of Good Basis is clearer, it is easy to recover the original message using its basis vectors during decryption.
The security of lattice-based encryption relies on a mathematical problem: recovering the shortest vector (or the correct message) from a dense lattice (defined by Bad Basis) is a very difficult problem. This problem, known as the Shortest Vector Problem (SVP), is currently not efficiently solvable by existing quantum algorithms.
Explanation of Key Points
Lattice Structure: The lattice is generated by linear combinations of basis vectors $( \mathbf{v_1} )$ and $( \mathbf{v_2} )$. In this example, the vectors are simple, but in real applications, the lattice structure is much more complex.
Encryption: The message is transformed into a ciphertext through lattice operations, typically involving some noise or error terms (such as in LWE).
Decryption: The secret key (a vector or some form of trapdoor information) is used to recover the original message by solving lattice-related problems.
This Markdown example is a basic introduction, and in practical lattice-based schemes, the lattice vectors, encryption, and decryption processes are far more intricate. But this should provide a simple framework for understanding the key concepts.