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
13 votes
3 answers
2k views

Does NTRU decrypt correctly now?

The NTRU public-key cryptosystem has a lot of interesting properties (being resistant to quantum computer attacks, being standardized by several important bodies), but it also has a pretty unique ...
Jack Schmidt's user avatar
10 votes
2 answers
817 views

Which attacks are possible against raw/textbook NTRU encryption?

In the same fashion that these questions about attacks to textbook RSA and ECC, I was wondering what are the immediate drawbacks of applying NTRU Encryption directly, without any padding scheme, such ...
cygnusv's user avatar
  • 4,952
9 votes
3 answers
2k views

How can one sign with NTRU?

I am looking at implementing NTRU, but I noticed that while the encryption/decryption algorithm seems to be mature and well-documented, there is comparatively little information about how to sign ...
Thomas's user avatar
  • 7,478
7 votes
1 answer
751 views

Secure, patent-free alternative to NTRU

I'm working on a P2P communications and chat framework, and am looking for a quantum-secure asymmetric key exchange algorithm which I can use to perform a key exchange of an AES-256 bit key. This is ...
bbosak's user avatar
  • 961
7 votes
1 answer
1k views

Why does NTRUEncrypt lack a formal security proof?

Is there any particular reason why NTRUEncrypt lacks a formal security proof? That is, a demonstration that it achieves certain security notion (e.g. IND-CPA). I know there is a provable-secure ...
cygnusv's user avatar
  • 4,952
7 votes
2 answers
606 views

Multiple NTRU public keys for the same private key?

An NTRU public key is generated essentially by multiplying the inverse of a polynomial $f$ by a polynomial $g$. The polynomial $f$ is the private key; $g$ is discarded. My question is: Is it insecure ...
devin.omalley's user avatar
6 votes
2 answers
2k views

NTRU crypto from unseen.is; myth busting help

I am always on the look out for privacy enhancing technologies. I stumbled upon the service from unseen.is. I had a look at their site (specifically here) and even though I lack knowledge there are a ...
user3244085's user avatar
6 votes
1 answer
295 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 ...
Ymi's user avatar
  • 175
6 votes
1 answer
1k views

Implementations of Ntru TLS

Has anyone come across any implementations of Ntru TLS? I'm working a project for uni that does quantum secure encryption. It relies on a mix of Ntru & AES, but I can't find an implementation of ...
Saf's user avatar
  • 205
6 votes
1 answer
1k 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 ...
dragonair's user avatar
6 votes
2 answers
200 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 ...
J. Doe's user avatar
  • 93
6 votes
1 answer
323 views

Where can I find NTRU test vectors?

In some research work in 2001, it is stated that test vectors were not publicly available at the time. Then in this ESSS1v2 standard under IEEE1363 here , the appendix B mentions that the test vectors ...
Jaynjayn's user avatar
5 votes
4 answers
1k views

Does NTRU provide Perfect Forward Secrecy?

Does NTRU provide Perfect Forward Secrecy if the world would use it in an HTTPS connection?
somelooser28533's user avatar
5 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 ...
a.refaat's user avatar
5 votes
1 answer
210 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?
user47167's user avatar
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 ...
Vega4's user avatar
  • 234
4 votes
1 answer
727 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 ...
floor cat's user avatar
  • 214
4 votes
3 answers
331 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 ...
Jeffrey Quesnelle's user avatar
4 votes
2 answers
2k views

Inverses in Truncated Polynomial Rings

I've been trying a long time to understand a thing which is obviously extremely simple, but I just can't get it. Read this, please: The NTRUEncrypt PKCS uses the ring of truncated polynomials $R$ ...
Andrey Chernukha's user avatar
4 votes
1 answer
919 views

what are the NTRU keysize and application in industry?

I'm a student currently working on a research project on the NTRU cryptosystem, I've read some papers about this cryptosystem, and in those papers they are talking about keysize, is it the size of the ...
KamuiYato's user avatar
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 ...
wdc's user avatar
  • 143
4 votes
1 answer
262 views

NTRU less secure than previously thought?

