Talk:NTRUEncrypt

{{WikiProject banner shell|class=C|

{{WikiProject Cryptography|importance=Mid}}

{{WikiProject Computing |importance=Low |software=yes |software-importance=Low |free-software=yes |free-software-importance=Low |science=yes |science-importance=Low}}

}}

Encryption example is wrong/incomplete

There is a serious flaw in the encryption example. The chosen random polynomial (the 'blinding value') has d = 3 coefficients which are 1 and -1. However, the following condition must hold true (outlined in this [http://www.math.uni-hamburg.de/home/kuehn/moldenhauer-bsc-NTRUKryptosystem-final.pdf bachelor thesis] ...unfortunately I currently don't have an english reference), otherwise the probability of unrecoverable messages will grow very large (and I was able to reproduce that in [https://github.com/hasufell/pqc/issues/2 my own implementation]):

$q\; >\; (6d\; +\; 1)p$

For the current random polynomial this will evaluate to:

$32\; >\; 57$

which is wrong.

For d = 2 we get:

$32\; >\; 39$

So, d = 1 seems the only way here (as in: one coefficient 1, one -1 and the rest 0). This additional condition is not anywhere in this article. It should be added and the example fixed, either by using d = 1 or changing the parameters altogether.

Hasufell (talk) 11:12, 1 June 2014 (UTC)

:A second similar reference to this issue can be found in this [http://teal.gmu.edu/courses/ECE646/project/reports_2001/dsouza.pdf work], describing the following situation: "The NTRU algorithm is actually probabilistic in nature; i.e. thereis a small chance of decryption failure. With the appropriate choice of parameters the decryption probability can be made to be on the order of 10 -25 or less."

:It suggests a table of different parameters, including the numbers of 1/-1 in f, g (the two random polynomials for key creation) and r (the blinding value). I'm still looking for a more mathematical explanation on why these parameters will lower the probability of unrecoverable messages.

:Hasufell (talk) 15:30, 3 June 2014 (UTC)

From the table:

Standard Security: N = 251, q = 128, p = 3

According to the article, the private key consists of f and f_p, both polynomials of size (at most) N-1, and "with coefficients much smaller than q, [...] and with coefficients in {-1,0,1}" (probably GF(p)) -- so which is it?

The public key is the polynomial h in GF(q).

This means you'd need roughly N*log2(q) =~ 2^11 bits for the public key, and 2*N*log2(p) =~ 2^10 bits for the private key if coefficients are in GF(p), or 2*N*log2(q) =~ 2^12 bits if coefficients are in GF(q). [http://bench.cr.yp.to/results-encrypt.html DJB] suggests that the private key is larger -- so... are the coefficients of f in GF(p), GF(q), or Z_n or what?

Furthermore, it seems that the memory requirements are quite comparable to RSA, at least for the public key (e.g., arguing that RSA-1024 is standard security it has a public key of 2^10 bits). This is also suggested by [http://bench.cr.yp.to/results-encrypt.html DJB].

Can somebody clarify?

Nageh (talk) 14:33, 3 June 2010 (UTC)

According to "An Introduction to Mathematical Cryptography," a book written by the three creators of NTRU, the "private key consists of two randomly chosen polynomials f(x)∈ T(d+1,d) and g(x)∈ T(d,d)", where d is a previously chosen integer of any size. The notation T(d+1,d) specifies the coefficients of the polynomial, where "T" stands for "ternary." A polynomial with ternary coefficients works like this:

T(d1,d2) = { a(x) has d1 coefficients equal to 1

a(x)∈ R: a(x) has d2 coefficients equal to -1

a(x) has all other coefficients equal to 0 }

So, as I understand it, f and g would have coefficients in {-1,0,1}, and the bit about "coefficients much smaller than q" is technically true, but irrelevant. There you have it, straight from the horse's mouth.

The23rd irishman (talk) 18:36, 1 December 2010 (UTC)