|
|
|
|
|
|
|
|
|
|
  This page contains current articles produced by the NTRU R&D department. These are the authoritative documents describing NTRU technology. Please also consult our Technical Notes for further technical information. NTRUEncrypt: Abstracts and ArticlesNTRUSign: Abstracts and Articles NTRU Lattice: Abstracts and Articles Survey Articles NTRUEncrypt: Abstracts and Articles NTRU: A Ring-Based Public Key Cryptosystem in Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288. We describe NTRU, a new public key cryptosystem. NTRU features reasonably short, easily created keys, high speed, and low memory requirements. NTRU encryption and decryption use a mixing system suggested by polynomial algebra combined with a clustering principle based on elementary probability theory. The security of the NTRU cryptosystem comes from the interaction of the polynomial mixing system with the independence of reduction modulo two relatively prime integers p and q. Format: Postscript | PDF Optimizations for NTRU in Public-Key Cryptography and Computational Number Theory (Warsaw, September 11-15, 2000) In this note we describe a variety of methods that may be used to increase the speed and efficiency of the NTRU Cryptosystem. Format: Postscript | PDF Random Small Hamming Weight Products With Applications to Cryptography There are many cryptographic constructions in which one uses a random power or multiple of an element in a group or a ring. We describe a fast method to compute random powers and multiples in certain important situations including powers in the Galois field F2 n , multiples on Koblitz elliptic curves, and multiples in NTRU convolution polynomial rings. The underlying idea is to form a random exponent or multiplier as a product of factors, each of which has low Hamming weight when expanded as a sum of powers of some fast operation. Format: Postscript | PDF NTRU in Constrained
