Lattices and the Security of NTRU

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₀, h₁,....., 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. 

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 Cryptography, Signing and Encrypting in Cryptography, Authenticated Encryption in Cryptography, CBC 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!