#
NTRU Scrutiny

## NTRUEncrypt

### 2015

#### Adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes

*R. Dahab, S. Galbraith, and E. Morais*

In this paper we present adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes. Among such schemes, we study the proposal by Bos et al [BLLN13] in 2013. Given access to a decryption oracle, the attack allows us to compute the private key for all parameter choices. Such attacks show that one must be very careful about the use of homomorphic encryption in practice. The existence of a key recovery attack means that the scheme is not CCA1-secure. Indeed, almost every somewhat homomorphic construction proposed till now in the literature is vulnerable to an attack of this type. Hence our result adds to a body of literature that shows that building CCA1-secure homomorphic schemes is not trivial.

#### NTRUReEncrypt: An Efficient Proxy Re-Encryption Scheme Based on NTRU

*D. Nunez, I. Agudo, and J. Lopez*

The use of alternative foundations for constructing more secure and efficient cryptographic schemes is a topic worth exploring. In the case of proxy re-encryption, the vast majority of schemes are based on number theoretic problems such as the discrete logarithm. In this paper we present NTRUReEncrypt, a new bidirectional and multihop proxy re-encryption scheme based on NTRU, a widely known lattice-based cryptosystem. We provide two versions of our scheme: the first one is based on the conventional NTRU encryption scheme and, although it lacks a security proof, remains as efficient as its predecessor; the second one is based on a variant of NTRU proposed by Stehlé and Steinfeld, which is proven CPA-secure under the hardness of the Ring-LWE problem. To the best of our knowledge, our proposals are the first proxy re-encryption schemes to be based on the NTRU primitive. In addition, we provide experimental results to show the efficiency of our proposal, as well as a comparison with previous proxy re-encryption schemes, which confirms that our first scheme outperforms the rest by an order of magnitude.

### 2014

#### Efficient Identity-Based Encryption over NTRU Lattices

*Léo Ducas, Vadim Lyubashevsky, Thomas Prest*

Efficient implementations of lattice-based cryptographic schemes have been limited to only the most basic primitives like encryption and digital signatures. The main reason for this limitation is that at the core of many advanced lattice primitives is a trapdoor sampling algorithm (Gentry, Peikert, Vaikuntanathan, STOC 2008) that produced outputs that were too long for practical applications. In this work, we show that using a particular distribution over NTRU lattices can make GPV-based schemes suitable for practice. More concretely, we present the first lattice-based IBE scheme with practical parameters – key and ciphertext sizes are between two and four kilobytes, and all encryption and decryption operations take approximately one millisecond on a moderately-powered laptop. As a by-product, we also obtain digital signature schemes which are shorter than the previously most-compact ones of Ducas, Durmus, Lepoint, and Lyubashevsky from Crypto 2013

#### A Scalable Implementation of Fully Homomorphic Encryption Built on NTRU

*Kurt Rohloff and David Bruce Cousins*

In this paper we report on our work to design, implement, and evaluate a Fully Homomorphic Encryption (FHE) scheme. Our FHE scheme is an NTRU-like cryptosystem, with additional support for efficient key switching and modulus reduction operations to reduce the frequency of bootstrapping operations. Ciphertexts in our scheme are represented as matrices of 64-bit integers. The basis of our design is a layered software services stack to provide high-level FHE operations supported by lower-level lattice-based primitive implementations running on a computing substrate. We implement and evaluate our FHE scheme to run on a commodity CPU-based computing environment. We implemented our FHE scheme to run in a compiled C environment and use parallelism to take advantage of multi-core processors. We provide experimental results which show that our FHE implementation provides at least an order of magnitude improvement in runtime as compared to recent publicly known evaluation results of other FHE software implementations.

#### A key recovery attack to the sale-invariant NTRU-based somewhat homomorphic encryption scheme

*Eduardo Morais, and Ricardo Dahab*

In this paper we present a key recovery attack to the scale-invariant NTRU-based somewhat homomorphic encryption scheme proposed by Bos et al [BLLN13] in 2013. The attack allows us to compute the private key for *t* > 2 and when the private key is chosen with coefficients in { -1, 0, 1}. The efficiency of the attack is optimal since it requires just one decryption oracle query, showing that if we don’t look for this kind of vulnerabilities in homomorphic encryption constructions we are likely to choose insecure parameters. The existence of a key recovery attack means that the scheme is not CCA1-secure. Indeed, almost every somewhat homomorphic construction proposed till now in the literature is vulnerable to this kind of attack, hence our result indicates that building CCA1-secure homomorphic schemes is not trivial. We also provide tables showing how the multiplicative depth is affected when the critical parameter B_{key} is chosen in order to mitigatte the attack.

