NTRU Resources

While Security Innovation’s expertise isn’t limited to any specific platform or technology, we do have deep experience and specialization in automotive and embedded security.

Resources:

NTRU Survey Article

Practical lattice-based cryptography: NTRUEncrypt and NTRUSign

J. Hoffstein, N. Howgrave-Graham, J. Pipher, W. Whyte
LLL Algorithm 2010: 349-390

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

PDF

NTRU Technical Reports

NTRU Technical Reports provide in-depth analysis of certain issues in NTRU cryptography. Please contact us with any questions regarding these reports.

Note: These Technical Reports are undergoing a continual process of revision, and some reports refer to different parameter sets from the ones that we currently recommend.

NTRU Report 004, Version 2. A Meet-In-The-Middle Attack on an NTRU Private Key.

In this report we describe a meet-in-the-middle attack on an NTRU private key. Hence if the private key is chosen from a sample space with 2M elements, then the security level of the cryptosystem is 2M/2.

Updated 2003/06 to reflect slight improvements in the running times, and to extend the analysis from binary keys to "product form" keys.

Format: Postscript | PDF

NTRU Report 005. Hard Problems and Backdoors for NTRU and Other PKCSs.

A hard problem and the associated back door for the NTRU Public Key Cryptosystem is described and compared/contrasted with the hard problems and back doors associated to other common public key cryptosystems.

Format: Postscript | PDF

NTRU Report 006. Implementation Notes for NTRU PKCS Multiple Transmissions.

Multiple NTRU encryptions of a single message using a single key may compromise the security of the message. In this report we analyze this situation and describe scrambling techniques that allow secure multiple transmissions of a single message.

Much of the material in this report has been superseded by the paper NAEP: Provable Security in the Presence of Decryption Failures.

Format: Postscript | PDF

NTRU Report 007. Plaintext Awareness and the NTRU PKCS.

This report has been superseded by the paper NAEP: Provable Security in the Presence of Decryption Failures.

NTRU Report 008. Efficient Conversions from Mod q to Mod p.

An efficient method for converting a list of numbers modulo q to a list of numbers modulo p is described.

Format: Postscript | PDF

NTRU Report 009. Invertibility in Truncated Polynomial Rings.

Let Rq = (Z/qZ)[X]/(XN-1) be the ring of truncated polynomials modulo q. We compute the probability that a randomly chosen polynomial f in Rq is invertible in Rq, and also the conditional probability if f is required to satisfy f(1)=1.

Format: Postscript | PDF

NTRU Report 010. High-Speed Multiplication of (Truncated) Polynomials.

Multiplication of two (truncated) polynomials of degree n takes on the order of n2 operations. By splitting the polynomials into two pieces, this may be reduced to approximately 0.75n2 operations, and repeated recursive application of this procedure leads to even greater savings.

Format: Postscript | PDF

NTRU Report 011. Wraps, Gaps, and Lattice Constants.

This note describes how the choice of a parameter set (N,p,q,df,dg,dphi) for an NTRU Public Key Cryptosystem determine various operating characteristics of the cryptosystem, such as the security level and the probabilities of wrapping failure and of gap failure.

Much of the analysis in this report is extended in Technical Report 18.

Format: Postscript | PDF

NTRU Report 012, Version 2. Estimated Breaking Times for NTRU Lattices.

In this note we report on experiments with the lattices underlying the NTRU Public Key Cryptosystem. We present data for the time needed to find a small vector and use this data to extrapolate expected breaking times for the NTRU PKCS for recommended parameter values. We also extend the "zero forcing" analysis of May and Silverman to include a check that the lattice strength in the lower-dimension, zero-forced lattice can correctly be approximated by the same extrapolation line as the non-zero-forced lattice.

Updated 2003/06 to reflect recommended new parameter sets, and to include the zero-forcing analysis.

Format: Postscript | PDF

NTRU Report 013. Dimension-Reduced Lattices, Zero-Forced Lattices, and the NTRU Public Key Cryptosystem.

