Talk:NTRUEncrypt

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

The wrong ring??

Shouldn't the lead section say the ring is: R=Z[X]/(X^(N-1)) rather than R=Z[X]/(X^N-1) — Preceding unsigned comment added by Dannyniu (talk • contribs) 08:55, 25 October 2015 (UTC)

No, that's the right ring, X^N-1 is an irreducible polynomial modulus for the ring Hackcasual (talk) 19:12, 7 January 2016 (UTC)

X^N-1 is not irreducible, since (X-1) divides it. — Preceding unsigned comment added by 217.72.104.76 (talk) 05:07, 10 May 2018 (UTC)

External links modified (February 2018)

Hello fellow Wikipedians,

I have just modified 4 external links on NTRUEncrypt. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Corrected formatting/usage for http://www.securityinnovation.com/security-lab/crypto/155.html
• Added archive https://web.archive.org/web/20071021011338/http://www.ntru.com/cryptolab/pdf/ANTS97.pdf to http://www.ntru.com/cryptolab/pdf/ANTS97.pdf
• Added archive https://web.archive.org/web/20071021093455/http://www.ntru.com/cryptolab/pdf/NTRUTech004v2.pdf to http://www.ntru.com/cryptolab/pdf/NTRUTech004v2.pdf
• Added archive https://web.archive.org/web/20071021011147/http://www.ntru.com/cryptolab/pdf/TECH_ARTICLE_OPT.pdf to http://www.ntru.com/cryptolab/pdf/TECH_ARTICLE_OPT.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 01:28, 11 February 2018 (UTC)

Should the statement "which is not known to be breakable using quantum computers" be removed?

A paper published in Dec 2022 uses the QAOA to optimize Babai's algorithm for solving the CVP in a given lattice. This algorithm can be used to solve SVP (the CVP is a generalisation of the SVP) but I'm unsure as to whether an edit should reflect this since no paper has explicitly outlined a solution for SVP using a quantum computer yet.

Also, is the word "breakable" ambiguous or even applicable here? The problem can be solved just not in polynomial time. I'm unsure as to whether "breakable" actually applies to a mathematical problem and if it does, if it is the correct word to use here.

Cheers. TheRift Wiki (talk) 22:17, 9 February 2023 (UTC)