### 2013

#### Lightweight Cryptography for Embedded Systems - A Comparative Analysis

*Charalampos Manifavas, George Hatzivasilis, Konstantinos Fysarakis, and Konstantinos Rantos*

There is a variety of cryptographic mech- anisms which can be used to safeguard the condentiality and integrity of stored and transmitted information. In the context of embedded systems, however, the problem at hand is exacerbated by the resource-constrained nature of the devices, in conjunction with the persistent need for smaller size and lower production costs. This paper provides a comparative anal- ysis of lightweight cryptographic algorithms applicable to such devices, presenting recent advances in the eld for symmetric and asymmetric algorithms as well as hash functions. A classication and evaluation of the schemes is also provided, utilizing relevant metrics in order to assess their suitability for various types of embedded systems.

### 2012

#### A Scan-Based Side Channel Attack on the NTRUEncrypt Cryptosystem

*A.A. Kamal, and A.M. Youssef*

Scan-based Design-for-Test (DFT) is a widely deployed technique for testing hardware chips. Using this approach, all flip-flops in the design under test are connected to a scan chain where their states can be scanned out through this chain during the testing phase. Scan-based side channel attacks exploit the information obtained by analyzing the scanned data in order to retrieve secret information from cryptographic hardware devices that are designed with this testability feature. The NTRU encryption algorithm (NTRUEncrypt) is a parameterized family of lattice-based public key cryptosystems which has recently been accepted to the IEEE P1363 standards under the specifications for lattice-based public-key cryptography. In this paper, we present a scan-based side channel attack on NTRUEncrypt hardware implementations that employ scan based DFT techniques. Our attack determines the scan chain structure of the polynomial multiplication circuits used in the decryption algorithm which allows the cryptanalyst to efficiently retrieve the secret key.

### 2010

#### Speed Records for NTRU

*J. Hermans, F. Vercauteren, B. Preneel*

In this paper, NTRUEncrypt is implemented for the first time on a GPU using the CUDA platform. As is shown, this operation lends itself perfectly for parallelization and performs extremely well compared to similar security levels for ECC and RSA giving speedups of around three to five orders of magnitude. The focus is on achieving a high through-put, in this case performing a large number of encryptions/decryptions in parallel.

### 2009

#### Quantum Resistant Public Key Cryptography: A Survey

*R. A. Perlner, D. A. Cooper*

In this paper, the authors survey some of the public key cryptographic algorithms, including NTRU, that have been developed that, while not currently in widespread use, are believed to be resistant to quantum computing based attacks and discuss some of the issues that protocol designers may need to consider if there is a need to deploy these algorithms at some point in the future.

#### Choosing NTRU Parameters in Light of Combined Lattice Reduction and MITM approaches

*P. Hirschhorn, J. Hoffstein, N. Howgrave-Graham, W. Whyte*

This paper describes parameters secure against the attacks of 2007. The paper, for the first time, details all the conservative assumptions that have been made in order to quantify the security level of parameter sets against both the conservative assumptions and the best current known implementations.

### 2007

#### New Chosen-Ciphertext Attacks on NTRU

*N. Gama, P. Nguyen*

If there is a decryption failure in NTRUEncrypt, and the decrypter outputs the result of the raw decryption operation (in other words, with no padding scheme or error checking applied), then the sender can recover the private key with a very small number of such outputs. It's not clear that this is a realistic attack model as, with a standard padding scheme, the decrypter will detect the error and output an error message rather than returning any data to the sender.

#### Recovering NTRU Secret Key from Inversion Oracles

*P. Mol, M. Yung*

We consider the NTRU encryption scheme as lately suggested for use, and study the connection between inverting the NTRU primitive (i.e., the one-way function over the message and the blinding information which underlies the NTRU scheme) and recovering the NTRU secret key (universal breaking). We model the inverting algorithms as black-box oracles and do not take any advantage of the internal ways by which the inversion works (namely, it does not have to be done by following the standard decryption algorithm). This allows for secret key recovery directly from the output on several inversion queries even in the absence of decryption failures. Our oracles might be queried on both valid and invalid challenges e, however they are not required to reply (correctly) when their input is invalid. We show that key recovery can be reduced to inverting the NTRU function. The efficiency of the reduction highly depends on the specific values of the parameters. As a side-result, we connect the collisions of the NTRU function with decryption failures which helps us gain a deeper insight into the NTRU primitive.

