# Questions tagged [ntru]

NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.

107 questions
Filter by
Sorted by
Tagged with
49 views

### Are high-dimensional versions of NTRU cryptosystem more secure?

The basis for this question is a 1-dimensional NTRU cryptosystem. After some literature inspection I have found out it can be also generalised into higher algebras: quaternions (QTRU) and octonions (...
268 views

### NTRU Cryptosystem: Why "rotated" coefficients of key f work the same as f

In the NTRU cryptosystem, we can use a randomly generated polynomial f that is inversible under modulo p and q to encrypt and decrypt our plaintext. While studying this system, I attempted to ...
79 views

### in NTRU, can g be recovered given f and h?

The NTRU key generation involves polynomials and their arithmetic in polynomial rings, which is a bit different from arithmetic in modular integers. In the NTRU cryptosystem, the public key $h$ is ...
1 vote
86 views

### How does big Galois groups yield better security in NTRU Prime?

I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people. Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how ...
43 views

### is it safe to reuse the public key in NTRUEncrypt?

Looking at https://github.com/tbuktu/libntru/blob/master/src/ntru.h, there are some functions that deal with having multiple public keys with the same private key. I don't believe I need such ...
43 views

### worst case to average case reduction in non-cyclotomic Ring LWE

I understand that we need 2-to-power cyclotomic ring to show that the solving decision RLWE is as hard as solving search RLWE. Is there any chance to prove it without 'cyclotomic' property? For ...
1 vote
71 views

### Hardness of a modified version of NTRU

Let the modified NTRU be $h=f/g$ such that $f$ is not necessarily a short polynomial, is the NTRU problem still hard in this case?
62 views

### What is the exact assumption behind OW-CPA of NTRU?

As shown in this paper the IND-CPA of NTRU is based on both the decision key cracking problem and the decision ciphertext cracking problem. However, I often see claims (such as in this paper) that the ...
272 views

### NTRUEncrypt fails on sedonion algebra

This question is a direct follow-up (hopefully - the last) of my previous one; please see it for full information. I would like to further generalise NTRU cryptosystem on higher-order algebras. ...
116 views

### NTRUEncrypt fails on quaternion algebra

This is a follow-up of my previous two questions (1 and 2), might be relevant to check them out first for a full context. I am trying to re-create results from this paper. The basic algorithm is ...
1 vote
133 views

### NTRUEncrypt fails on complex algebra

I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the ...
133 views

### Why does NTRUEncrypt fail on different values for large modulus?

I am trying to closely follow the algorithm here (keeping the same variable names) and reconstruct the cryptosystem in Sage Math engine. It seems to work on parameters ...
96 views

### Do ideal non-cyclotomic lattices provide better compression in lattice-based cryptography?

Let $f \in \mathbb{Z}[x]$ be an irreducible polynomial of degree $N$ and $q \in \mathbb{N}$. Consider the rings $R := \mathbb{Z}[x]/f$ and $R_q := R/q$. Obviously, an element of $R_q$ can be ...
154 views

### Dense sphere packings and lattice-based cryptography

It is known that there are two popular applications of lattices: dense sphere packings and lattice-based cryptography. I didn't find any information on the Internet about possible interaction of these ...
1 vote
111 views

### Basis matrix of NTRU lattice

In NTRUEncrypt, we choose polynomials $\mathbf f,\mathbf g$ (with suitably small coefficients) such that $\mathbf f$ admits inverses $\mathbf f_p, \mathbf f_q$ with respect to the moduli $p,q$. The ...
51 views

### MITM against NTRU

In MITM attacks against the NTRU cryptosystem, we exploit the fact that in the ring of truncated polynomials of degree $n-1$ it holds that $$fg=h\mod q$$ for our secret and public keys $f,h$. The ...
330 views

### Is reverse NTRU still secure? (Looking for a signature scheme)

I'm currently prototyping something with the NTRU encryption scheme but I wish to use it in "reverse" -- distribute private keys so anyone can decrypt, but keep the public keys secret and thus only ...
51 views

### The special case of NTRUEncrypt when N = q

I've found this task in the "Introduction Mathematical Cryptography by Jeffrey Hoffstein": The guidelines for choosing NTRUEncrypt public parameters (N, p, q, d) in-clude the assumption that ...
878 views

### Is the combination of X25519 ECDH and NTRU in OpenSSH 9.X secure against quantum attacks?

Can the combination of X25519 ECDH and NTRU in OpenSSH 9.X defend me against quantum attacks? Why is it believed that this combination is secure?
1 vote
53 views

### Why will the polynomial f almost always have an inverse for NTRU?

In many NTRU material it is said that with our choice of the polynomial $f$, it will almost always have an inverse. Maybe it's a stupid question, but why will it almost always have an inverse element? ...
209 views

### NTRUencrypt in NIST competition

Why did the NTRUencrypt team not maintain the NTRU1024 release in the NIST second-round competition? Is this because of the speed performance or security performance or other things?
436 views

### Is the IEEE 1363.1 standard of NTRU post-quantum secure?

I have a question regarding the IEEE 1363.1 standard for NTRU with padding, which offers CCA security. Does the IEEE standardized implementation offer post-quantum security as well? Also, what are the ...
1k views

### What is the most efficient attack on NTRU?

So, I got how finding the private key is equivalent to resolving the SVP. I also understood that the LLL algorithm can only be used in small dimensions. Now, I wonder what is the most efficient attack ...
292 views

### What kind of operations are involved in NTRU?

I've read that lattice based algorithms involve matrix-vector products. Is this the case of the NTRU algorithm? When I've read the details of the NTRU algorithm, I've seen products of polynoms. Where ...
390 views

### Is Ntru-Encrypt still secure in 2022

I'm going to use NTRU as post-quantum public-key encryption algo in my project. I've googled attacks on NTRU and found a lot of them but since I'm new to NTRU and don't understand the math used, and ...
48 views

### Duality Results for Some Module Lattices

Let $R$ be the ring of integers of a cyclotomic field $\mathbb{Q}(\zeta_n)$, where $n$ is a power of two, and $\boldsymbol{a} \in R_{q}^{m}$, for $m\in\mathbb{Z}^+$, $q\in\mathbb{Z}_{\geq2}$ prime. ...
347 views

### What is the NTRU parameter equivalent to security level 112, 128 and 192?

I came across this paper which mentions this table, which states that NTRU 347 is equivalent to 112 bit security level However, in this paper, Choosing parameters for NTRU mentions that NTRU-401 is ...
332 views

### How to decide if an element is a public key in NTRU encryption scheme?

First, I'm using the settings of https://en.wikipedia.org/wiki/NTRUEncrypt, with $L_f$ set of polynomials with $d_f+1$ coefficients equal to 1, $d_f$ equal to $-1$ and the remaining $N-2d_f-1$ equal ...
1 vote
24 views

### Does EESS#1 NTRUEncrypt use the PKCS#1 MGF (mask generation function)?

I downloaded the 1st-round NTRUEncrypt submission from NIST website, the spec mentions the mask generation function MGF1 in ASN.1 definition but not in algorithm description. Does the EESS#1 ...
1 vote
134 views

### NTRU cryptosystem on complex numbers

Background I am interested in lattice-based cryptography. Recently I got familiar with the NTRU cryptosystem and found out that it can be extended onto hypercomplex numbers, like Quaternions (QTRU) or ...
94 views

### Volume of an NTRU lattice

Let $K$ be a number field of degree $n$ and $\Lambda^q_h=\{(f,g)\in\mathcal{O}_K\text{ : }fh-g = 0\bmod q\mathcal{O}_K\}$, where $h$ is an NTRU public key. Then $\{(1,h),(0,q)\}$ generates a lattice. ...
129 views

### Howgrave-Graham lattice attack on NTRU

I am lookin for a good example to illustrate this attack on NTRU using low parameters but I failed to do that, The attack consist to use LLL reduction on A basis of NTRU Lattice, let us use the column ...
94 views

### Is NTRU still hard if $G$ is set to 1?

I'm looking at the description of NTRUEncrypt given on page 21 of http://archive.dimacs.rutgers.edu/Workshops/Post-Quantum/Slides/Silverman.pdf and using its notation. So in NTRU there are always two ...
168 views

### Lifting a congruence $f(X) \equiv gh (\textrm{mod} \ p)$ to a higher power moduli

I have the polynomial ring $R = \mathbb{Z}[X]/(X^N - 1)$ with $N = 11$ and $h \in R$ with \begin{equation*} h = 7 -11X - 7X^2 -12X^3 + 8X^4 - 11X^5 + -8X^6 + 11X^7 - 4X^8 + 2X^9 + 3X^{10} \end{...
158 views

### Coppersmith attack on NTRU and non-commutativity

In this paper, Coppersmith and Shamir used lattice reduction to attack NTRU. At the very end of the paper, they note that developing non-commutative variants of NTRU would be wise, in light of their ...
1 vote
408 views

### NTRU Euclidean algorithm the inverse of f modulo p

I am very new to the world of cryptography and have just began my research in the post quantum cryptography sector. I have been reading and trying to understand NTRU key generation and am struggling ...
410 views

### What is the largest parameter broken for NTRU?

The original secure parameters for NTRU shown below are from the original HPS98 paper. This is vastly different from the current secure suggested parameters in the NIST PQC round 3 submission. ...
124 views

### Is the NTRU Challenge still ongoing?

In 2016, security innovation released the NTRU challenge. I understand that NTRU is now patent free and it seems like most of the documents related to the NTRU challenge on security innovation's ...
521 views

### How to encode and decode message into polynomial form on NTRU

This question is based on a previously asked question. How to make a message into a polynomial on NTRU encryption? I am tasked to implement NTRU with toy parameters such as $N=7$ or $N=11$ and I have ...
222 views

### Significance of parameter q in NTRU lattice attack

In NTRU (N,p,q,d), N is usually chosen to be prime and q be a power of 2. Why is it that if I increase the parameter q, the probability of finding a key or spurious key that can decrypt the message is ...
1 vote
107 views

### Algebraic Variants of NTRU

There are a large number of algebraic NTRU variants: for example, in some (such as ETRU), the underlying ring has been changed to the ring of integers of a certain number field; there is GR-NTRU, ...
191 views

### NTRU HPS98 vs NTRU-HRSS-KEM vs new NTRU

What is a simple explanation for the difference in terms of key gen, encryption and decryption between the original NTRU (HPS98) and the NTRU candidates submitted in NIST PQ Standardisation? Round 1 - ...
1 vote
34 views

### Sampling polinomials in NTRUEncrypt

Some time ago I read an explanation of the key generation process of NTRUEncrypt, where it was stated that a polynomial $f$ should have "small" coefficients. It defined the number $df$, ...
195 views

### Layered encryption in mixnets with post-quantum cryptography

I am trying to implement a mixnet using post-quantum public-key crypto. Each message may be encrypted by up to 10 levels of public keys, shuffled, before the layers of encryption are stripped off one ...
795 views

### Which attacks are possible against raw/textbook NTRU encryption?

In the same fashion that these questions about attacks to textbook RSA and ECC, I was wondering what are the immediate drawbacks of applying NTRU Encryption directly, without any padding scheme, such ...
62 views

### Calculation expansion factor of $x ^ n - x - 1$

I'm trying to calculate the expansion factor for a polynomial of the form $x ^ n - x - 1$. Any help would be appreciated.
78 views

### Canonical inclusion map in subfield attack on overstretched NTRU

I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf authors used "canonical inclusion map" to lift vector to full lattice. What does ...
1k views

### How to find the inverse of a polynomial in NTRU-PKCS

I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...