A new paper (https://eprint.iacr.org/2015/552.pdf) says: This makes it possible to asymptotically and heuristically break the NTRU cryptosystem in subexponential time (without contradicting its ...
devin.omalley's user avatar
4 votes
1 answer
373 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 ...
evernal's user avatar
  • 237
4 votes
1 answer
503 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. ...
evernal's user avatar
  • 237
4 votes
0 answers
280 views

How can I implement decryption for NTRU homomorphic encryption scheme?

I have come across this paper On-the-fly multiparty computation via on-the-cloud Multikey from Fully Homomorphic Encryption by Lopez-Alt et al., where authors describe a NTRU-based homomorphic ...
guglielmo london's user avatar
4 votes
0 answers
124 views

How about a homomorphic integer sorting in a MPC context?

I want to implement the ATV-FHE scheme as described by Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan: On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption (...
guglielmo london's user avatar
3 votes
1 answer
906 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?
Z0OM's user avatar
  • 155
3 votes
2 answers
446 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 ...
cw_jackson's user avatar
3 votes
1 answer
337 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 ...
Leafar's user avatar
  • 325
3 votes
1 answer
283 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. ...
max's user avatar
  • 219
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 ...
Aran Smeallie's user avatar
3 votes
1 answer
645 views

NTRU and one failed example

In NTRU crypto system I have used these polynomials and parameters: $N = 17, p = 7, q = 64$ and $f$ as private key is: $$f = -1 + x + x^2 - x^4 + x^6 + x^9 - x^{10}$$ So the inverse of $f$ in ring $\...
Lisbeth's user avatar
  • 497
3 votes
1 answer
734 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 ...
Hani's user avatar
  • 31
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 ...
Dimitri Koshelev's user avatar
3 votes
1 answer
933 views

Regarding NTRU homomorphic properties

NTRU has some homomorphic properties modulo q, supporting both addition and multiplication. Due to its nature, it cannot support many of them. My main focus currently is in the addition, so the ...
absinthe_minded's user avatar
3 votes
0 answers
56 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 (...
max's user avatar
  • 219
3 votes
0 answers
435 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 ...
morthy's user avatar
  • 31
3 votes
0 answers
163 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 ...
a196884's user avatar
  • 381
3 votes
0 answers
380 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)...
OneUser's user avatar
  • 123
3 votes
0 answers
245 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 (...
Leafar's user avatar
  • 325
3 votes
0 answers
86 views

On a proposition in NTRU original paper: $\gamma_1 |f|_2 |g|_2 \leq |f \circledast g|_\infty \leq \gamma_2 |f|_2 |g|_2$

In the original paper of NTRU cryptosystem, we have the following proposition (that is said to be suggested by Don Coppersmith): For any $\epsilon > 0$, there are constants $\gamma_1,\gamma_2 &...
Leafar's user avatar
  • 325
3 votes
0 answers
123 views

How to test a FHE implementation?

I want to implement a FHE scheme based on NTRU, namely the scheme described here https://eprint.iacr.org/2014/039.pdf . How to test the security of my implementation ? Do I have to implement the ...
Radu Mardari's user avatar
2 votes
2 answers
3k views

How to make a message into a polynomial on NTRU encryption?

How to make a message into a polynomial on NTRU encryption? for example how we can conver 'hello world' to polynomial... i have read the converting operation on IEEE Std 1363.1- 2008, but i can't ...
Sunia Raharja's user avatar
2 votes
1 answer
174 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 ...
Dimitri Koshelev's user avatar
2 votes
1 answer
129 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 ...
max's user avatar
  • 219
2 votes
1 answer
95 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. ...
a196884's user avatar
  • 381
2 votes
1 answer
245 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$ (...
TomBombadil's user avatar
2 votes
1 answer
818 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 ...
Mike Ounsworth's user avatar
2 votes
1 answer
479 views

What is the most common encoding of messages to polynomials?

How polynomial based encryption schemes such as NTRU encode messages in to polynomials? Is there a generic conversion?
curious's user avatar
  • 6,160
2 votes
2 answers
715 views

NTRU key generation

I've been experimenting with an NTRU open-source C implementation here I've noticed something (potentionally) strange with a certain set of params: NTRU_EES1087EP2 (defined here). When generating ...
hunter's user avatar
  • 3,955