#### Timing attacks on NTRUEncrypt via variation in the number of hash calls

*J. H. Silverman, W. Whyte*

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.

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

*N. Howgrave-Graham*

This paper describes an improved attack on NTRUEncrypt parameters. This resulted in the creation of new new parameters presented in 2009.

### 2005

#### Choosing Parameter Sets for NTRUEncrypt with NAEP and SVES-3

*N. Howgrave-Graham, J. Pipher, J. H. Silverman, W. Whyte*This paper has been superseded by this one.

### 2004

#### Parallel Symmetric Attack on NTRU using Non-Deterministic Lattice Reduction

*T. E. Seidel, D. Socek, M. Sramka*Currently, the most efficient passive attack on the NTRU public-key cryptosystem, proposed by Coppersmith and Shamir, is based on finding a short enough vector in an integral lattice. An NTRU lattice possesses a cyclic automorphism group whose symmetry may be exploited. We have designed methods for reducing bases of NTRU integral lattices based on this symmetry. In addition to these methods, we use hill-descending techniques to combine new and proposed lattice-reduction algorithms. This approach includes deterministic and non-deterministic components which may be efficiently parallelized.

### 2003

#### Estimating Decryption Failure Probabilities for NTRUEncrypt

*J. H. Silverman, W. Whyte*

The paper discusses how to analyze the probability of an NTRUEncrypt decryption failure, and demonstrates that there are parameter sets which reduce the probability of a decryption failure to less than 2-80 for N=251.

#### A meet-in-the-middle attack on an NTRU private key

*N. Howgrave-Graham, J. H. Silverman, W. Whyte*

This note describes a technique, originally due to Odlyzko, for trading off memory for time in searching for an NTRUEncrypt private key by a brute-force method. It demonstrates that for recommended parameter sets with N=251 the strength against meet-in-the-middle attacks is at least 280. However the analysis does not address the attack given in 2007.

#### Enhanced NTRU cryptosystem eliminating decryption failures

*J. Yao, G. Zeng*

This paper aims to eliminate decryption failures from NTRUEncrypt. However this can be done simply by choosing parameters accordingly (e.g. increasing q). Also the existence of decryption failures is not considered a weakness by NTRU if decryption failures occur with negligible probabiliy (w.r.t. the security parameter), and a good padding scheme is used (e.g. NAEP).

#### A Wrap Error Attack Against NTRUEncrypt

*T. Meskanen, A. Renvall*

The paper describes an attack on NTRUEncrypt as described in EESS#1 with the SVES-1 padding scheme. The attack uses decryption failures to recover the private key, exploiting the fact that the chosen parameter sets do not constrain r to be binary.

#### Imperfect Decryption and an Attack on the NTRU Encryption Scheme

*J. Proos*

The paper describes an attack on NTRUEncrypt as described in early NTRU papers with p=3 and different padding schemes. The attack uses decryption failures to reduce the size of the lattice problem that must be solved to recover the private key. The attack is successful with relatively few messages, emphasizing the importance of choosing the correct padding scheme and a parameter set that reduces the chance of decryption failures.

#### On the Bit Security of NTRUEncrypt

*M. Naslund, I. Spharlinski, W. Whyte*

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

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

This paper describes an attack on NTRU as described in EESS#1 with the SVES-1 or SVES-2 padding scheme. The attack uses decryption failures to recover the private key with about 240 queries to a decryption oracle. It illustrates the importance of choosing parameter sets such that the chance of decryption failures is negligible.

#### Key recovery attacks on NTRU without ciphertext validation routine

*D. Han, J. Hon, J. W. Han, and D. Kwon*

NTRU is an efficient public-key cryptosystem proposed by Hoffstein, Pipher, and Silverman. Assuming access to a decryption oracle, we show ways to recover the private key of NTRU systems that do not include a ciphertext validating procedure. The strongest of our methods will employ just a single call to the oracle, and in all cases, the number of calls needed will be small enough to be realistic.

#### NAEP: Provable Security in the Presence of Decryption Failures

*N. Howgrave-Graham, J. Pipher, J. H. Silverman, W. Whyte*

This paper presents a padding scheme appropriate for cryptosystems with a non-zero but negligible average-case chance of decryption failure. It explains the application of this padding scheme to NTRUEncrypt and gives a proof of security. This is the first full proof of security for NTRUEncrypt, demonstrating that the problem of breaking NTRUEncrypt reduces to the problem of finding a close vector in a specific lattice.

### 2002