In this note we describe, extend, and analyze the lattice construction ideas of Alexander May as they apply to the NTRU public key cryptosystem. We use both theoretical and experimental methods to analyze the strength of the attacks. The final conclusion is that the new attacks only marginally affect the security levels of the standard commercial NTRU parameter sets (N=167, 263, and 503), but that the new lattices can be helpful for very low security levels (N=107).

Format: Postscript | PDF

NTRU Report 014. Almost Inverses and Fast NTRU Key Creation

We explain how to use the "Almost Inverse Algorithm" of Schroeppel, Orman, O'Malley, and Spatscheck to efficiently compute NTRU public/private key pairs.

Format: Postscript | PDF

NTRU Report 015. Reaction Attacks Against the NTRU Public Key Cryptosystem.

This report has been superseded by the paper NAEP: Provable Security in the Presence of Decryption Failures.

NTRU Report 016. Protecting NTRU Against Chosen Ciphertext and Reaction Attacks.

This report has been superseded by the paper NAEP: Provable Security in the Presence of Decryption Failures.

NTRU Report 018. Estimating Decryption Failure Probabilities for NTRUEncrypt.

We describe a theoretical method for estimating the decryption failure probability for NTRUEncrypt. We apply this method to a suggested parameter set and compare it with experiment.

Format: Postscript | PDF

Articles by the NTRU Team

This section contains articles produced by the NTRU R&D department. These are the authoritative documents describing NTRU technology. Please also consult our Technical Reports for further technical information.

NTRUEncrypt: Abstracts and Articles

Timing Attacks on NTRUEncrypt Via Variation in the Number of Hash Calls PDF

Joseph H. Silverman, William Whyte
CT-RSA 2007: 208-224

This report studies timing attacks on NTRUEncrypt based on variation in the number of hash calls made on decryption. The attacks apply to the parameter sets of [8,6]. To mount the attacker, an attacker performs a variable amount of precomputation, then submits a relatively small number of specially constructed ciphertexts for decryption and measures the decryption times. Comparison of the decryption times with the precomputed data allows the attacker to recover the key in greatly reduced time compared to standard attacks on NTRUEncrypt. The precomputed data can be used for all keys generated with a specific parameter set and tradeoffs exist that increase the amount of precomputation in order to decrease the time required to recover an individual key. For parameter sets in [3] that claim k-bit security but are vulnerable to this attack, we find that an attacker can typically recover a single key with about k/2 bits of effort.

Finally, we describe a simple means to prevent these attacks by ensuring that all operations take a constant number of SHA calls. The recommended countermeasure does not break interoperability with the parameter sets of [8,6] and has only a slight effect on performance.

Choosing Parameters for NTRUEncrypt - PDF

Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte and Zhenfei Zhang

We describe a methods for generating parameter sets and calculating security estimates for NTRUEncrypt. Analyses are provided for the standardized product-form parameter sets from EESS #1 and for the NTRU Challenge parameter sets.

NTRU: A Ring-Based Public Key Cryptosystem Postscript | PDF

Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman

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.

Optimizations for NTRU Postscript | PDF

J. Hoffstein, J. Silverman

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.

Random Small Hamming Weight Products With Applications to Cryptography Postscript | PDF

J. Hoffstein, J. Silverman

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.

NTRU in Constrained Devices PDF

D. Bailey, D. Coffin, A. Elbirt, J. Silverman, A. Woodbury

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.

On the bit security of NTRUEncrypt Postscript | PDF

M. Naslund, I. Shparlinski, W. Whyte

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.

The Impact of Decryption Failures on the Security of NTRU Encryption Postscript | PDF

N. Howgrave-Graham, P. Nguyen, D. Pointcheval, J. Proos, J. H. Silverman, A. Singer, W. Whyte

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.

NAEP: Provable Security in the Presence of Decryption Failures Postscript | PDF

