Is the "secure-as-worst-case" version of NTRU patented? Does the improved version of NTRU — which is described in "Making NTRU as Secure as Worst-Case Problems over Ideal Lattices" by 
Stehlé and Steinfeld — fall under the same patents as the original?
I work for Security Innovation, which owns the NTRU patents. We think the NTRU patents would cover this algorithm too -- the patents are written broadly enough to cover different types of keys.

Note that although there are patents, we try to be reasonable about licensing terms. We have granted a free license for non-commercial use on many occasions and are currently exploring our options about licensing both the patents and a reference implementation under an open-source license. If you're interested in learning more, you can contact me directly on wwhyte@securityinnovation.com.