#### Analysis and Improvements of NTRU Encryption Paddings

*P. Q. Nguyen, D. Pointcheval *

The paper analyses the security against chosen plaintext attack given by three different padding schemes proposed for NTRUEncrypt. It demonstrates that care must be taking when adding random data to a message to ensure that the random data gives full protection against brute-force distinguishing attacks.

#### Imperfect Decryption and an Attack on the NTRU Encryption Scheme

*J. Hong, J. W. Han, D. Kwon, D. Han*

Originally named "Chosen-Ciphertext Attacks on Optimized NTRU", the paper describes an attack on NTRUEncrypt without the use of a specially designed padding scheme. The paper illustrates the importance of choosing the correct padding scheme for a public-key encryption algorithm such as NTRUEncrypt.

### 2001

#### Key Recovery and Message Attack on NTRU-Composite

*C. Gentry*

The paper presents a clever attack that would work against NTRUEncrypt if NTRUEncrypt were ever deployed with the security parameter N not a prime number. In practice, NTRU Cryptosystems has strongly recommended that N always be prime. Indeed, all commercial implementations conform to NTRU's recommendations, and are immune to this attack.

### 2000

#### A chosen-ciphertext attack against NTRU

*E. Jaulmes, A. Joux*

Chosen-ciphertext attacks exist for all public key cryptosystems, including RSA, ECC and NTRUEncrypt. Such attacks may be possible even if the underlying hard mathematical problem is secure. They typically rely on sending specially constructed fake messages to a decryptor and watching to see what happens. If the underlying cryptographic primitive is secure, a well-chosen padding scheme will typically prevent chosen ciphertext attacks. The Jaulmes-Joux paper presents an interesting chosen-ciphertext attack against NTRUEncrypt with the padding schemes that were recommended at the time; the recommended padding schemes have since been altered.

### 1997

#### Lattice attacks on NTRU

*D. Coppersmith, A. Shamir*

The paper presents some early cryptanalysis of NTRU, including the first publication of the "NTRU lattice basis", and an argument showing small vectors that are not necessarily the NTRU private key are sufficient for successful decryption. However these other short vectors appear no easier to find than the NTRU private key.

## NTRU Sign

### 2012

#### Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures

*L. Ducas, P. Q. Nguyen.*

At Asiacrypt '12 Ducas and Nguyen presented a key-recovery attack on NTRUSign with Perturbations, a scheme which had previously been believed to withstand the 2006 attack of Nguyen and Regev. This new work demonstrates that a small number of perturbations is insufficient to mask the local minima unveiled by principal component analysis and gradient descent techniques. The team was able to recover an NTRUSign-251 key from a single perturbation transcript of 8000 signatures in less than one day of computation. It is claimed that the attack can be extended to transcripts with more than one perturbation. In the light of this result, the NTRU research team is investigating alternative approaches to signatures in the NTRU lattice for which it may be possible to base security against transcript attacks on provable statements.

### 2009

#### Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures

*P. Q. Nguyen, O. Regev *

Lattice-based signature schemes following the Goldreich–Goldwasser–Halevi (GGH) design have the unusual property that each signature leaks information on the signer’s secret key, but this does not necessarily imply that such schemes are insecure. At Eurocrypt ’03, Szydlo proposed a potential attack by showing that the leakage reduces the key-recovery problem to that of distinguishing integral quadratic forms. He proposed a heuristic method to solve the latter problem, but it was unclear whether his method could attack real-life parameters of GGH and NTRUSign. Here, we propose an alternative method to attack signature schemes à la GGH by studying the following learning problem: given many random points uniformly distributed over an unknown n-dimensional parallelepiped, recover the parallelepiped or an approximation thereof. We transform this problem into a multivariate optimization problem that can provably be solved by a gradient descent. Our approach is very effective in practice: we present the first successful key-recovery experiments on NTRUSign-251 without perturbation, as proposed in half of the parameter choices in NTRU standards under consideration by IEEE P1363.1. Experimentally, 400 signatures are sufficient to recover the NTRUSign-251 secret key, thanks to symmetries in NTRU lattices. We are also able to recover the secret key in the signature analogue of all the GGH encryption challenges.

### 2008

#### Analysis of Ntrusign

*R. Lindner*

### 2007

#### A Countermeasure for Protecting NTRUSign against the Transcript Attack

*S. Hasegawa, S. Isobe, M. Mambo, H. Shizuya, Y. Futa, M. Ohmori *

