|
|
|
|
|
|
|
|
|
|
  Standards
Performance
Security
Fundamentals Standards What is the current status of NTRUEncrypt within standards bodies? The main forum for standardizing the NTRU algorithms is the Consortium for Efficient Embedded Security (CEES). This is a multi-vendor body, with members such as Texas Instruments, Microsoft, and Sony [RSA is not a member - they were just a sponsor of the event we hosted last June.] as well as NTRU, which is considering appropriate security solutions for highly constrained devices. Its first standard, Efficient Embedded Security Standard (EESS) #1, is the canonical definition of how to implement the base NTRU algorithms for interoperability. We will shortly begin work on a document in the ANSI X9 working group. This will position us to be considered for adoption in the appropriate FIPS standards when they come up for review. We are progressing documents in the IETF PKIX and TLS working groups. In the PKIX group, the NTRU algorithms are being included in the Internet Draft on Supplementary Algorithms For PKIX. This draft standardizes not just NTRUEncrypt, but also the new versions of the Digital Signature Standard (DSA) and the hash algorithms SHA-256, SHA-384, SHA-512, and is expected to become a standards track document. The TLS working group is considering an Internet Draft on NTRU Ciphersuites for TLS. We are active in the WAP forum, working mainly at the application layer rather than the transport layer. We intend to submit a CR to include NTRUEncrypt and NTRUSign in the SignText and EncryptText WMLScript API when the group considers it appropriate. We are also under consideration for use in WIM. We have been very active in the IEEE 802.15.3 and 802.15.4 standards groups; we were the main authors of the security text for the current 803.15.3 draft documents. We have also submitted NTRUEncrypt to the Japanese Cryptrec process for consideration for adoption by the Japanese e-Government project, and are active members of numerous other standards bodies and working groups. Is NTRUEncrypt being reviewed by standards bodies? When will NTRUEncrypt be adopted as a standard? What is the purpose of cryptographic standards? What is the difference between a "proprietary" system and a "standard" one? The key to such market acceptance is often the uniqueness of the proprietary solution and the willingness of the technology owner to license its technology to other companies, not just to end users. NTRU is committed to a reasonable and nondiscriminatory licensing policy and is aggressively pursuing licensees through CTT, its marketing partner in the United States, and Tao Group, its global distributor. NTRUEncrypt, with its high speed and disposable keys, is not merely the best solution for many customers, it is the only solution for many market segments, in particular for applications on low powered computing devices and those requiring very fast key generation. Note that "proprietary" does not mean "secret." NTRUEncrypt's algorithms are published and have been studied by the cryptographic community for many years. Performance Why is the NTRUEncrypt Public Key Cryptosystem so fast? Why is NTRUEncrypt so much faster than RSA, El Gamal, and ECC? (A non-technical overview) A private key for any cryptosystem can be thought of as a long list of bits, for example By way of contrast, NTRUEncrypt breaks the key up into small chunks, generally consisting of 7 or 8 bits each. For example, A careful mathematical analysis shows that for keys consisting of around N bits, the RSA, El Gamal, and ECC systems require on the order of N3 operations to encrypt or decrypt a message, while NTRUEncrypt requires only on the order of N2 operations to encrypt or decrypt a message. The tremendous difference between N3 and N2 can be clearly seen in the timing comparisons between NTRUEncrypt, RSA, and ECC. [Technical Addendum: The above description is highly oversimplified. In practice, use of fancy techniques (Fast Fourier Transforms, Karatsuba Multiplication, etc) will increase RSA and ECC efficiency to N2*log(N) operations and increase NTRUEncrypt efficiency to N*log(N) operations. NTRUEncrypt retains its order of magnitude advantage.] What performance figures do you have for NTRU Encryption, Decryption, Signing, Verification and Key Generation relative to RSA and ECC (for equivalent of 1024 and 2048 RSA)? Here are the benchmarks for NTRU-251 against RSA 1024 and ECC over GF (2^163): NTRU-251 v RSA-1024 on 800 MHz Pentium III:
NTRU-251 vs RSA-1024 on Palm V
(RSA public exponent is Fermat-4 prime = 0x010001 = 65537). NTRU-251 vs ECC over GF (2^163) on 800 MHz Pentium III:
NTRU-251 vs ECC over GF (2^163) on Palm:
The Pentium benchmarks were obtained from Wei Dai's Crypto++ benchmarks (http://www.eskimo.com/~weidai/benchmarks.html). The Palm benchmarks were obtained from published results (RSA due to Dan Boneh of Stanford University, ECC due to Certicom). In all cases, we have taken the RSA public exponent to be 65537 = 0x010001, as this is common practice (in fact, some software will only accept RSA public keys with this exponent). The following figures compare the performance of NTRU-347 to RSA 2048 on an 800 MHz Pentium III. The NTRU-347 figures are extrapolated from the NTRU-251 figures. The RSA figures are from Wei Dai's Crypto++ benchmarks, referenced above. NTRU-347 v RSA-1024 on 800 MHz Pentium III:
How do we measure and compare the speeds of NTRUEncrypt, RSA and ECC? Statements like Cryptosystem XXX is 100 times faster than Cryptosystem YYY are meaningless without additional information. Unfortunately, the marketplace insists on succinct quantitative comparisons, so we and our competitors frequently publish these sorts of statements. To be accurate, three issues need to be addressed: Implementation Another important application that more than justifies our claim to a 100x speed advantage is through the use of disposable keys. For example, NTRUEncrypt is currently being implemented in a commercial product that will generate a new public/private key pair for each few seconds of audio and use that pair to encrypt and decrypt a symmetric key for that piece of audio. So in this real world situation, a single application of the public key cryptosystem consists of three operations: Generate Key / Encrypt One Block / Decrypt One Block If we compare NTRUEncrypt N=263 with RSA 1024 in this situation, we find that NTRUEncrypt is far more that 100 times faster. Indeed, NTRUEncrypt key pair generation takes about 3.0 milliseconds, while Crypto++ takes over 1 second to generate an RSA key pair (on our 300 MHz machines), so the NTRUEncrypt speed advantage tops 300. What Is Being Measured Comparable Security For example, the current recommendation for RSA medium term security is RSA 1024. The equivalent security level for NTRUEncrypt is provided by NTRUEncrypt 263. Long term RSA security requires using RSA 2048, and a much higher security level (closer to RSA 4096) is provided by NTRUEncrypt 503. (In comparing NTRUEncrypt 503 to RSA 2048, we are simply being extra conservative in our security evaluation.) Keeping the above remarks in mind, the following table gives timing comparisons for NTRUEncrypt and RSA at comparable security levels.
However, even a seemingly precise table like this one requires notes explaining where the figures come from and how they were derived. Here is a list of footnotes to accompany the above table: How do "low exponents" make RSA encrypt faster? The RSA cryptosystem involves repeated multiplication in the group of numbers modulo p. Thus encryption requires taking a certain element g of the group and computing gk, and then decryption involves taking another element h and computing hn. In order to make encryption faster, sometimes people take the encryption exponent k to be very small. Typical examples of encryption exponents that people use are k=3 or k=17=24+1 or k=216+1=65537. Don Coppersmith has shown that the use of a very small exponent such as k=3 is probably not a good idea, at least for unpadded RSA messages. D. Coppersmith, Small solutions to polynomial equations and low exponent RSA vulnerabilities, Journal of Cryptology 10 (1997), 233-260. However, if the message is padded (as is generally the case), then many cryptographers feel that using k=3 is fine. (The Crypto++ benchmarks use exponent k=17.) Note that although it may seem like there is a tremendous difference between using k=3, k=17, and k=65537, the use of repeated squaring means that the difference is not that great. Thus g3 requires 2 multiplications, g17 requires 5 multiplications, and g65537 requires 17 multiplications, so taking k=3 makes encryption about 8.5 times faster than taking k=65537. Important Note: The above discussion applies only to the exponent used for encryption. The exponent used for RSA decryption is always very large and requires hundreds of multiplications. How do special curves make ECC run faster? The initials ECC stand for "elliptic curve cryptosystem." An elliptic curve is a complicated mathematical object consisting of points that can be "added" to one another. An elliptic curve cryptosystem is formed from a field F, an elliptic curve E and a point P on the elliptic curve. Encryption and decryption require repeated addition of P to itself P+P+...+P. (This is analogous in some ways to RSA encryption, which requires repeated multiplications g*g*...*g. However, RSA multiplications are much simpler than elliptic curve "additions".) There are certain special types of fields F and elliptic curves E for which the addition operation can be performed especially efficiently. Some of these special types have been found to be insecure (e.g. "supersingular" elliptic curves, Galois fields with many subfields), but there are other special types that appear to be secure and that offer some speed advantages. Using ECC thus requires choosing one of the following two options: Choose a new elliptic curve for each transaction (or for each few transactions). This takes a large amount of time (compared to, say, creation of a new NTRUEncrypt key), but may offer additional security because it creates many targets. All speed and footprint advantages of ECC over RSA (for example) are negated unless you are comfortable with fixing one elliptic curve and using it for many transactions. At present, this appears to be as secure as choosing a random elliptic curve for each transaction, provided the fixed elliptic curve is chosen carefully. What benchmarks do you have that show feasibility of NTRUEncrypt running on an 8051 card without a co-processor? encrypt: 214,000 cycles (107 ms) Much of this code is written in C, and we expect these figures to improve. Also, note that encrypting and decrypting with the standard NTRU formatting method requires five calls to SHA-1 when encrypting and four when decrypting, and these calls are included in the figures above. The figures for raw encrypt/decrypt are: Encrypt: 47,000 cycles (23.5 ms) Will NTRU work on a 16-bit card? Yes, NTRU algorithms are suited for any environment. NTRUEncrypt is unique among asymmetric cryptosystems in that it can be implemented on any processor, even 8-bit processors, without requiring a co-processor. Security Will NTRU work on a 16-bit card? The NTRUEncrypt Public Key Cryptosystem is based on the hard mathematical problem of finding very short vectors in lattices of very high dimension. The process of solving this problem is called "Lattice Reduction", and the general study of small vectors in lattices goes by the name "Geometry of Numbers". This subject has a long history due to its importance in a variety of areas of mathematics (both pure and applied) and physics. For example, in 1880 Hermite proved an upper bound for the length of the shortest vector in a lattice, and in 1896 Minkowski gave an important criterion for when a symmetric convex body must contain a nonzero lattice vector. (This is the same Minkowski responsible for the formulation of space-time in relativity.) Minkowski also gave the subject its name in his book Geometrie der Zahlen (Geometry of Numbers), published in Leipzig in 1910. The geometry of numbers has flourished as a mathematical field. A standard reference is Lekkerkerker's Geometry of Numbers (John Wiley, NY, 1969), a massive 510 page volume with a 32 page bibliography. When Lekkerkerker was updated (Elsevier, 1987), it grew to 732 pages with a 93 page bibliography. As a further indication of the importance of lattices in modern mathematics, a search of Mathematical Reviews found over 14,000 articles published between 1986 and 1999 that have the word "lattice" in their title. Although not all research on lattices is directly relevant to cryptography, there is no question that lattices are a fundamental object of study in algebra, geometry, analysis, and physics. With the advent of modern computers, attention turned to the practical problem of finding short vectors in lattices. One can always find the shortest nonzero vector by an exhaustive search, but the search space grows exponentially in the dimension of the lattice, so people looked for better methods. The most important modern advance in the algorithmic theory of lattice reduction is the method discovered by Lenstra, Lenstra and Lovasz and dubbed LLL. The LLL algorithm finds a moderately small vector in polynomial time, but it will generally not find the smallest vector. There have been a number of improvements, mostly of a combinatorial nature, to the LLL algorithm due to Schnorr, Euchner, and others. These improvements go by names like "deep insertions", "block reduction", "pruning". But the problem of finding the smallest vector in a general lattice remains an exponentially hard problem using even the best known algorithms. It is worth observing that LLL was invented BEFORE lattices became important in cryptography. LLL has numerous applications in signal processing, combinatorics, computer algebra, algebraic number theory, Diophantine equations, and physics, as well as cryptography. To indicate the widespread interest in LLL and computational lattice reduction, we note that the original LLL article was cited in more than 145 research articles between 1986 to 1999, the LLL algorithm is included in many computer packages (Mathematica, Maple, Pari, Simath, NTL, ...), and the LLL algorithm is featured in numerous books. Important Disclaimer We cannot prove that breaking NTRUEncrypt is as hard as finding a shortest vector in a general lattice. All we can assert is that the best method anyone has found for breaking NTRUEncrypt involves finding the shortest vector in certain lattices of high dimension, and that experiments indicate that known lattice reduction methods are incapable of breaking NTRUEncrypt if one uses the suggested parameter sets. Notice the similarity with RSA. No one knows if breaking RSA in general is equivalent to the general problem of factoring large numbers; and even if they are equivalent, it may still be possible that some numbers are easier to factor than others, so some particular RSA keys may be weak. Has NTRUEncrypt been reviewed by the cryptographic community? Since its introduction at Crypto '96, NTRUEncrypt has been subject to constant scrutiny by top cryptographers, including a EuroCrypt '97 security analysis by Adi Shamir and Don Coppersmith. NTRUEncrypt has been publicly presented at top cryptographic conferences, has been described through publication in refereed journals and conference proceedings, and has been reviewed by outside experts. How is the security of NTRUEncrypt measured? The hard problem underlying the NTRUEncrypt Public Key Cryptosystem is that of finding a very short vector in a lattice of very high dimension. The best way known to attack NTRUEncrypt is to use the LLL lattice reduction method to search for the target vector. In order to test the security of NTRUEncrypt, we used LLL to run numerous tests on NTRUEncrypt lattices of various dimensions and graphed the amount of time it took to find the target vector. From this graph we extrapolated the running time for lattices of higher dimension and used these figures to select appropriate parameters for NTRUEncrypt. The following table gives estimated breaking times for NTRUEncrypt and RSA at various security levels. (Times are rounded to the nearest 10 MIPS-years.)
NTRUEncrypt experiments were done using the implementation of LLL in Victor Shoup's highly regarded NTL package and run on 400 MHz Celeron processors operating under Linux. The security levels and estimated breaking times for RSA are taken from the P1363 draft standards. Our discussion of security in this FAQ is of necessity brief and somewhat sketchy. For complete details, including experiments and a full security analysis, see the papers and technical notes at our Technical Center. A MIPS-year is the number of operations performed in one year by a computer that is capable of performing one million instructions per second. Roughly speaking, a single 400 MHz computer does about 400 million instruction per second (one instruction per clock cycle), so it is a 400 MIPS machine. According to the above table, it would have to run for about 1012/400 years (that's about 2,500,000,000 years) to break an RSA 1024 bit key. So if you could harness the power of one million 400 MIPS machines, they would still require 2500 years to break a single key. Why is the NTRUEncrypt Public Key Cryptosystem more secure than earlier lattice based systems, such as knapsack systems, that have been broken? The original collection of cryptosystems broken by lattice reduction were those based upon variations of the knapsack problem. As each new variation appeared, hopeful authors did everything in their power to avoid potential transformations of their "hard problem" into one that could be attacked by lattice reduction. As the survey article by Odlyzko describes, no matter how obscured the original problem was, it still always proved in the end to be possible to transform it into one vulnerable to LLL lattice reduction methods. The last one to bite the dust was the Chor-Rivest system, broken by Schnorr's recent improvements to the LLL algorithm. One of the fundamental problems these authors faced was the fact that the key size of their system grew with the square of the dimension of the lattice used for an attack. Because of this, it was impossible to make the dimension of an attack lattice greater than a couple of hundred without simultaneously making the cryptosystem impractical. Developments in LLL technology by Schnorr, Euchner, and others now allow lattices of dimension 200 or less to be analyzed in a short amount of time, and even certain lattices of dimension up to 300 can occasionally be broken. This is enough to dispose of all proposed practical knapsack systems. It was also enough to dispose of the lattice based system proposed in 1997 by Goldreich, Goldwasser and Halevi. The GGH system also had a key size which grew with the square of the lattice dimension, and thus either the lattice was too small for security or the key size was too large to be practical. One important point of the NTRUEncrypt cryptosystem is to make the underlying lattice problem perfectly clear and straightforward from the outset. Thus unlike the knapsack cryptosystems, there is no question of trying to prevent the use of lattice reduction methods. A second crucial point for the NTRUEncrypt cryptosystem is that the key sizes are linear in the dimension. This means that it is easy to set up an NTRUEncrypt cryptosystem with practical key sizes (and blinding speed) which nevertheless relates to a lattice problem of dimension 500 to 1000. Current LLL techniques are completely incapable of dealing with lattice problems of this size. Expanding on this last point, developments in LLL technology have been similar to, but somewhat less advanced than, advances in the problems of factoring large integers or finding discrete logarithms. For example, the number field sieve is a very sophisticated method of factoring which uses advanced mathematical ideas to solve the factorization problem in subexponential time. Improvements in LLL technology by Schnorr, Euchner and others have been at a simpler, more combinatorial, level. Their innovations have improved the efficiency of the LLL algorithm, but they still leave the breaking time at least exponential in the dimension. At NTRUEncrypt Cryptosystems we have taken the best LLL technology available today and applied it to the problem of breaking the lattice problems associated to the NTRUEncrypt cryptosystem. We have extrapolated out breaking times in much the same way that factoring attacks have been used to extrapolate breaking times for RSA 1024 or 2048 keys. Our estimates based on these experiments have been extremely conservative and have made generous assumptions about the abilities and power of the LLL programs. Do you have any mathematical proof of the security of NTRUEncrypt and NTRUSign? NTRUEncrypt uses techniques derived from an approach due to Fujisaki and Okamoto, which give the property of Indistinguishability against Adaptive Chosen Ciphertext Attack (IND-CCA2). Details are in [1] and [2]. [1] E.Fujisaki,T.Okamoto, How to Enhance the Security of Public-Key Encryption at Minimum Cost, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.E83-A, No.1, Special Issue on Cryptography and Information Security (January 2000) [2] NTRU Technical Note 16, available from The security relies on various assumptions, of which the most important are: NTRUSign, in the random oracle model, also reduces to the assumption that SVP and CVP are hard problems in the NTRU lattice. NTRU Tech Notes 12 and 13 give the results of numerical experiments which allow us to estimate the difficulty of SVP and CVP in the NTRU lattice. There are no known techniques which take advantage of the special structure of the NTRU lattice; the best known technique to attack NTRU-based algorithms is the standard LLL technique. It certainly appears that, in so far as the NTRU lattice differs from a random lattice, those differences make standard lattice reduction techniques less likely, rather than more likely to succeed (for example, the lattice contains a set of public moderately short vectors, which LLL will find in polynomial time, but which prevent the algorithm from finding the shorter vectors which actually act as keys). Why is NTRUEncrypt resistant to parallelized attacks? The hard problem underlying the NTRUEncrypt cryptosystem is that of finding short vectors in lattices of high dimension. To solve this problem, one uses lattice reduction methods, more specifically the Lenstra-Lenstra-Lovasz (LLL) algorithm with various improvements due to Schnorr, Euchner, Horner, and others. In a similar manner, people use the number field sieve (NFS) to factor integers and break RSA, and they use the Pollard rho method (PRM) to find elliptic curve discrete logarithms and break ECC. One way to make these methods (LLL, NFS, PRM) faster is to simultaneously use a large number of computers. In order to understand how this is done, we need to distinguish between two different ways that computers can interact: Parallelized Computation Distributed Computation Briefly, parallel computations require computers to be in continuous contact, while distributed computations can be performed on isolated computers with infrequent communications. Parallel computations are done by many computers (or computer chips) in a single room or building, while distributed computations may be done over a large diffuse network such as the internet. Important Note: Security levels for NTRUEncrypt, RSA, and ECC are generally given in MIPS-Years. This measures how many years it would take a single computer, operating at one millions instructions per second, to break the system. In order to establish suitable security levels, cryptographers estimate the total computational power, in MIPS, of all of the computers currently in existence, and they also make a reasonable guess for the total computational power of all computers that will exist at certain times in the future (10 years, 50 years, 100 years, etc.). They then assume that some portion of the world's computer power could be devoted to breaking a cryptosystem and use that number to suggest appropriate security levels. Thus security levels are set under the most conservative assumption that breaking a cryptosystem can be fully distributed, since no one believes that 1% (or even .01%) of the world's computational power will ever be parallelized. We have followed this conservative approach in setting NTRUEncrypt security levels, so even if lattice reduction is ever possible in a fully distributed environment, it will not affect the security of NTRUEncrypt. Lattice Reduction (LLL) and NTRUEncrypt The basic LLL algorithm is sequential, which means that each step relies on the results of the previous step. Briefly, one starts with a list of not-very-short vectors, modifies them to get a list that is (hopefully) a little shorter, and then keeps repeating the process. After a large number of repetitions, one hopes to find some very short vectors. Lattice reduction computations (using the best current algorithms) cannot be distributed, since each step relies on the results of the previous step. Thus it does not appear to be possible to distribute lattice reduction problems over a large number of computers connected by the internet. Parallelization, on the other hand, does offer the possibility of improved performance, and there has been important research on this topic. Remember that LLL takes a list of vectors and "modifies" it to get a better list. This modification process itself requires a large number of basic operations (additions, subtractions, multiplications, etc.). The idea for parallelized LLL is to connect a large number of computers (or computer chips) in the form of an n-by-n grid and do the list modification in one (or a few) computer cycles. In principle, using n2 computers can speed up LLL by a factor of n2. However, there is an important caveat. Parallelization only helps up to n equal to the dimension of the lattice, so for NTRUEncrypt the theoretical maximum gain is at most 106. Thus assembling a million computers in one building might give a corresponding speed increase, but as noted above, NTRUEncrypt security levels are set using conservative assumptions that already account for this scenario. For those interested in pursuing this topic, see for example: Number Field Sieve (NFS) and RSA The number field sieve (NFS) is the fastest known method for factoring large numbers. It consists of two distinct steps, "Relation Creation" and "Relation Reduction". The Relation Creation stage of NFS can be fully distributed, and indeed the factorization of a 512 bit RSA modulus by NFS did Relation Creation on hundreds of computers distributed over the internet. The Relation Reduction stage, by contrast, does not seem to be distributable, since it is a sequential process similar in some ways to lattice reduction. (More precisely, it involves matrix reduction of very large sparse matrices over the field with two elements.) However, parallelization using a grid of computers might well allow Relation Reduction to be done more rapidly. How does NTRUEncrypt cope with SPA-based attacks? [Glossary: SPA = Simple Power Analysis; DPA = Differential Power Analysis; both are ways of extracting cryptographic data from a device by measuring the power it consumes. The difference between SPA and DPA is that DPA, which is by and large more powerful, averages results over a large number of runs.] The core NTRU convolution is relatively easy to blind against SPA attacks. The operations are simply adds and reductions modulo a power of two. We would be happy to collaborate with interested device vendors on constructing an NTRU implementation that is entirely immune to SPA attacks. Full NTRU encryption requires the use of a hash function, typically SHA-1. This would need to be blinded against DPA and SPA to protect individual messages. It does not seem, however, that an SPA-based attack on the hash algorithm would endanger the private key. Does the NTRUEncrypt Public Key Cryptosystem pass the "Snake Oil Test"? We begin with a quote from the Snake Oil FAQ explaining what the term means. "Why "snake oil"? The term is used in many fields to denote something sold without consideration of its quality or its ability to fulfill its vendor's claims. This term originally applied to elixirs sold in traveling medicine shows. The salesmen would claim their elixir would cure just about any ailment that a potential customer could have. Listening to the claims made by some crypto vendors, "snake oil" is a surprisingly apt name." "Superficially, it is difficult to distinguish snake oil from the Real Thing: all encryption utilities produce garbled output. The purpose of the Snake Oil FAQ is to present some simple "red flags" that can help you detect snake oil." The Snake Oil FAQ gives a list of warning signs to look for when evaluating cryptographic systems and products. Another similar list was compiled by Bruce Schneier in the February 15, 1999 issue of the Crypto-Gram, published on the web by Counterpane Systems. We urge you to look at these sources for further details. (Disclaimer: The statements about NTRU that follow are ours alone. Neither the Snake Oil FAQ, Counterpane Systems nor Bruce Schneier in any way endorses any of our statements.) The following list of snake oil indicators was complied from the Snake Oil FAQ and from the Crypto-Gram. We feel that NTRUEncrypt easily passes the "snake-oil test". Warning Sign #1: Beware of Technobabble and Pseudo-Mathematical Gobbledygook Warning Sign #2: Beware of Secret Algorithms and Proprietary Cryptography Warning Sign #3: Beware of Revolutionary Breakthroughs and New Mathematics Warning Sign #4: Beware of Ridiculous Key Length. All discussion of the security of (public key) cryptosystems rests on the unspoken, but very necessary, assumption that we already know the most efficient algorithm for breaking the cryptosystem. With this assumption, it becomes a matter of theoretically and/or experimentally testing how fast the best breaking algorithm runs, and then extrapolating out to the recommended key sizes. The following table lists four practical public key cryptosystems which are based on well-studied mathematical problems and gives the best known algorithm for solving the underlying mathematical problem and breaking the system.
In conclusion, if a cryptosystem is to be secure, it is necessary that the number of possible keys be so large that one can't check all of them. But key length alone does not determine security. There is much more to analyzing the security of a cryptosystem than simply having a large number of keys. It is essential to thoroughly understand and test the system using the most sophisticated known mathematical techniques. It is also good if the underlying mathematical problem has been studied for many years, above and beyond its uses in cryptography. For example, this is the case with the integer factorization problem utilized by RSA, and it is also the case with the Short Vector Problem utilized by NTRUEncrypt. Warning Sign #5: Beware of One-Time Pads However, we do sometimes say that NTRUEncrypt has "disposable keys". This simply means that key creation is so fast that it is reasonable to create a new key for each transaction, something not possible with older systems. In addition to giving increased security, this opens up new applications and is an aspect of NTRUEncrypt of which we are quite proud. Warning Sign #6: Unsubstantiated Claims and Rave Reviews We reiterate that the hardest claims to substantiate are those relating to security. (It's relatively easy to test how fast a system is, or to see how long its keys are.) And everyone in the cryptographic industry, from market leaders to tiny upstarts, is frequently guilty of making unsubstantiated security claims through the sin of omission, because no security claim is complete unless it explicitly says that the stated time to break the cryptosystem depends on the assumption that no one will ever come up with a substantially better algorithm for solving the underlying mathematical problem. This is well known to every professional cryptographer, but people in the business community who buy cryptographic products generally do not realize that the security of the system is contingent on a lack of mathematical breakthroughs. Both the Snake-Oil FAQ and Schneier's article recommend using cryptosystems that have been reviewed by the cryptographic community. We know that NTRUEncrypt has been examined by numerous professional cryptographers, since we've received a lot of correspondence about it since 1996. Since these were direct private communications, we do not feel we can list their names in a public forum such as this web page. However, as an indication that top cryptographic professionals have studied NTRUEncrypt and take it seriously, we can point to an article on NTRUEncrypt that was presented at ANTS '98 by NTRU President Jeff Hoffstein, an article about the NTRUEncrypt Cryptosystem by Don Coppersmith and Adi Shamir that appeared in the proceedings of EUROCRYPT '97, and a Master's Thesis on NTRU written by Alexander May under the direction of Claus Schnorr. Further, the Tumbler implementation (C and Java) of the NTRU cryptosystem by Tao Group, Ltd. has been reviewed by Counterpane Systems, a well-known and highly respected company specializing in security evaluations of cryptographic products. Warning Sign #7: Security Proofs We certainly don't claim to have a proof that NTRUEncrypt is secure. We only claim that the best known method to find an NTRUEncrypt private key or break an encryted NTRU message requires solving the Short Vector Problem, and that the best known method to solve the Short Vector Problem is LLL Lattice Reduction (with improvements by Schnorr and others). We have conducted extensive tests of these methods and used these tests (in a very conservative manner) to set appropriate security levels. Of course, we also publish full details of our experiments and encourage independent testing by others. Warning Sign #8: Beware of Cracking Contests Cracking contests are mainly useful for perking interest in mathematical problems that already interest mathematicians and computer scientists. In some sense, they create a fun, yet competitive, setting for doing serious work. This is true of RSA's factorization challenges, Certicom's discrete logarithm challenges, and NTRUEncrypt's lattice reduction challenges. There has been a great deal of research in both the academic and business worlds on the problem of finding short vectors in lattices, partly because the problem is inherently mathematically appealing, and partly because it has many practical applications. So we feel that it is worthwhile running a contest which encourages people to study and refine methods for solving the Short Vector Problem. (Of course, we're also happy to have people think about other ways to break NTRUEncrypt which do not involve lattices or short vectors.) Thus although we would never say that the NTRU Challenge Problems in any way guarantee the security of NTRUEncrypt, we do feel that they are helpful in encouraging people to further study the Short Vector Problem and to study NTRUEncrypt. Finally, we stress that the NTRU Challenge Problems are fair, in the sense that we completely describe the algorithms used to create a key, to encrypt, and to decrypt. We even give step-by-step instructions on how to check if a solution (key or message) is correct. Visit the NTRU Challenge Page for further information. You can also read Bruce Schneier's comments on cracking contests (with which we don't entirely agree, but we'll let you form your own opinion) in the December issue of the Crypto-Gram. Is NTRU vulnerable to attacks based on quantum computing? There is no known quantum computing algorithm which speeds up attacks on NTRU. In general, there are two quantum computing algorithms of great significance to cryptanalysis: Shor's algorithm and Grover's algorithm. Shor's algorithm uses the fact that quantum computing methods can calculate the period of a periodic function very quickly. This can be used to massively speed up attacks on RSA, Discrete Log based cryptosystems such as DSA and Diffie-Hellman, and Elliptic Curve Discrete Log systems such as ECDSA, ECMQV, and so on. (Note that in the case of RSA the period of the function essentially is the private key). Shor's algorithm has no obvious application to NTRU: NTRU has no similar periodic function to exploit. Grover's algorithm speeds up unsorted database and brute force searches: using Grover's algorithm, it is possible to search a list of N items in sqrt(N) time. This effectively halves the keylength of symmetric ciphers. However, there is no obvious application to NTRU, as in the case of NTRU the brute force attack is not the most efficient, even if sped up by Grover's algorithm. (Note that there is a known meet-in-the-middle attack on NTRU private keys which also speeds up a brute force search by a square-root factor; there is no known way to compose this speed-up with a quantum computing speed-up). Additional quantum computing algorithms exist (e.g. to find eigenvalues quickly): again, there is no obvious application to breaking NTRU. Finally, we note that the threat from quantum computers to all encryption algorithms is currently theoretical. The biggest working quantum computer to date can do 7-bit operations; it will take a quantum computer of a few thousands of qubits to break RSA-1024. However, theory is advancing rapidly and claims are being made all the time of new designs that will enable multi-bit operations. Fundamentals What is the difference between a ring-based cryptosystem and a group-based cryptosystem? A ring is a mathematical object which has two algebraic operations, addition and multiplication. Examples of rings are the integers, the rational numbers, finite fields, and rings of polynomials. Groups, on the other hand, have only one operation. An important example of a group is the collection of non-zero elements in a finite field, where the one operation is multiplication. Another example is the set of points on a mathematical object called an elliptic curve. Aside from NTRUEncrypt, the three most popular pubic key cryptosystems in use today are RSA, El Gamal, and ECC (elliptic curve cryptosystem). All of these are group-based cryptosystems in the sense that the encryption/decryption processes use only one algebraic operation. Thus RSA uses multiplication in a finite ring (the integers modulo m), El Gamal uses multiplication in a finite field, and ECC uses elliptic curve addition. The NTRUEncrypt public key cryptosystem, by way of contrast, makes use of both the addition and the multiplication in a certain finite ring, which is why we say that NTRUEncrypt is a ring-based cryptosystem. This fact does not, in and of itself, make NTRUEncrypt either better or worse than earlier systems; but it does serve to differentiate it. It is worth noting that the groups used for RSA and El Gamal actually fit very naturally into rings. Indeed, in both cases the group being used is the group of invertible elements (i.e., elements with multiplicative inverses) inside a large ring, so one might ask why they aren't also ring-based systems. The answer is that neither cryptosystem makes use of the addition operation in the ring; they only use multiplication, so they are groups-based. On the other hand, the fact that the groups used by RSA and El Gamal fit naturally into rings is exploited in mounting attacks on these systems. More precisely, the sub-exponential algorithms to break RSA and El Gamal (quadratic sieve, number field sieve, index calculus) rely on both addition and multiplication. By way of contrast, the elliptic curve groups used by ECC do not naturally fit inside of a ring, which might help explain why there are no known subexponential algorithms for ECC. Now to the NTRUEncrypt cryptosystem. The encryption and decryption processes for NTRUEncrypt use both addition and multiplication in an essential way, which is why we call NTRUEncrypt a ring-based system. This is not to say that merely using ring operations makes NTRUEncrypt secure. But as we have just observed, if a group based system fits naturally into a ring, then the extra operation in the ring can be exploited in attacking the system. This explains why it makes sense to look at cryptosystems which directly use both addition and multiplication, since if both operations will be available to the attacker anyway, it makes sense to also use both of them for the encryption and decryption processes.
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
| Copyright © NTRU Cryptosystems, Inc. 1998-2008 35 Nagog Park, Acton, MA 01720, USA Tel. 978-844-5200 |
Created by PixelMEDIA |
|
|