N. Howgrave-Graham, J. H. Silverman, A. Singer, W. Whyte

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.

A Hybrid Lattice-Reduction and Meet-in-the-Middle Attack Against NTRU PDF

N. Howgrave-Graham

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.

Choosing NTRU Parameters in Light of Combined Lattice Reduction and MITM Approaches PDF

P. Hirschhorn, J. Hoffstein, N. Howgrave-Graham, W. Whyte
ACNS 2009: 437-455

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.

NTRUSign: Abstracts and Articles

Practical Signatures from the Partial Fourier Recovery Problem PDF

Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte
ACNS 2014: 476-493

We present PASSSign, a variant of the prior PASS and PASS-2 proposals, as a candidate for a practical post-quantum signature scheme. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation. For our particular instantiation, this corresponds to the recovery of a signal with small infinity norm from a limited set of its Fourier coefficients.

The key improvement over previous versions of PASS is the introduction of a rejection sampling technique from Lyubashevsky (2009) which assures that transcript distributions are completely decoupled from the keys that generate them.

Although the scheme is not supported by a formal security reduction, we present extensive arguments for its security and derive concrete parameters based on the performance of state of the art lattice reduction and enumeration techniques.

Performance Improvements and a Baseline Parameter Generation Algorithm for NTRUSign PDF

J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. Silverman, W. Whyte

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

J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. Silverman, W. Whyte

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: Postscript | PDF

Extended version, referred to in proceedings version: Postscript | PDF

NTRU Lattice: Abstracts and Articles

IEEE Draft Standard Specification for Public- Key Cryptographic Techniques Based on Hard Problems Over Lattices PDF

William Whyte, Nick Howgrave-Graham, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, Philip S. Hirschhorn

Specifications of common public-key cryptographic techniques based on 1 hard problems over lattices supplemental to those considered in IEEE 1363 and IEEE P1363a, including mathematical primitives for secret value (key) derivation, public-key encryption, identification and digital signatures, and cryptographic schemes based on those primitives. Specifications of related cryptographic parameters, public keys and private keys. Class of computer and communications systems is not restricted

Transcript Secure Signatures Based on Modular Lattices PDF

Jeff Hoffstein, Jill Pipher, John M. Schanck, Joseph H. Silverman, William Whyte
PQCrypto 2014: 142-159

We introduce a class of lattice-based digital signature schemes based on modular properties of the coordinates of lattice vectors. We also suggest a method of making such schemes transcript secure via a rejection sampling technique of Lyubashevsky (2009). A particular instantiation of this approach is given, using NTRU lattices. Although the scheme is not supported by a formal security reduction, we present arguments for its security and derive concrete parameters based on the performance of state-of-the-art lattice reduction and enumeration techniques.

On Estimating the Lattice Security of NTRU Postscript | PDF

N. Howgrave-Graham, J. Hoffstein, J. Pipher, W. Whyte

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.

Isodual Reduction of Lattices PDF

N. Howgrave-Graham

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.

Standards

Efficient Embedded Security Standards (EESS) #1: Implementation Aspects of NTRUEncrypt PDF

This document specifies common techniques and implementation choices using the NTRUEncrypt publickey cryptography algorithms. Topics covered include: Cryptographic primitives, Cryptographic schemes, Supported parameter choices and ASN.1 syntax for NTRUEncrypt and NTRUSign. In addition, this standard includes relevant information to assist in the development and interoperable implementation of NTRUEncrypt, including security.

Protocols

A quantum-safe circuit-extension handshake for Tor PDF

John Schanck, William Whyte, and Zhenfei Zhang

We propose a method for integrating NTRUEncrypt into the ntor key exchange protocol as a means of achieving a quantum-safe variant of forward secrecy. The proposal is a minimal change to ntor, essentially consisting of an NTRUEncrypt-based key exchange performed in parallel with the ntor handshake. Performance figures are provided demonstrating that the client bears most of the additional overhead, and that the added load on the router side is acceptable.