Scott Fluhrer edited section_Abstract_This_paper_shows__.tex  almost 9 years ago

Commit id: 7ea925874ebceb2edf6f604713b189f8b90438a5

deletions | additions      

       

Now, in practice, this attack would not generally appear to be a significant threat; in most cases, NTRUEncrypt will be used to pass symmetric keying data, and symmetric keying data has high entropy, making this attack infeasible.  \section{Key Recovery Attack}  The NTRU public key $H$ is the polynomial $F^{-1}G$ (computed over $\mod q$), where $F$ and $G$ are sparse polynomials. polynomials; the polynomial $F$ is the private key.  One way to try to recover the private key is to search for an $F$ such the product polynomial $FH$ is sparse. Now, the defined NTRU parameter sets work in one of two ways; in the straight-forward method, the key generation process selects a random polynomial whose coefficients consists of $F_r$ 1's, $F_r$ -1's, and the rest 0 (where $F_r$ is a parameter from the parameter set). The other method, known as the product form, has the key generation process select three polynomials $F_1, F_2, F_3$, and effectively sets $F = F_1F_2 + F_3$. Each of these polynomials $F_1, F_2, F_3$ is sparcer than the target $F$ polynominal; and computing $F_1(F_2H) + F_3H$ is faster than computing $FH$ directly.