Summary
Our work :
- We generalize the analysis of [NgRe06] for raw NTRUSign
- We successfully break all heuristic countermeasures
Impact :
- Dismiss heuristic approach and use Gaussian Sampling which is provably secure in the ROM.
On that topic : Faster Gaussian Sampling using Lazy-Floating
Point Arithmetic [DuNg12]. But this is another story...
Open Problems :
- Prove that zonotopes have no other local minima
- Provably secure countermeasure better than Gaussian Sampling