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- 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

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.

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.

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= (h_{0}, h_{1},....., h_{N-1}) and lattice L_{h} whose basis consists of the rows of the 2N x 2N matrix given below.

The lattice L_{h} contains the vectors: L_{h} = {(a, b) âˆˆ Z^{2N} : 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) âˆˆ L_{h}.

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:

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

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.

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.