Questions tagged [ntru]
NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.
113
questions
1
vote
0
answers
43
views
Noncommutative generalizations of NTRU
I recently learned and implemented NTRU Encrypt successfully in Python/SageMath. The key players are the polynomial rings $R = \mathbb{Z}[x]/(x^N-1)$ and reduction $R_p = \mathbb{Z}_p[x]/(x^N-1)$.
One ...
- 131
3
votes
1
answer
91
views
What are the recommended parameters for NTRUEncrypt?
I'm looking into NTRU for the first time and I am confused by the variants and the set of parameters. I'd like to use a secure NTRU-based cryptosystem to have a (plausibly) quantum secure PKE offering ...
- 25.5k
5
votes
1
answer
207
views
Shortest Vector Problem as Dihedral Hidden Subgroup Problem
I’m a mathematician trying to get into cryptography. I have a somewhat silly question, but I can’t seem to find a proper answer anywhere. I am interested in whether or not there is a way to directly ...
- 25.5k
0
votes
1
answer
97
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 ...
0
votes
1
answer
109
views
NTRU: Does the ```*``` indicates something more than a simple multiplication, so for that reason omitted from ```ph``` instead of ```p*h```?
I read the literature and more specific a book describing NTRU encryption. Somewhere (among other things) it describes the "encrpyption", etc... between Alice and Bob.
The author writes:
$e\...
- 150k
1
vote
1
answer
147
views
What makes so difficult to calculate the needed vector in NTRU's CVP and SVP problems?
I am reading literature related to NTRU cryptosystem. I have readen many questions in the current Cryptography stackexchange site, But, I still search for some answers:
What makes so difficult to ...
9
votes
2
answers
690
views
Is NTRU broken?
Today a new paper appeared on ePrint, "Improved Provable Reduction of NTRU and Hypercubic Lattices". It claims that:
this is the first provable result showing that breaking NTRU lattices ...
- 1,356
1
vote
1
answer
113
views
Degree of inverse of f in NTRU?
In NTRU, we know that $f$ is a ternary polynomial in the ring $$R=\frac{\mathbb{Z}_q[x]}{x^n-1}.$$
Here $f$ has $d+1$ coefficients 1 and $d$ coefficients $-1$ and rest are zero.
For computing the ...
- 25.5k
7
votes
3
answers
5k
views
Lightweight Asymmetric encryption algorithm
I'm an embedded systems researcher, and new in the crypto field. Actually, I need to know if there are any lightweight asymmetric encryption algorithm especially considering the time needed for key ...
- 41
3
votes
0
answers
62
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 (...
- 219
6
votes
1
answer
331
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 ...
- 49.3k
2
votes
1
answer
94
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 ...
- 49.3k
1
vote
1
answer
119
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 ...
- 13.8k
2
votes
0
answers
47
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 ...
- 33
1
vote
1
answer
80
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?
- 25.5k
3
votes
0
answers
105
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 ...
- 15.4k
3
votes
1
answer
290
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. ...
- 219
2
votes
1
answer
134
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 ...
- 219
1
vote
1
answer
153
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 ...
- 25.5k
2
votes
2
answers
144
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 ...
- 25.5k
3
votes
1
answer
100
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 ...
- 13.8k
2
votes
1
answer
200
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 ...
- 13.8k
2
votes
1
answer
169
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 ...
- 25.5k
0
votes
1
answer
62
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 ...
- 23.1k
4
votes
3
answers
338
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 ...
- 9,692
0
votes
0
answers
56
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 ...
- 21
3
votes
1
answer
945
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?
- 155
1
vote
0
answers
59
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? ...
- 11
5
votes
1
answer
214
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?
- 15.4k
3
votes
2
answers
456
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 ...
- 15.4k
6
votes
1
answer
2k
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 ...
- 15.4k
2
votes
2
answers
312
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 ...
- 15.4k
3
votes
0
answers
520
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 ...
- 23.1k
2
votes
1
answer
52
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. ...
- 13.8k
4
votes
1
answer
427
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 ...
CommunityBot
- 1
3
votes
1
answer
340
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 ...
- 13.8k
1
vote
0
answers
28
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 ...
- 9,692
1
vote
0
answers
142
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 ...
- 94k
2
votes
1
answer
97
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. ...
- 13.8k
2
votes
0
answers
144
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 ...
- 151
4
votes
1
answer
97
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 ...
- 2,625
0
votes
1
answer
180
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{...
CommunityBot
- 1
3
votes
0
answers
169
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 ...
- 381
1
vote
1
answer
474
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 ...
CommunityBot
- 1
4
votes
1
answer
546
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.
...
CommunityBot
- 1
0
votes
0
answers
146
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 ...
- 237
2
votes
1
answer
641
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 ...
- 49.3k
2
votes
1
answer
247
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
1
answer
116
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, ...
- 13.8k
2
votes
0
answers
214
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 - ...
- 237