Talk:NTRUEncrypt

Cryptography: Computer science C‑class Mid‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography
C	This article has been rated as C-class on Wikipedia's content assessment scale.
Mid	This article has been rated as Mid-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Mid-importance).

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^12 bits for the public key, and 3*N*log2(p) =~ 2^10 bits for the private key if coefficients are in GF(p), or 3*N*log2(q) =~ 2^12 bits if coefficients are in GF(q). 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^11 bits). This is also suggested by DJB.

Can somebody clarify? Nageh (talk) 14:33, 3 June 2010 (UTC)[reply]

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 2
                   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,2}, 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)[reply]