Devices in Proc. Cryptographic Hardware and Embedded Systems, Paris, France, 2001 The increasing connectivity offered by constrained computing devices signals a vital need for public-key cryptography in such environments. By their nature, however, public-key systems have been difficult to implement in systems with limited computational power. The NTRU public-key cryptosystem addresses this problem by offering tremendoub performance enhancements over previous practical systems. The efficiency of NTRU is applied to a wide variety of constrained devices in this paper, including the Palm Computing Platform, Advanced RISC Machines ARM7TDMI, the Research in Motion pager, and finally, the Xilinx Virtex 1000 famility of FPGAs. On each of these platforms, NTRU offers exceptional performance, enabling a new range of applications to make use of the power of public key cryptography. Format: PDF On the bit security of
NTRUEncrypt in Proc. Intern. Workshop on Public Key Cryptography, PKC'03, Miami, USA, 2003 We show that in certain natural computational models every bit of a message encrypted with the NTRUEncrypt cryptosystem is as secure as the whole message. Format: Postscript | PDF The Impact of Decryption
Failures on the Security of NTRU Encryption in Proc. Crypto 2003, Santa Barbara, USA, 2003 NTRUEncrypt is unusual among public-key cryptosystems in that, with standard parameters, validly generated ciphertexts can fail to decrypt. This affects the provable security properties of a cryptosystem, as it limits the ability to build a simulator in the random oracle model without knowledge of the private key. We demonstrate attacks which use decryption failures to recover the private key. Such attacks work for all standard parameter sets, and one of them applies to any padding. The appropriate countermeasure is to change the parameter sets and possibly the decryption process so that decryption failures are vanishingly unlikely, and to adopt a padding scheme that prevents an attacker from directly controlling any part of the input to the encryption primitive. We outline one such candidate padding scheme. Format: Postscript | PDF NAEP: Provable Security in the
Presence of Decryption Failures We consider the impact of the possibility of decryption failures in proofs of security for padding schemes, where these failures are both message and key dependent. We explain that an average case failure analysis is not necessarily sufficient to achieve provable security with existing CCA2-secure schemes. On a positive note, we introduce NAEP, an efficient padding scheme similar to PSS-E, designed especially for the NTRU one-way function. We show that with this padding scheme we can prove security in the presence of decryption failures, under certain explicitly stated assumptions. We also discuss the applicability of proofs of security to instantiated cryptosystems in general, introducing a more practical notion of cost to describe the power of an adversary. Format: Postscript | PDF A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU To date the NTRUEncrypt security parameters have been based on the existence of two types of attack: a meet-in-the-middle attack due to Odlyzko, and a conservative extrapolation of the running times of the best (known) lattice reduction schemes to recover the private key.We show that there is in fact a continuum of more efficient attacks between these two attacks. We show that by combining lattice reduction and a meet-in-the-middle strategy one can reduce the number of loops in attacking the NTRUEncrypt private key from 284.2 to 260.3, for the k = 80 parameter set. In practice the attack is still expensive (dependent on ones choice of cost-metric), although there are certain space/time tradeoffs that can be applied. Asymptotically our attack remains exponential in the security parameter k, but it dictates that NTRUEncrypt parameters must be chosen so that the meet-in-the-middle attack has complexity 2k even after an initial lattice basis reduction of complexity 2k. Format: PDF Choosing NTRU Parameters in Light of Combined Lattice Reduction and MITM Approaches Published at ACNS 2009. We present the new NTRUEncrypt parameter generation algorithm, which is designed to be secure in light of recent attacks that combine lattice reduction and meet-in-the-middle (MITM) techniques. The parameters generated from our algorithm have been submitted to several standard bodies and are presented at the end of the paper. Format: PDF NTRUSign: Abstracts and Articles Performance
Improvements and a Baseline Parameter Generation
Algorithm for NTRUSign We present a general recipe for generating parameter sets to a specific level of security. We also present certain technical advances upon which we intend to build in subsequent papers. Presented at Workshop on Mathematical Problems and Techniques
in Cryptology, Barcelona, Spain, June 2005
NTRUSign: Digital Signatures Using the NTRU Lattice In this paper we introduce NTRUSign, a new family of signature schemes based on solving the approximate closest vector problem (appr-CVP) in NTRU-type lattices. We explore the properties of general appr-CVP based signature schemes (e.g. GGH) and show that they are not immune to transcript attacks even in the random oracle model. We then introduce the idea of using carefully chosen perturbations to limit the information that is obtainable from an analysis of a large signature transcript. In the case of NTRUSign, this can be achieved while maintaining attractive efficiency properties. CT-RSA 2003 Proceedings Version: Extended version, referred to in proceedings version: NTRU Lattice: Abstracts and Articles On Estimating the
Lattice Security of NTRU This report explicitly refutes the analysis behind a recent claim that NTRUEncrypt has a bit security of at most 74 bits. We also sum up some existing literature on NTRU and lattices, in order to help explain what should and what should not be classed as an improved at- tack against the hard problem underlying NTRUEncrypt. We also show a connection between Schnorr's RSR technique and exhaustively searching the NTRU lattice. Format: Postscript | PDFIsodual Reduction of Lattices We define a new notion of a reduced lattice, based on a quantity introduced in the LLL paper. We show that lattices reduced in this sense are simultaneously reduced in both their primal and dual. We show that the definition applies naturally to blocks, and therefore gives a new hierarchy of polynomial time algorithms for lattice reduction with fixed blocksize. We compare this hierarchy of algorithms to previous ones. We then explore algorithms to provably minimize the associated measure, and also some more efficient heuristics. Finally we comment on the initial investigations of applying our technique to the NTRU family of lattices. Format: PDFSurvey Articles Practical lattice-based cryptography: NTRUEncrypt and NTRUSign We provide a brief history and overview of lattice based cryptography and cryptanalysis: shortest vector problems, closest vector problems, subset sum problemand knapsack systems, GGH, Ajtai-Dwork and NTRU. A detailed discussion of the algorithms NTRUEncrypt and NTRUSign follows. These algorithms have attractive operating speed and keysize and are based on hard problems that are seemingly intractable. We discuss the state of current knowledge about the security of both algorithms and identify areas for further research. Format: PDF
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
|
|
| Copyright © NTRU Cryptosystems, Inc. 1998-2006 35 Nagog Park, Acton, MA 01720, USA Tel. 978-844-5200 |
Created by PixelMEDIA |
|
|
