Questions tagged [ntru]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
44 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? ...
user avatar
1 vote
1 answer
322 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?
user avatar
3 votes
0 answers
120 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 ...
user avatar
  • 31
2 votes
1 answer
33 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. ...
user avatar
  • 349
3 votes
1 answer
304 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 ...
user avatar
  • 325
2 votes
0 answers
66 views

Basic explanation of Falcon and Dilithium

I've been trying to search for toy examples of the round 3 digital signatures Rainbow, Falcon and Dilithium. Not a lot of actual implementation examples are out there. What I'm searching for are ...
user avatar
  • 21
1 vote
0 answers
20 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 ...
user avatar
  • 6,621
1 vote
0 answers
87 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 ...
user avatar
2 votes
1 answer
71 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. ...
user avatar
  • 349
2 votes
0 answers
90 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 ...
user avatar
4 votes
1 answer
78 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 ...
user avatar
  • 143
3 votes
0 answers
104 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 ...
user avatar
  • 349
0 votes
0 answers
74 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 ...
user avatar
  • 227
4 votes
1 answer
216 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 ...
user avatar
  • 227
1 vote
1 answer
208 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 ...
user avatar
4 votes
1 answer
138 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. ...
user avatar
  • 227
2 votes
1 answer
241 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 ...
user avatar
  • 227
1 vote
1 answer
88 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, ...
user avatar
  • 349
3 votes
1 answer
142 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 ...
user avatar
  • 227
2 votes
0 answers
79 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 - ...
user avatar
  • 227
1 vote
0 answers
28 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$, ...
user avatar
  • 111
0 votes
1 answer
136 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{...
user avatar
0 votes
0 answers
56 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.
user avatar
0 votes
1 answer
58 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 ...
user avatar
  • 103
3 votes
1 answer
813 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 ...
user avatar
1 vote
1 answer
271 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.
user avatar
  • 103
1 vote
1 answer
51 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 ...
user avatar
  • 593
0 votes
1 answer
95 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 ...
user avatar
5 votes
1 answer
193 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?
user avatar
  • 87
1 vote
1 answer
211 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 ...
user avatar
0 votes
1 answer
176 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 ...
user avatar
2 votes
0 answers
229 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)...
user avatar
  • 103
2 votes
1 answer
133 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 ...
user avatar
  • 135
2 votes
1 answer
201 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 ...
user avatar
  • 167
3 votes
2 answers
362 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 ...
user avatar
-1 votes
1 answer
97 views

Decide whether a polynomial is invertible mod $q$

When implementing NTRU related cryptosystem, I came across the problem of deciding whether a randomly generated polynomial is invertible mod $q$. How to solve it?
user avatar
1 vote
1 answer
134 views

Is there is a way to calculate the public key from the private key in pqNTRUSign algorithm?

There is source code of this algorithm (https://github.com/NTRUOpenSourceProject/NTRUMLS). But this algorithm does not provide a function for generating a public key from a private key. Studying the ...
user avatar
2 votes
1 answer
202 views

NTRU homomorphic rerandomization

I am currently implementing NTRU, keeping its homomorphic properties. I want to implement rerandomization like this: Encryption: $e = pr * h + m \pmod q$ Rerandomization: $e = e + pr \pmod q$ (...
user avatar
1 vote
0 answers
318 views

NTRUencrypt: why is it dangerous to use two different ephemeral keys for the same message?

I'm self-studying NTRU encrypt, and I read following in the book "an introduction to mathematical cryptography" -Chapter 6.10-remark 6.50 (Jeffrey hoffstein, Jill Pipher, Joseph H. silverman)...
user avatar
  • 509
2 votes
0 answers
150 views

NTRU-based threshold encryption system?

I want to implement threshold homomorphic encryption for my project. (encrypt a message using one public key, and decrypt a ciphertext using distributed secret keys) I read a paper "Multiparty ...
user avatar
  • 509
2 votes
1 answer
725 views

Key and signature sizes of NTRU and NTRU Prime?

I would have expected this info to be easier to Google Scholar for, but alas I'm asking here. Partial answers: NTRU key size (confused) the public key consists of one ring, and so it takes up $11 ...
user avatar
0 votes
1 answer
648 views

How to find the inverse of f(x) in NTRU key generation?

I work on a project that depends on the NTRU cryptosystem, but I don't know how to find the inverse of $f(x)$. Please see the picture: Please help me to understand this problem.
user avatar
  • 11
6 votes
2 answers
179 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 ...
user avatar
  • 93
-3 votes
1 answer
186 views

Uniform Distribution and discrete Gaussian distribution for NTRU

I want to implement the NTRU cryptosystem. What is the method and algorithm to choose vectors elements from a uniform distribution and discrete Gaussian distribution?
user avatar
  • 87
4 votes
2 answers
1k views

NTRU key size (confused)

I'm evaluating the performance of NTRU; and I got confused. the key size is said to be smaller than RSA but larger than ECC. Using both the reference implementation when I choose APR2011_439 setting ...
user avatar
  • 234
1 vote
1 answer
184 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.
user avatar
  • 325
4 votes
1 answer
673 views

NTRU Backdoor and NewHope TLS Protocol

The pre-print, Unstructured Inversions of NewHope was posted yesterday and uses a backdoor method against NTRU to claim that Grover's algorithm and an inversion oracle could be applied to NewHope. My ...
user avatar
  • 214
2 votes
1 answer
228 views

Message expansion in NTRU: why is it $\log_p(q)$-to-$1$?

Suppose that we are working with the original version of NTRU with parameters $(N,p,q,k,d_f,d_g,d_\phi)$. In this case we are working with the original NTRU with the digital envelope and the ...
user avatar
  • 325
0 votes
1 answer
114 views

In NTRU digital envelope, do everyone know the hash function $H$ used?

I have a simple question about the NTRU original cryptosystem using a digital envelope. The article can be found here: http://grouper.ieee.org/groups/1363/lattPK/submissions/ntru.pdf It is said that ...
user avatar
  • 325
3 votes
0 answers
212 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 (...
user avatar
  • 325