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.
Security of NTRU
4.
Frequently Asked Questions
4.1.
Mention the importance of Encryption.
4.2.
Describe the Blind Signature Scheme.
4.3.
Define Confidentiality.
4.4.
Why do we use Cipher?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Lattices and the Security of NTRU

Author Rupal Saluja
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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- Security of NTRU. 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 the 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.

Lattice in Cryptography

Suppose we already have,

Lattice in Cryptography
Lattice in Cryptography

and

Lattice in Cryptography

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

Now, we have

Lattice in Cryptography

This equation and the relation will be used to find a solution for the polynomial.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Security of NTRU

We already learned that security of NTRUEncrypt is based on certain lattice problems. NTRUEncrypt is the fastest known lattice-based encryption scheme. It offers moderate key-sizes, great asymtotic performance and efficient resistance to quantum computers. It is considered as the most preferred alternative to discrete log-based encryption and factorisation schemes. However, it is believed that its security could be better.

The practical security of any public key cryptosystem can only be estimated by the most effective known attack against it. 

notion of security

One way to break the NTRUEncrypt is to compute the polynomials f(x) and g(x) used to construct the public key h. Denote h= (h0, h1,....., hN-1) and lattice Lh whose basis consists of the rows of the 2N x 2N matrix given below.

Security of NTRU

The lattice Lh contains the vectors: Lh = {(a, b) ∈ Z2N : a * h = b}

From the way h is constructed, we have: f * h ≡ g mod q where, f and g are coefficients of f(x) and g(x) respectively. This means: f * h − g = q t

for any integer t. Now, it is very simple to compute: (f, −t)M = (f, g) so that (f, g) ∈ Lh.

In addition, the vector (f,g) has a small norm because all of its coefficients are in the same set {−p, −1, 0, 1, p}. More specifically, (f,g) has roughly N/3 coefficients equal to each of −p, −1, 1, and p. The remaining 2N/3 coefficients are equal to 0. So, the norm of (f,g) approximately becomes:

Security of NTRU

Since a vector of length 2N whose coordinates take on random values in [−q/2, q/2] would have a norm approximately equals to:

Security of NTRU

which is much larger.

 

Another way to break the NTRUEncrypt is by using good lattice reduction algorithm. For the standard NTRU parameters, it is estimated that the attacks based on the lattice reduction requires great strength. So, you can imagine a new concept in lattice reduction becoming the most effective known attack against NTRU. The only problem with estimating the running times of lattice reduction algorithms is that they often behave far better than one can imagine. To handle this, NTRU can run a series of tests and extrapolate the data in a conservative manner.

Frequently Asked Questions

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.

Describe the Blind Signature Scheme.

The phenomenon of hiding the message’s content of digital signature before it is signed is known as Blind Signature Scheme. This happens when message author and signer are complete different stakeholders.

Define Confidentiality.

Confidentiality is the term used to describe the level of secrecy of data. If the data is highly-confidential, only the sender and receiver can access the message exchanged between them.

Why do we use Cipher?

Cipher is an algorithm that transforms plain text into cipher text by two methods- Substitution and Transposition.

Conclusion

Overall, we understood the aspects of Security of NTRU. 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!

Previous article
Let’s Expand the Acronym NTRU
Next article
Learning with the Errors- Lattice in Cryptography
Live masterclass