All Questions
Tagged with ntru lattice-crypto
34 questions
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
9
votes
2
answers
745
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
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
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
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
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
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
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
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
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 ...
4
votes
0
answers
438
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)...
- 143
2
votes
1
answer
298
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 ...
- 187
1
vote
1
answer
190
views
Explain: An NTRU key for a lattice of dimension $d$ has size only $O(d\log{d})$
The associated NTRU lattice is of dimension $d=2N$.
The public and private key sizes are both of length $O(N)=O(d/2)=O(d)$.
So where does the $d\log(d)$ appear?
Thanks in advance.
- 325
3
votes
0
answers
270
views
In NTRU, if $N$ is not prime, prove that one can recover the private key by solving a lattice problem in dimension lower than $2N$
In the NTRU cryptosystem, it is suggested to take $N$ prime.
I want to understand why.
In Jeffrey Hoffstein, Jill Pipher and H. Silverman An Introduction to Mathematical Cryptography, they suggest (...
- 325
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 ...
- 61
2
votes
2
answers
320
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 ...
- 2,897
3
votes
1
answer
775
views
Illustrate NTRU using lattices
I studied some papers related to NTRU. All these papers describe NTRU as a lattice based cryptosystem but I could not find any paper which illustrates NTRU algorithm from lattice point of view. It ...
- 31