[6932] in cryptography@c2.net mail archive
Re: NTRU Public Key Cryptosystem
daemon@ATHENA.MIT.EDU (dmolnar)
Mon Apr 17 21:47:01 2000
Date: Mon, 17 Apr 2000 21:24:32 -0400 (EDT)
From: dmolnar <dmolnar@hcs.harvard.edu>
To: Joseph Silverman <jhs@ntru.com>
Cc: cryptography@c2.net
In-Reply-To: <l03010d47b52163a7e349@[38.32.11.167]>
Message-ID: <Pine.OSF.4.05.10004172116100.11997-100000@hcs.harvard.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
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