NTRUSign is a lattice-based digital signature scheme proposed by Hoffstein et al. NTRUSign is quite different from many other signature schemes in a sense that its security depends on neither the integer factorization problem nor the discrete logarithm problem but on a geometric problem called the close vector searching problem. However, it is known that there is some vulnerability in NTRUSign, namely there is an attack called the transcript attack. In this paper, we propose a countermeasure for protecting NTRUSign against the transcript attack, and give an improved NTRUSign algorithm.

### 2006

#### A Note on the Security of NTRUSign

*P. Q. Nguyen*

At Eurocrypt '06, Nguyen and Regev presented a new key-recovery attack on the Goldreich- Goldwasser-Halevi (GGH) lattice-based signature scheme: when applied to NTRUSign-251 without perturbation, the attack recovers the secret key given only 90,000 signatures. At the rump session, Whyte speculated whether the number of required signatures might be significantly decreased to say 1,000, due to the special properties of NTRU lattices. This short note shows that this is indeed the case: it turns out that as few as 400 NTRUSign-251 signatures are sufficient in practice to recover the secret key. Hence, NTRUSign without perturbation should be considered totally insecure.

### 2005

#### Performace Improvements and a Baseline Parameter Generation Algorithm for NTRUSign

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

This is the most up-to-date paper on NTRUSign at the moment, but is not fully secure against the hybrid attacks of 2007.

### 2003

#### Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures

*M. Szydlo*

The paper considers a problem that arises naturally in the context of NTRUSign signature transcript analysis, the Gram Matrix Problem of recovering a unitary matrix U from its Gram matrix G = UUT. It shows this is polynomial-time equivalent to a problem which is conjectured to be simpler. This result does not affect the advertised security of NTRUSign, as the advertised security of NTRUSign does not depend on that the Gram Matrix problem is hard (and, in fact, assumes that it is easy).

#### Computing the $M = U U^t$ integer matrix decomposition

*N. Smart, K. Geissler *

The cryptanalysis of Gentry and Szydlo of the revised NTRU signature scheme requires the computation of the integer matrix decomposition M = U Ut. We propose a heuristic algorithm to compute this decomposition and investigate its properties. Our test implementation of this algorithm in Magma is able to deal with matrices up to 158 rows and columns.

### 2002

#### NTRUSign: Digital Signatures Using the NTRU Lattice

*J. Hoffstein, N. Howgrave-Graham, J. Pipher, J.H. Silvernman, and 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-CVR 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.

#### Cryptanalysis of the revised NTRU Signature Scheme

*C. Gentry, M. Szydlo*

The paper demonstrated that the (now abandoned) NSS algorithm was insecure. It also showed how an attacker could recover information from a transcript of signatures generated by the NTRUSign algorithm. The use of perturbations, as recommended in the NTRUSign paper presented at CT-RSA 2003, can essentially eliminate the information leakage from transcripts.

### 2001

#### Cryptanalysis of the NTRU Signtare Scheme (NSS) from Eurocrypt 2001

*C. Gentry, J. Jonsson, J. Stern, M. Szydlo*

In 1996, a new cryptosystem called NTRU was introduced, related to the hardness of finnding short vectors in specific lattices. At Eurocrypt 2001, the NTRU Signature Scheme (NSS), a signature scheme apparently related to the same hard problem, was proposed. In this paper, we show that the problem on which NSS relies is much easier than anticipated, and we describe an attack that allows efficient forgery of a signature on any message. Additionally, we demonstrate that a transcript of signatures leaks information about the secret key: using a correlation attack, it is possible to recover the key from a few tens of thousands of signatures. The attacks apply to the recently proposed parameter sets NSS251-3-SHA1-1, NSS347-3-SHA1-1, and NSS503-3-SHA1-1 in [15]. Following the attacks, NTRU researchers have investigated enhanced encoding/verification methods in [8].

## Lattice Reduction

### 2015

#### Provably Weak Instances of Ring-LWE

*Y. Elias, K.E. Lauer, E. Ozman, and K.E. Stange*

The *ring and polynomial learning with errors* problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring- LWE problem for general number rings and demonstrate *provably weak instances* of Ring- LWE. We construct an explicit family of number elds for which we have an ecient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in *q*, where *q* is the modulus.

Our attack is based on the attack on Poly-LWE which was presented in [EHL]. We extend the EHL-attack to apply to a larger class of number elds, and show how it applies to attack Ring-LWE for a heuristically large class of elds. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the rst weak instances of the Ring-LWE problem. We also provide additional examples of elds which are vulnerable to our attacks on Poly-LWE, including power-of-2 cyclotomic elds, presented using the minimal polynomial of ?_{2n}±1.

