Editing NTRUEncrypt (section)

==Security and performance improvements==

Using the latest suggested parameters (see [[#Table 1: Parameters|below]]) the NTRUEncrypt public key cryptosystem is secure to most attacks. There continues however to be a struggle between performance and security. It is hard to improve the security without slowing down the speed, and vice versa.

One way to speed up the process without damaging the effectiveness of the algorithm, is to make some changes in the secret key '''f'''.
First, construct '''f''' such that <math> \ \textbf{f} = 1+p\textbf{F} </math>, in which '''F''' is a small polynomial (i.e. coefficients {-1,0, 1}). By constructing '''f''' this way, '''f''' is invertible mod  ''p''. In fact <math> \  \textbf{f}^{-1} = 1\pmod p </math>, which means that Bob does not have to actually calculate the inverse and that Bob does not have to conduct the second step of decryption. Therefore, constructing '''f''' this way saves a lot of time but it does not affect the security of the NTRUEncrypt because it is only easier to find <math> \ \textbf{f}_p </math> but '''f''' is still hard to recover.
In this case '''f''' has coefficients different from -1, 0 or 1, because of the multiplication by ''p''. But because Bob multiplies by ''p'' to generate the public key '''h''', and later on reduces the ciphertext modulo ''p'', this will not have an effect on the encryption method.

Second, '''f''' can be written as the product of multiple polynomials, such that the polynomials have many zero coefficients. This way fewer calculations have to be conducted.

According to the 2020 NTRU NIST submission <ref>{{Cite web |title=NIST-PQ-Submission-NTRU-20201016.tar.gz |url=https://ntru.org/release/NIST-PQ-Submission-NTRU-20201016.tar.gz}}</ref> the following parameters are considered secure:

===Table 1: Parameters===
{| class="wikitable"
|-
! 
! '''N'''
! '''q'''
! '''p'''  
|-
| 128 bit security margin (NTRU-HPS)			
| 509
| 2048
| 3
|-
| 192 bit security margin (NTRU-HPS) 			
| 677 
| 2048 
| 3 
|-
| 256 bit security margin (NTRU-HPS)	 		
| 821 
| 4096 
| 3 
|-
| 256 bit security margin (NTRU-HRSS) 
| 701 
| 8192 
| 3 
|}