Cryptography is a technique to transform plain text to cipher text and vice versa. We use a key for the conversion, which can be used for encoding and decoding. Plain Text is a piece of writing that can be understood and read by any human. However, Cipher Text is an encrypted piece of text that can only be read by humans but cannot be understood.
In this blog, we will use several examples to understand one of the concepts of Post-Quantum Cryptography- Learning with the Errors. We will also learn in brief about Cryptography and Lattice in Cryptography.
Lattice in Cryptography
Lattice in Cryptography has been in focus for a long time. This is because the lattice is a security provided to the NTRU public-key cryptosystem. That is, NTRU’s confidentiality is based on certain lattice problems.
NTRUEncrypt is a quick ecosystem and is very easy to implement. It is based on three parameters- N, p, and q- fixed integers. All the computations are performed in the ring R with an equation,
R = Z[x]/(x N − 1)
The reason why Ring is preferred is the multiplication of two components is easy in R.
For Example, N=3, and we want to compute the product of (x^2 + 3x + 1)(2x^2 + x − 4). The computation will be done as
Now, we will use the vector of coefficients given below to represent the above polynomial in R.
Suppose we already have,
and
Using the above relations, we calculate that the coefficient of vectors has the relation c= a*b
Now, we have
This equation, and the relation will be used to find a solution for the polynomial.
Learning with the Errors
By its name, you might have an idea of what the module is all about. The process involves generating errors for learning.
Suppose you have a linear equation. You can find a solution to this equation in a few variables. But did you learn anything?
Now, by introducing some randomness to the equation, you will be able to get a new problem. This way, you can learn more about the equation.
Suppose Z denotes the ring of integers of modulo q, and there is a set of n vectors over it. There is a certain unknown linear function where,
The input to the LWE problem is a sample of pairs (x,y) where,
Now, there is a high probability that this relation becomes true, y= f(x).
The deviation from the equality is based on some known noise model. The LWE problem aims to find the values of function f or some close approximation to it. We will use a cryptosystem based on LWE for better understanding.
Regev Cryptosystem
The Regev Cryptosystem is based on Learning with the Errors (LWE) used to encrypt a single bit. Note that the cipher text involves a sum of samples and the errors in the sample are also summed up. The Regev Cryptosystem follows that to make decryption possible, it is vital to choose the probability distribution in such a way that the effective error is not such that it hampers the solution set.
Let x and y be integers and q is a modulo. E is a discrete random variable defined on Zq. The private key element, s E Znq
and the public key consists of m samples (ai, bi), where ai E Znq and
We will choose a random subset S ⊆ {1, 2, . . . , m} to encrypt a one-bit message x. The cipher text y is given by
Compute the quantity given below to decrypt a cipher text.
The value of decrypted message can either be 0 or 1. If the result of above quantity is closer to 1, the value is 0. If the result is closer to q/2, the value is 1.
This Cryptosystem turned out to be impractical due to long process required to encrypt a single bit. There are more efficient cryptosystems based on Learning with the Errors (LWE).
Decision Version
The LWE version you just learned is the search version. The Decision Version aims to differentiate noisy inner products from uniformly random samples of equation
The Decision and Search can be made equivalent if q is a prime bounded by some polynomial in n.
There are two types of LWE problems in Decision Version- Solving decision assuming search and Solving search assuming decision.
Solving decision assuming search
We have a procedure for the search problem, the decision version is calculated.
In this type, denote the given samples by
If the variable s is also involved in the calculation, use the relation
If the samples are not uniform, the result of the calculation will be distributed on the basis of fixed probability. However, if the samples are uniform, the result will be distributed randomly.
Solving search assuming decision
We have a procedure for the decision problem, the search version is calculated.
We will start recovering s candidates, one at a time. To obtain the first candidate s1, follow these steps.
1. Make a guess k E Zq.
2. Choose any random number r E Zq uniformly.
3. Transform the given samples as
4. Calculate the samples using the following equation.
5. Send the calculated samples to the decision solver.
6. If the guess k was correct, it is taken to the following distribution.
Otherwise, it is taken to the uniform distribution.
At the end, you will get separate sets for both the distributions.
Frequently Asked Questions
Briefly explain DSA.
The full form of DSA is Digital Signature Algorithm. DSA is one type of cryptographic algorithm used to create keys, sign data and validate signatures. It encrypts the digital signatures and hence, secure them.
Mention the importance of Encryption.
Encryption ensures the conversation’s privacy and confidentiality. We frequently use Encryption when there is a need to secure the data such as financial statements, test results, or important documents.
Name the two types of Cryptographic Algorithms.
The two types of Cryptographic Algorithms are Asymmetric Key Encryption and Symmetric Key Encryption.
Mention the principles of Cryptography.
The four principles of Cryptography include Data Confidentiality, Data Integrity, Authentication, and Non-repudiation.
Conclusion
Overall, we understood Learning with the Errors using several examples. We also learned in brief about Lattice in Cryptography.
Visit our website to read more such blogs. Make sure you enroll in our courses, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations. Do upvote our blog to help fellow ninjas grow.
Happy Coding!
Live masterclass
Switch from service to product-based MAANG companies