### 2007

#### Isodual Reduction of Lattices

*N. Howgrave-Graham*

The paper proposes proposes a new lattice reduction algorithm that proves to be more efficient than previously known lattice reduction algorithms, such as BKZ, if there is no particularly short vector in the lattice. This makes it particularly well suited to reducing sublattices as in the hybrid attacks of 2007.

### 2006

#### Symplectic Lattice Reduction and NTRU

N. Gama, N. Howgrave-Graham, P. Nguyen

This paper shows that an NTRU public basis and an NTRU private basis have a special structure, namely that they are proportional to symplectic matrices. In fact the paper shows one can change from the public basis to the private basis using only symplectic transformations during lattice reduction. The observation is interesting from a mathematical point of view, since it shows how lattice reduction can exploit the symplectic structure, and incidentally actually improves the best known integer Gram Schmidt algorithm. However the evidence given in this paper does not show that the symplectic property gives more than a constant improvement over traditional reduction strategies, and therefore does not seem to threaten the security of NTRU.

#### Rankin's Constant and Blockwise Lattice Reduction

*N. Gama, N. Howgrave-Graham, H. Koy, P. Q. Nguyen*

Lattice reduction is a hard problem of interest to both public-key cryptography and cryptanalysis. Despite its importance, extremely few algorithms are known. The best algorithm known in high dimension is due to Schnorr, proposed in 1987 as a block generalization of the famous LLL algorithm. This paper deals with Schnorr's algorithm and potential improvements. We prove that Schnorr's algorithm outputs better bases than what was previously known: namely, we decrease all former bounds on Schnorr's approximation factors to their (In 2)-th power. On the other hand, we also show that the output quality may have intrinsic limitations, even if an improved reduction strategy was used for each block, thereby strengthening recent results by Ajtai. This is done by making a connection between Schnorr's algorithm and a mathematical constant introduced by Rankin more than 50 years ago as a generalization of Hermite's constant. Rankin's constant leads us to introduce the so-called smallest volume problem, a new lattice problem which generalizes the shortest vector problem, and which has applications to blockwise lattice reduction generalizing LLL and Schnorr's algorithm, possibly improving their output quality. Schnorr's algorithm is actually based on an approximation algorithm for the smallest volume problem in low dimension. We obtain a slight improvement over Schnorr's algorithm by presenting a cheaper approximation algorithm for the smallest volume problem, which we call transference reduction.

#### Practical Lattice Basis Sampling Reduction

*J. Buchmann, C. Ludwig*

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

### 2005

#### On Estimating the Lattice Security of NTRU

*N. Howgrave-Graham, J. Pipher, J. H. Silverman, W. Whyte*

The paper analyzes the claims of Buchmann and Ludwig and disputes their results.

First, Schnorr fourth-roots the time for Koy's primal-dual method, not the time for BKZ with a certain blocksize, so it is not valid to draw a link between BKZ times and times achieved by their method in the absence of experimental evidence. Second, their claim that their method 3/4-roots running times is unjustified. Third, Schnorr's result is asymptotic and it is not clear that, even if it reduced the time for BKZ, this effect would be noticeable at the moderate dimensions under consideration.

Finally, we explicitly analyze the expected running times of Schnorr's method, applied to the NTRU lattice. In the special case of binary f, Schnorr's algorithm essentially reduces to brute force search with running time about 2^N. In the more general case, we expect the running time of a naïve application of Schnorr's algorithm to be superexponential. Since the Ludwig/Buchmann algorithm is admitted to be less efficient in general than Schnorr's algorithm, we consider it unlikely that it impacts the security of the current NTRU parameter sets.

### 2003

#### Hypercubic Lattice Reduction and Analysis of GGH and NTRU Signatures

*M. Szydlo*

The paper considers a problem that arises naturally in the context of NTRUSign signature transcript analysis, the Gram Matrix Problem of recovering a unitary matrix U from its Gram matrix G = UUT. It shows this is polynomial-time equivalent to a problem which is conjectured to be simpler. This result does not affect the advertised security of NTRUSign, as the advertised security of NTRUSign does not depend on that the Gram Matrix problem is hard (and, in fact, assumes that it is easy).

### 2001

#### The Two Faces of Lattices in Cryptology

*P. Q. Nguyen, J. Stern*

