On Mon, 17 Apr 2000, Joseph Silverman wrote:
Hi,
> The hard problem underlying the NTRU cryptosystem is called the
> "Shortest Vector Problem" (or SVP), which is the problem of finding the
> shortest nonzero vector in a lattice.
Is it known how tightly related NTRU is to the shortest vector problem? Is
there a reduction known yet from SVP to NTRU, or is it still in a
position analagous to RSA and factoring?
Not that a reduction would necessarily be a good thing, as Ajtai and Dwork
found out the hard way... :-)
Seriously, is anything known about how "good an approximation" would be
needed to break NTRU? Apologies if this is already answered in the
Coppersmith paper or someplace else; just point me there.
Thanks,
-David Molnar
