Submissions and Contributions to IEEE P1363.1

• Hybrid Lattice-Reduction and Meet-In-The-Middle Resistant Parameter selection for NTRUEncrypt
• A Hybrid Lattice-Reduction and Meet-In-The-Middle Attack against NTRU
• Timing Attacks on NTRUEncrypt via Variation in the Number of Hash Calls
• Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures
• Performance Improvements and a Baseline Parameter Generation for NTRUSign (paper and presentation)
• Practical Lattice Basis Sampling Reduction
• On Estimating the Lattice Security of NTRU
• Random Sampling Reduction
• Performance Improvements and a Baseline Parameter Generation for NTRUSign, original version
• Variation in Breaking Times for NTRU and Other Cryptosystems
• Lattice Breaking Times
• Choosing NTRUEncrypt Parameters
• Cryptography and the Variational Stability of Algorithms
• X9.98 Top N Issues
• Estimating Decryption Failure Probabilities for NTRUEncrypt.
• A Meet-In-The-Middle Attack on an NTRU Private Key.
• Estimated Breaking Times for NTRU Lattices.
• NAEP: Provable Security in the Presence of Decryption Failures
• The Impact of Decryption Failures on the Security of NTRU Encryption
• On the bit security of NTRUEncrypt
• Efficient Embedded Security Standard #1, version 2
• NTRU: A Public Key Cryptosystem

We present a new method for choosing parameter sets for the NTRUEncrypt public key cryptosystem. This modifies our original method to protect against the new hybrid meet in the middle and lattice reduction attack.

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 reduciton schemes to recover the private key. We show that there is in fact a continuum of more efficient attacks between these two attacs. 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 2^84.2 to 2^60.3, for the k = 80 parameter set. In practice the attack is still expensive (dependent on one's 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 2^k even after an initial lattice basis reduction of complexity 2^k.

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[7,5]. 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 [7,5] and has only a slight effect on performance.

(Contributed June 2006)

back to top

A presentation (.ppt) by William Whyte on the implications of this result for P1363.1.

A presentation (ppt) on this paper

The original presentation of the NTRUSign signature scheme gave a set of parameters that were claimed to give 80 bits of security, but did not give a general recipe for generating parameter sets to a specific level of security. In line with recent research on NTRUEncrypt, this paper presents an outline of such a recipe for NTRUSign. We also present certain technical advances upon which we intend to build in subsequent papers.

y

.pdf file

On estimating the lattice security of NTRU, Nick Howgrave-Graham, Jeff Hoffstein, Jill Pipher, William 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.

.pdf file

Random Sampling Reduction, William Whyte

A single Powerpoint slide illustrating a lower-triangular matrix, to help explain the principle behind Random Sampling Reduction.

(Contributed April 2005)

back to top

Original version, superseded by the version from August 2005.

Postscript PDF

(Contributed November 2004)

back to top

Variation in Breaking Times for NTRU and Other Cryptosystems, Joseph H. Silverman and William Whyte
LatticeBreakingVariation-1363-2004-03.ppt (Powerpoint)
Comparing average and minimum breaking times for NTRU and other cryptosystems.

Lattice Breaking Times, William Whyte
Lattice-P1363-2004-03.ppt (Powerpoint)
A survey of known results in lattice breaking times, and how to calculate the breaking times of recommended NTRU lattices.

Choosing NTRUEncrypt Parameters, William WHyte
Parameters-1363-2004-03.ppt (Powerpoint)
How to choose NTRUEncrypt parameters. Proposals for slight variations in NTRUEncrypt encryption schemes to allow for greater efficiency. NTRUEncrypt schemes that allow for perfect forward secrecy.

Cryptography and the Variational Stability of Algorithms, Joseph H. Silverman
StabilityOfAlgorithms.pdf (Acrobat)
Many algorithms exhibit a wide variation of running times when presented with different inputs. For such algorithms, if the goal is simply to solve a single problem instance, then it may be more efficient to set a cutoff time and to start on a new problem instance if the chosen cutoff time is exceeded. Whether or not this cutoff strategy is helpful depends on the extent to which the running time varies. In this note we quantify this notion of algorithmic variability and we define a stability exponent StExp with the property that a cutoff strategy is useful if and only if StExp > 1. We compute the stability exponent exactly for exhaustive searches and for meet-in-the-middle (eg, Pollard rho) searches and we estimate the stability exponent experimentally for an LLL lattice reduction implementation. These three examples have applications, respectively, to symmetric ciphers (DES, AES), elliptic curve cryptosystems (ECC), and lattice cryptosystems (NTRU).

(Contributed March 2004)

back to top

Microsoft Powerpoint (.ppt) File (179 K)

(Contributed November 2003)

back to top

NTRU Report 018. Estimating Decryption Failure Probabilities for NTRUEncrypt, J. H. Silverman, W. Whyte

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 (212K)   |   PDF (228K)

NTRU Report 004, Version 2. A Meet-In-The-Middle Attack on an NTRU Private Key.
N. Howgrave-Graham, J. H. Silverman, W. Whyte

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 2^M elements, then the security level of the cryptosystem is 2^M/2.

Format:  Postscript (134K)   |   PDF (150K)

NTRU Report 012, Version 2. Estimated Breaking Times for NTRU Lattices.
J. Hoffstein, J. H. Silverman, W. Whyte

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.

Format:  Postscript (257K)   |   PDF (194K)

NAEP: Provable Security in the Presence of Decryption Failures
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.

Format:   Postscript (438K)   |    PDF (205K)

The Impact of Decryption Failures on the Security of NTRU Encryption
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.

Format:  Postscript (311K)   |   PDF (294K)

On the bit security of NTRUEncrypt
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.

Format:   Postscript (113K)   |    PDF (279K)

Efficient Embedded Security Standard #1, version 2
Consortium for Efficient Embedded Security, June 2003

Standardized descriptions of NTRUEncrypt and NTRUSign.

Format:   PDF (315K)

back to top

back to top

NTRU: A Public Key Cryptosystem
Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, August 1999.
Presented at the August 1999 and October 1999 meetings.

This purpose of this paper is to submit the NTRU public key cryptosystem for consideration for inclusion into the P1363a standard.

Compared to other public key cryptosystems at roughly equivalent levels of security, NTRU offers: more efficient encryption and decryption, in both hardware and software implementations; much faster key generation, allowing the use of ``disposable'' keys (because keys are computationally ``cheap'' to create).

NTRU was originally presented by Jeffrey Hoffstein in the rump session at CRYPTO '96, and was published in 1998. Since that time, NTRU Cryptosystems, Inc. has issued a number of technical reports. In some cases, these reports have described amplifications on the techniques in in order to deal with new attacks (e.g., to deal with issues of plaintext awareness). In other cases, these reports have described fast algorithms for carrying out some of the computations required by NTRU. In this document, we have freely copied from the original paper introducing NTRU and other NTRU Cryptosystems, Inc. publications whenever appropriate.

Format:  Postscript (526K)   |   PDF (268K)

back to top

IEEE Home Page	IEEE Standards	IEEE P1363