Lattices are regular arrangements of points in n-dimensional space, whose study appeared in the 19th century in both number theory and crystallography. Since the appearance of the celebrated Lenstra-Lenstra-Lovasz lattice basis reduction algorithm twenty years ago, lattices have had surprising applications in cryptology. Until recently, the applications of lattices to cryptology were only negative, as lattices were used to break various cryptographic schemes. Paradoxically, several positive cryptographic applications of lattices have emerged in the past five years: there now exist public-key cryptosystems based on the hardness of lattice problems, and lattices play a crucial role in a few security proofs. We survey the main examples of the two faces of lattices in cryptology.

## Implementations

### 2008

#### Comparison of innovative asymmetric signature schemes for WSNs

*B. Driessen, A. Poschmann, C. Paar *

Despite the fact that there exist a variety of asymmetric algorithms, publications dealing with implementation of public key schemes for WSN only focus on RSA and ECC. In order to close this gap we have investigated the e?ciency and suitability of two innovative asymmetric algorithms forWSN – namely XTR-DSA and NTRUSign – in direct comparison to the de-facto standard for lightweight signature applications ECDSA. However, past and present attacks on the NTRU-based scheme weakened the trust into NTRUSign, it should be awaited if NTRUSign becomes stable before using it in security critical applications. Nevertheless, our implementation results show that NTRUSign requires 619ms to generate and 78ms to verify a signature. This is significantly less than any other digital signature scheme published so far. At the same time the memory requirements of 11.3kB ROM and 542B RAM are moderate making it an interesting candidate for usage in WSN.

#### Efficiency Improvements for NTRU

*R. Lindner, J. Buchmann, M. Doering*

The NTRU encryption scheme is an interesting alternative to well-established encryption schemes such as RSA, ElGamal, and ECIES. The security of NTRU relies on the hardness of computing short lattice vectors and thus is a promising candidate for being quantum computer resistant. There has been extensive research on efficient implementation of the NTRU encryption scheme. In this paper, we present a new algorithm for enhancing the performance of NTRU. The proposed method is between 11% and 23% faster on average than the best previously known method. We also present a highly efficient implementation of NTRU within the Java Cryptography Architecture.

### 2007

#### Sliding Window Method for NTRU

*M. Lee, J. Kim, J. Song, K. Park*

The NTRU cryptosystem is a ring-based public key system using hard problems over lattices. There has been an extensive research on efficient implementation of NTRU operations, including recent results such as Bailey et al.'s software implementation over a resource-constrained device and Gaubatz et al.'s hardware implementation using only 3,000 gates. In this paper, we present a new algorithm to improve further the performance of NTRU. We speed up the encryption and decryption operations of NTRU up to 32% using some temporary memory, and if we can use precomputation, then the speed-up becomes up to 37%. Our method is based on the observation that specific sub-operations are repeated frequently in the underlying polynomial operations of NTRU.

### 2006

#### Cryptography for Ultra-Low Power Devices (PhD dissertation)

*J.-P. Kaps*

This thesis demonstrates that public key cryptography is possible on ultra-low power devices, using Rabin, NTRUEncrypt, and ECC as candidate algorithms. It concludes that:

- Due to its asymmetry, Rabin’s scheme is particularly suitable if only encryption and signature verification are performed on the node. Otherwise it is comparable to ECC.
- Ntru has the smallest average power consumption, but the largest message size of 5 packets. In environments where transmission power is not the most dominant part, Ntru has an advantage.
- ECC has a small message expansion for encryption and a high power consumption but requires the smallest number of packets. Also, the message content (key material) rarely exceeds 200 bits. On most WSN nodes, transmitting a single bit costs as much power as executing 1000 instructions. Small message sizes and low overhead is of utmost importance which is a feature of ECC.

### 2005

#### Capabilities and Performance of a JCE Implementation of NTRU Public Key Cryptosystem

*K. Kadati, K. Bhimavarapu, George Koodarappally*

An implementation of the original NTRUEncrypt parameters, comparing performance in C, Java, and JNI.

### 2004

#### An algebraic approach to NTRU (q = 2^n) via Witt vectors and overdetermined systems of nonlinear equations.

*N. Smart, F. Vercauteren, J. H. Silverman*

We use the theory of Witt vectors to develop an algebraic approach for studying the NTRU primitive with q-parameter equal to a power of two. This results in a system of nonlinear algebraic equations over GF(2) having many symmetries, which is reminiscent of the approach of Courtois, Murphy, Pieprzyk, Robshaw and others for studying the structure of block ciphers such as the AES. We study whether this approach to NTRU provides any immediate security threat and conclude that under the most favourable assumptions, the method is of asymptotic interest but is completely impractical at current or likely future parameter sizes.

