Questions tagged [ntru]
NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.
107
questions
3
votes
0
answers
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 (...
- 219
6
votes
1
answer
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 ...
- 175
2
votes
1
answer
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 ...
- 23
1
vote
1
answer
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 ...
- 13
0
votes
0
answers
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 ...
- 1
2
votes
0
answers
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 ...
- 33
1
vote
1
answer
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?
- 421
3
votes
1
answer
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. ...
- 219
2
votes
0
answers
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 ...
- 258
2
votes
1
answer
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 ...
- 219
1
vote
1
answer
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 ...
- 219
2
votes
2
answers
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 ...
- 219
3
votes
1
answer
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 ...
- 395
1
vote
1
answer
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 ...
2
votes
1
answer
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 ...
- 395
0
votes
1
answer
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 ...
0
votes
0
answers
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 ...
- 21
1
vote
0
answers
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? ...
- 11
3
votes
1
answer
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?
- 155
3
votes
0
answers
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 ...
- 31
2
votes
1
answer
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. ...
- 381
3
votes
1
answer
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 ...
- 325
1
vote
0
answers
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 ...
- 9,001
1
vote
0
answers
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 ...
maciek
2
votes
1
answer
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. ...
- 381
2
votes
0
answers
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 ...
- 421
4
votes
1
answer
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 ...
- 143
3
votes
0
answers
156
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
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 ...
- 237
4
votes
1
answer
345
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
407
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
408
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
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 ...
- 237
1
vote
1
answer
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, ...
- 381
2
votes
1
answer
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 ...
- 237
2
votes
0
answers
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 - ...
- 237
1
vote
0
answers
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$, ...
- 111
0
votes
1
answer
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{...
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
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 ...
- 123
3
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
356
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.
- 123
1
vote
1
answer
61
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 ...
- 613
0
votes
1
answer
110
views
Does AES encryption of a NTRU pivate key reduce security?
The NTRU crypto system requires quite long keys. For example with parameters N=439 and q=2048 the security is 128 bits and the key_size is 4829 bits.
When the private key is encrypted with AES-256 ...
5
votes
1
answer
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?
- 87
1
vote
1
answer
324
views
NTRUSign (considered broken) as a one or few time PQ signature scheme
As many know, original NTRUSign is considered broken as signatures leak information about the private key.
It takes a number of signatures to accomplish a break though, with the original break paper ...
- 896
0
votes
1
answer
211
views
NTRU: Possible misunderstending of division and euclidean algorithm for polynomials
Please consider this answer before reading
I am trying to find GCD of two polynomials, but I have some troubles understanding division and euclidean algorithms:
1) In description of division ...
- 1
3
votes
0
answers
365
views
Comparison of NTRU-based schemes and LWE-based schemes
What advantages and disadvantages can be distinguished in NTRU-based and LWE-based schemes relative to each other? In what cases which scheme gives advantage?
UPD: I'm interesting in two things: 1)...
- 123
2
votes
1
answer
152
views
Encrypt your ECDSA signature with NTRU to make them quantum secure, does that work?
I have a general question about quantum security. ECDSA is suppose to be broken by quantum computers. Whilst something like NTRU is suppose to be secure.
My question is: if we sign with ECDSA and ...
- 135
2
votes
1
answer
266
views
Original NTRU : How to calculate the size of private key?
In the original NTRU paper：NTRU: A Ring-Based Public Key Cryptosystem,1996, the author proposes 3 choices of implementation parameters: moderate, high and highest. Let's take moderate security level ...
- 177