[This is very salesy, but there is enough meat that I'm forwarding it
anyway. --Perry]
>From: "Salz, Rich" <[EMAIL PROTECTED]>
>To: "'[EMAIL PROTECTED]'" <[EMAIL PROTECTED]>
>Subject: www.ntru.com
>Date: Tue, 11 Apr 2000 13:53:06 -0400
>Sender: [EMAIL PROTECTED]
>
>I forget -- has NTRU been discussed here? In light of the recent Fortune
>article, someone mentioned http://www.ntru.com to me. A new fast public
>key crypto system. Just got $11M in funding. :)
Hi, Rich,
There has been discussion of NTRU on sci.crypt, but I'm not sure if
we've been mentioned on this mailing list. Let me first introduce myself.
My name is Joe Silverman, VP for R&D at NTRU Cryptosystems. With Jeff
Hoffstein and Jill Pipher -- all of us members of the Mathematics faculty
at Brown University -- I'm also one of the inventors of NTRU.
NTRU is indeed a fast public key cryptosystem, but it is not all
that new. It was first announced at the Crypto '96 rump session, where Jeff
Hoffstein distributed numerous copies of our paper giving the complete
details of the algorithm. At Crypto '96, and thereafter, we have received
critical feedback from many cryptographers, including many of the top
people in the field, which we used to establish NTRU's parameters and
define appropriate security levels for our commercial cryptosystem.
I want to stress that a full detailed description of the NTRU
algorithm has been available for analysis by the cryptographic community
since 1996; and that it has been the subject of much study. This is in
marked contrast to some companies that have tried to sell "secret"
cryptographic algorithms. It is generally accepted that no cryptographic
algorithm can be considered secure until it has been subject to public
scrutiny by the cryptographic community.
Our technology is new in the commercial OEM world, but we have been
actively developing it, exploring its architectural implications, and
debating its importance in academic and professional forums for a much
longer period. Obviously, there are alternative PKCs which are better known
and which have some advantage in the sheer number of years they have been
studied. On the other hand, NTRU offers some extraordinary performance
characteristics which many hope will open up wholly new markets for
crypto-enhanced products and services.
After four years of intense and welcome scrutiny of NTRU by many
querilous and skeptical cryptographers, we (and others) have also grown
increasingly confident in our algorithm.
NTRU picked up an early supporter in Sony Corporation, which
invested in our initial development venture two years ago. Last week --
after an extended evaluation of our technology -- Sony chose to
significantly expand its equity investment in NTRU in our second round of
financing.
(In addition to its prominent role in consumer electronics, Sony is
also a pioneer in home networking and owns one of the world's largest
libraries of copyrighted multimedia. I'm doubtless a little biased, but I
believe Sony has a very sophisticated grasp of the potential demand for
crypto with NTRU's unique mix of performance characteristics, configuration
options, and power requirements.)
The recent Fortune article cited above describes an apparently
failed commercial crypto venture, TriStrata, from the point of view of its
venture capitalists. According to the article, TriStrata's VCs invested
millions without even an independent (let along public) peer review of
TriStrata's proprietary and unpublished cryptography. I suspect this is a
fairly rare occurance;-) NTRU's recent experience with our leading VCs --
Sony and Greylock -- was quite different, I assure you.
We have a lot of technical data on our web site, including my FAQ
on NTRU's performance characteristics
<http://www.ntru.com/tech.learning.faq.htm#Why is NTRU fast>;
tutorials describing the NTRU algorithm at some depth; details of the NTRU
Challenge problems; and information about the Tumbler SDK developed by the
Tao Group, Ltd., in the UK. (We are now developing a VHDL implementation of
NTRU, adapted for efficiency in silicon.)
I'm not sure how much information the List would like on the
security of NTRU, and I don't want to impose, so I will just make a few
additional comments.
Anyone who studies our technology quickly realizes that NTRU is
very fast, very easy to implement, and has a very small footprint. To bring
home this point, some of our advertising declares that NTRU is "100 times
faster than other leading systems." Let me forestall some likely criticism
and acknowledge now that a headline like this is obviously an
oversimplification, since different security levels and different protocols
will have different operating characteristics. (I append below two notes
from my recent private exchange with David Wagner concerning NTRU's claims
and their potential implications. David has given me permission to post his
comments.)
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. Among those who have studied NTRU are
many of the leading world experts in the study of lattices and their uses
in cryptography. Their results have been very positive. For example, let me
offer a brief quote from the preprint on "Lattice Reduction in Cryptology"
which Jacques Stern and Phong Nguyen are planning to present at the ANTS IV
conference (July 3-7, 2000, Leiden):
>Note that the keysize of NTRU...makes NTRU the leading candidate
>among latticed-based cryptosystems. It seems that better attacks
>or better lattice reduction algorithms are needed to break NTRU.
>To date, none of the numerical challenges (on the NTRU web site)
>has been solved."
In other words, no known algorithm or attack can break even the
lowest security level of NTRU. Of course, this does not preclude someone
from coming up with a radically new attack or with some huge improvement on
current lattice methods, but the same can be said of RSA (any huge
improvement in factorization would be dangerous) and ECC (any huge
improvement in solving the elliptic curve discrete logarithm problem would
be bad).
NTRU Cryptosystems is obviously still a startup, just beginning to
explore the commercial potential of our technology, but the founders of
NTRU are professional cryptographers and mathematicians who have worked for
years to establish a firm technical foundation for NTRU. A foundation we
are confident is today worthy of the trust some OEMs and commercial
developers have already placed in our cryptosystem.
Yours truly,
Joe Silverman <[EMAIL PROTECTED]>
VP - Research and Development
NTRU Cryptosystems, Inc. <http:// www.ntru.com>
-----------------------------------------------------------------
Mr. Wagner's Comments:
Subject: Re: NTRU Public Key Cryptosystem
To: [EMAIL PROTECTED] (Joseph Silverman)
Date: Thu, 24 Feb 2000 21:22:37 +0000 (GMT)
From: "David A. Wagner" <[EMAIL PROTECTED]>
I agree that it is important to consider both encryption,
decryption, and key generation. In trying to understand the performance
numbers of other systems, I've found that looking at only one of those
factors or lumping them all together leads to less-than-total appreciation,
for many public-key systems have particular niches where they will beat all
competition, e.g.,
RSA: best at encryption (SSL clients?) or verification (verifying long cert
chains?) heavy workloads
El Gamal, DSA: best for fast signing, if you can afford precomputation
elliptic curves: hard to beat for low-bandwidth, low-power, or
otherwise-constrained low-end devices
Diffie-Hellman: fast key generation (where forward secrecy is important)
When you know about these niches and where the various
cryptosystems excel, you can often design a protocol to take advantage of
all these strong points to maximize performance.
I guess when reading the NTRU web site I was hoping to get a feel
for where NTRU fell into this space. The sense I am getting is that NTRU is
probably best thought of as a general-purpose public-key cryptosystem: it
may not beat any of the above on their home turf, but it achieves
simultaneously the best of most of the above (in terms of performance) in a
single cryptosystem. i.e., NTRU-verification may not be faster than
RSA-verification, but it's a lot faster than RSA-signing; NTRU-signing may
not be faster than DSA-signing with precomputation, but NTRU-verification
is a lot faster than DSA-verification; etc. I don't know if that's accurate
or if that matches your perspective, but it is representative of the sort
of information I was trying to tease out of the website.
I do recognize the need to summarize these complicated issues in a
short soundbyte for the consumer without the time or interest to delve more
deeply. That said, I must admit I still view the unqualified 100x claim as
not really telling the whole story, although of course not everything in
the world is intended to be interpreted in a rigorous careful scientific
context.
Thanks for the detailed note! I'm grateful for NTRU Inc.'s
commitment to openness; I think it says good things about the company. I
wish you the best of luck in future endeavors. May the best public-key
cryptosystem win!
-- David
P.S. Feel free to post this note if you like.
------------
Subject: Re: NTRU Public Key Cryptosystem
To: [EMAIL PROTECTED] (Joseph Silverman)
Date: Fri, 25 Feb 2000 01:31:40 +0000 (GMT)
From: "David A. Wagner" <[EMAIL PROTECTED]>
Actually, those vague niche assignments were ignoring the existence
of NTRU, since I don't understand NTRU's performance characteristics too
well. But from what I've seen so far it looks quite plausible to me that
NTRU is as fast as each of today's popular cryptosystems on their home turf
(i.e., not any slower in any case, and often faster in many scenarios), so
if NTRU is as secure as the competition there would not be much point in
keeping around all the specialty niche-oriented cryptosystems. If this is
right, it would force one to totally revise the picture I drew -- the
niche-oriented systems would become irrelevant. But that's just a guess --
I haven't looked closely enough at the performance numbers to know for sure
whether that's an accurate summary of the situation.
Regards,
-- David