### 2003

#### Achieving NTRU with Montgomery Multiplication

*B. Sunar, C. M. O'Rourke*

The performance and application analysis conducted on the new unified core has demonstrated that all three types of applications, RSA, ECC, and NTRU, can be achieved with high performance on small footprint. It is interesting to note that 503 NTRU offers the best performance for its security level compared to the other two applications. For instance, NTRU with N = 503 provides a security level comparable to 4,096-bit RSA with an additional 2 ms over a short exponent 1,024-bit RSA operation.

### 2002

#### Efficient NTRU Implementations (Master's Thesis)

*C. M. O'Rourke*

To quote from the conclusions section:

"The research has demonstrated that the NTRU multiplier presents a wide range of time/area configurations. For instance, for embedded applications where low power consumption is critical, a single processing unit design can perform a polynomial multiplication in 0.9 ms with less than 1500 gates.

[...]

For the unified design, this research has demonstrated that the Montgomery Multiplication algorithm can be used to perform modular multiplications for GF(p) and GF(2k) and polynomial multiplications for NTRU. In addition, only 10 gates of additional hardware are required for the Montgomery Multiplier core to provide support for NTRU. The performance and application analysis demonstrated that all three types of applications RSA, ECC, and NTRU can be executed by the unified architecture with high performance. It is interesting to note that 503 NTRU offers the best performance for its security level compared to the other two applications. With an additional 2 ms over a short exponent 1024-bit RSA operation, 503 NTRU provides a security level comparable to 4096-bit RSA."

## Variants

### 2013

#### ETRU: NTRU over the Eisenstein Integers

*K. Jarvis, M. Nevins*

NTRU is a public-key croptosystem based on polynomial rings over Z. Replacing Z with the ring of Eisenstein integers yields ETRU. We prove through both theory and implementation that ETRU is faster and has smaller keys for the same or better level of security than does NTRU.

### 2008

#### Algebraic Cryptanalysis of CTRU Cryptosystem

*N. Vats*

CTRU, a public key cryptosystem was proposed by Gaborit, Ohler and Sole. It is analogue of NTRU, the ring of integers replaced by the ring of polynomials . It attracted attention as the attacks based on either LLL algorithm or the Chinese Remainder Theorem are avoided on it, which is most common on NTRU. In this paper we presents a polynomial-time algorithm that breaks CTRU for all recommended parameter choices that were derived to make CTRU secure against popov normal form attack. The paper shows if we ascertain the constraints for perfect decryption then either plaintext or private key can be achieved by polynomial time linear algebra attack.

#### CTRU, a polynomial analogue of NTRU

*P. Gaborit, J. Ohler, P. Sole*

This paper descibes a generalization of NTRU to function fields, but the proposed scheme has been shown to be insecure.

### 2005

#### Efficient Traitor Tracing Scheme Based On NTRU

*X. Lv, B. Yang, C. Pei *

Since its introduction, broadcast encryption has attracted many useful applications. One major problem faced by such broadcast systems is "piracy." An effective approach to piracy prevention in such systems is traitor tracing. In this paper, a new traitor tracing scheme is proposed by using the efficient and computationally inexpensive public key cryptosystem NTRU. The proposed scheme is the first concrete construction of NTRU-based public-key traitor tracing and has the advantages of extremely efficient encryption and decryption, fast and easy key creation, low memory requirements and revocation property etc. Moreover, this novel work contains other desirable features, such as Collusion-resistant, which the previous traitor tracing schemes did not offer. In addition, with its complexity only O(log2n), the tracing algorithm of this system is more efficient than that of the previous ones.

#### MaTRU, A New NTRu-Based Cryptosystem

*M. Coglianese, B.-M. Goi*

In this paper we propose a new variant of the NTRU public key cryptosystem -- the MaTRU cryptosystem. MaTRU works under the same general principles as the NTRU cryptosystem, except that it operates in a different ring with a different linear transformation for encryption and decryption.

**2002**

#### A Variant of NTRU with Non-invertible Polynomials

*W. D. Banks, I. E. Shparlinski*

We introduce a generalization of the NTRU cryptosystem and describe its advantages and disadvantages as compared with the orig- inal NTRU protocol. This extension helps to avoid the potential problem of finding "enough" invertible polynomials within very thin sets of poly- nomials, as in the original version of NTRU. This generalization also exhibits certain attractive "pseudorandomness" properties that can be proved rigorously using bounds for exponential sums.