Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 0 down vote favorite

I'm trying to implement NTRUEncrypt but encounter some problems. I've finished all the basic functions that are needed for the scheme base on this Document, but I can't find an algorithm to check the validity of the initial polynomial f.

If f is not qualified (inverse mod p or inverse mod q doesn't exist) then the function to calculate the inverse modulo would end up in an infinite loop.

I've found some documentation about ntru con the ntru's website but there are too many of them and I don't have the time to go through them all. If anyone can help me with the algorithm or point out the document that I should read, that'd be helpful.

share|improve this question

1 Answer

up vote 0 down vote accepted

So long the GCD of f(1) with p and with q is 1, f will have an inverse with high probability. (f(1) = f evaluated at 1, i.e. the sum of the coefficients of f).

If you take f to be binary with df 1s, then take df to be relatively prime to p and q.

If you take f to be trinary and it has df 1s and df-1 -1s, then f(1) = 1 and this will satisfy the GCD requirement identically.

If you take f to be of form 1 + pF, f(1) is 1 mod p and satisfies that requirement identically. For the GCD requirement mod q, either pick F to be trinary with equal +1s and -1s (so f(1) = 1) or pick F to be binary such that 1 + p*F(1) is relatively prime to q.

"High probability" above means that the probability of not having an inverse goes down rapidly as both q and N increase. I've posted toy examples on Stack Overflow (http://stackoverflow.com/questions/2754444/meet-in-the-middle-atack-on-an-ntru-private-key) and when I generated them I came up with invertible keys on the first attempt for N = 11, q = 29.

share|improve this answer
Wow, thank you, that was a very detailed answer. But just to be clear, df is the number of ones in the polynomial, right? – FljpFl0p May 16 '12 at 18:13
One more thing I need to ask: Is there any requirement for r, g and m? Currently I'm generating those polynomials randomly (they're all trinary) and the failure rate is extremely high – FljpFl0p May 17 '12 at 8:39
For binary, df is the number of 1s; for trinary with "flat" f, you have df 1s and df-1 -1s (or you could define df so that there are df+1 1s and df -1s, it doesn't matter much); for trinary with form 1+pF, you have df +1s and df -1s. – William Whyte May 17 '12 at 14:27
What about r, g and m? I'm tried N = 167, q = 128, p = 3 and half of the time the decryption failed. – FljpFl0p May 17 '12 at 17:38
If p = 3 then you're using trinary, so let's say that r, g and m have dr, dg, dm +1s and -1s respectively and f has df +1s and (df-1) -1s. To avoid decryption failures altogether you need p*2dr*2dg + (2df-1)*2dm < 128, so df, dm, dr, dg all need to be around sqrt(128) or, basically, 11. If you're taking them much larger than this you'll see significant numbers of decryption failures. You want to be able to take df etc to be around N/3. If you take q to be the power of 2 above (N^2)/9 you will certainly have no decryption failures. Lower values of q give you some risk. – William Whyte May 19 '12 at 2:36
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.