Closed hasufell closed 10 years ago
This seems to only happen if the polynomial f for the private key is of degree N - 1. If it is less, then it does not happen.
The problem is the following:
Random polynomials for encryption need to hold the following condition in order for the probability of unrecoverable messages to be less than e.g. 2^-80
:
q > (6 * d + 1) * p
where d is the amount of -1 and 1 in the random polynomial.
This suggests that the wikipedia article needs a fix.
Reference to the condition above is here: http://www.math.uni-hamburg.de/home/kuehn/moldenhauer-bsc-NTRUKryptosystem-final.pdf
best we can do is to provide checks for the parameters
Some encrypted polynomials don't recover properly with the following setup. Could be related to poly_starmultiply().