Questions tagged [ntru]
NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.
114 questions
3
votes
1
answer
165
views
What Makes Single-Part Ciphertext Possible in NTRU, and Why Do LWE Schemes Typically Need Two Parts?
Both LWE-based and NTRU-based PKE/KEMs are lattice-based cryptographic approaches. Why do LWE-based schemes typically require two parts in the ciphertext, while NTRU-based schemes need only one single ...
- 55
1
vote
1
answer
82
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
129
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 ...
- 33
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\...
- 51
5
votes
1
answer
253
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 ...
- 101
1
vote
1
answer
152
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 ...
- 51
9
votes
2
answers
744
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 ...
- 880
1
vote
1
answer
116
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 ...
- 161
3
votes
0
answers
63
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
350
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 ...
- 175
2
votes
1
answer
99
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 ...
- 23
1
vote
1
answer
131
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
2
votes
0
answers
48
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
84
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?
- 483
3
votes
1
answer
294
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
3
votes
0
answers
114
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 ...
- 278
2
votes
1
answer
135
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
160
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 ...
- 219
2
votes
2
answers
150
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 ...
- 219
3
votes
1
answer
101
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 ...
- 425
2
votes
1
answer
179
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 ...
2
votes
1
answer
216
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 ...
- 425
0
votes
1
answer
63
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 ...
0
votes
0
answers
57
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
1
vote
0
answers
62
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
3
votes
1
answer
963
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
4
votes
0
answers
550
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 ...
- 41
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. ...
- 381
3
votes
1
answer
341
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 ...
- 325
1
vote
0
answers
30
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,795
1
vote
0
answers
145
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 ...
maciek
2
votes
1
answer
98
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. ...
- 381
2
votes
0
answers
151
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 ...
- 483
4
votes
1
answer
98
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 ...
- 143
3
votes
0
answers
170
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
0
votes
0
answers
157
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
4
votes
1
answer
429
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 ...
- 237
1
vote
1
answer
525
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 ...
- 51
4
votes
1
answer
568
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.
...
- 237
2
votes
1
answer
685
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 ...
- 237
1
vote
1
answer
120
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, ...
- 381
2
votes
1
answer
257
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 ...
- 237
2
votes
0
answers
225
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
1
vote
0
answers
35
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$, ...
- 111
0
votes
1
answer
190
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{...
0
votes
0
answers
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.
0
votes
1
answer
99
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 ...
- 143
4
votes
1
answer
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 ...
1
vote
1
answer
370
views
Fully Homomorphic Encryption - state of the art
What are the latest advances in fully homomorphic encryption? First of all, I am interested in cryptosystems based on LWE / RLWE and NTRU problems.
- 143
1
vote
1
answer
66
views
NTRUEncrypt polynomial $r$ Uniqueness
During the encryption process in NTRU, a random polynomial $r$ of small coefficients is generated to bind to the message to obscure it, and this polynomial must be kept secret. Does this polynomial ...
- 623