- 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)*

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

We propose a practical sampling reduction algorithm for lattice bases based on work by Schnorr as well as two even more effective generalizations. We report the empirical behaviour of these algorithms. We describe how Sampling Reduction allows to stage lattice attacks against the NTRU cryptosystem with smaller BKZ parameters than before and conclude that therefore the recommended NTRU security parameters offer <= 74 Bit security.

**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)*

Original version, superseded by the version from August 2005.

*(Contributed November 2004)*

**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)*

Presentation to the ANSI X9F1 working group on the X9.98 standard, concerning NTRUEncrypt.

Microsoft Powerpoint (.ppt) File (179 K)

*(Contributed November 2003)*

**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)

**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)

IEEE Home Page | IEEE Standards | IEEE P1363 |