Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Lattice in Cryptography
3.
Learning with the Errors
3.1.
Regev Cryptosystem
3.2.
Decision Version
4.
Frequently Asked Questions
4.1.
Briefly explain DSA.
4.2.
Mention the importance of Encryption.
4.3.
Name the two types of Cryptographic Algorithms.
4.4.
Mention the principles of Cryptography.
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Learning with the Errors- Lattice in Cryptography

Author Rupal Saluja
0 upvote

Introduction

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.

notion of cryptography

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

(x^2 + 3^x + 1)(2x^2 + x − 4) = 2x^4 + 7x^3 + x^2 − 11x − 4

      = 2x + 7 + x^2 − 11x − 4

      = x^2 − 9x + 3

Now, we will use the vector of coefficients given below to represent the above polynomial in R.

Formula

Suppose we already have,

Formula

 

Formula

and

Formula

Using the above relations, we calculate that the coefficient of vectors has the relation c= a*b

Now, we have

Formula

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.

image explaining LWE

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,

Formula

The input to the LWE problem is a sample of pairs (x,y) where,

Formula

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 

Formula

 

We will choose a random subset S ⊆ {1, 2, . . . , m} to encrypt a one-bit message x. The cipher text y is given by

Formula

Compute the quantity given below to decrypt a cipher text.

Formula

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

Formula

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 

Formula

If the variable s is also involved in the calculation, use the relation

Formula

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 

Formula

4. Calculate the samples using the following equation.

Formula

5. Send the calculated samples to the decision solver.

6. If the guess k was correct, it is taken to the following distribution.

Formula

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. 

We hope the above discussion helped you understand the concepts of Learning with the Errors and Lattice in Cryptography and can be used for reference whenever needed. To learn more about Cryptography, you can refer to blogs on Security in CryptographySigning and Encrypting in CryptographyAuthenticated Encryption in CryptographyCBC MAC in Cryptography, and Message Authentication Codes 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