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

learn more… | top users | synonyms

14
votes
3answers
856 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 ...
7
votes
1answer
245 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 ...
6
votes
2answers
117 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 ...
6
votes
1answer
284 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 ...
5
votes
3answers
914 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 ...
5
votes
2answers
1k 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 ...
5
votes
2answers
110 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 ...
5
votes
1answer
73 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 ...
4
votes
1answer
240 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 ...
4
votes
1answer
650 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 ...
4
votes
0answers
53 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 &...
4
votes
0answers
88 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 ...
4
votes
0answers
63 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 (...
3
votes
2answers
118 views

Is reverse NTRU still secure?

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 ...
3
votes
2answers
852 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$ ...
3
votes
1answer
131 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 ...
3
votes
1answer
72 views

NTRU test vectors

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 ...
3
votes
0answers
40 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 (...
3
votes
0answers
49 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 ...
2
votes
2answers
703 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 ...
2
votes
1answer
68 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?
2
votes
1answer
116 views

Reduced message expansion in NTRU

In the original NTRU proposal from 1998, it says on page 16: It may be worth mentioning, though, that there is a simple. masking technique that can be used to significantly reduce message ...
2
votes
2answers
99 views

Calculating Polynomial Inverse with extended euclid in java

I'm trying to understand the NTRU-PKCS and therefor I wanted to code a naive Version of it. Now my Problem: I tried to calculate the inverse of a Polynomial with an extended Version of euclids ...
2
votes
2answers
99 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
votes
1answer
129 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 $\...
2
votes
1answer
267 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 ...
2
votes
0answers
104 views

How can I make a message into a blocks for NTRU?

I have more bits than the degree of the NTRU polynomial. For example: $x^{11}-1$ message: Hello (I am using ascii, 8 bits for 1 symbol) got: ...
1
vote
2answers
320 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 ...
1
vote
2answers
186 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 ...
1
vote
1answer
14 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 ...
1
vote
1answer
162 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 ...
1
vote
1answer
154 views

NTRU Encryption

It's using Euclidian inverse. Can you show it step by step? $$N=7, q=11, a = 3+2X^2 -3X^4 +X^6$$ the inverse of $a \pmod {11}$ is $$A=-2+4X+2X^2 +4X^3 -4X^4 +2X^5 -2X^6$$ How do we compute $A$?
1
vote
1answer
226 views

Is the “secure-as-worst-case” version of NTRU patented?

Does the improved version of NTRU — which is described in "Making NTRU as Secure as Worst-Case Problems over Ideal Lattices" by Stehlé and Steinfeld — fall under the same patents as the original?
1
vote
0answers
33 views

How to generate public key for ATV-FHE scheme?

I want to implement the ATV-FHE scheme as it is described here https://eprint.iacr.org/2014/039.pdf. How to generate the public key? Should I compute it as indicated in section 2 : $h(i) = 2g(i)*...
1
vote
0answers
291 views

computing inverses in truncated polynomial rings manually for NTRU encryption [duplicate]

Can someone explain how to find inverses in truncated polynomial rings manually (i.e. on pen and paper)? As an example from the tutorial: Example. Take $N=7$, $q=11$, $a=3+2X^2-3X^4+X^6$. The ...
1
vote
1answer
259 views

NTRUEncrypt - Choose the initial random polynomial

I'm trying to implement NTRUEncrypt but encounter some problems. I've finished all the basic functions that are needed for the scheme base on this Document, but I can't find an algorithm to check the ...
0
votes
1answer
29 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 ...
0
votes
3answers
272 views

Does NTRU provide Perfect Forward Secrecy?

Does NTRU provide Perfect Forward Secrecy if the world would use it in an HTTPS connection?
0
votes
1answer
132 views

reduces the coefficients of a modulo 3 on NTRU

i'm still don't understand about 'reduces the coefficients of a modulo 3' on NTRU tutorial $a = f*e = 3 - 7X - 10X^2 - 11X^3 + 10X^4 + 7X^5 + 6X^6 + 7X^7 + 5X^8 - 3X^9 -7X^{10} \pmod{32}.$ Note ...
0
votes
1answer
45 views

how to define the Truncated Polynomial?

In NTRUEncryption, I seen the trucated polynimials, but I cannot understand the trunacated polynomial calculation. So, could tell me anyone How do we calculate the truncated polynomial?
0
votes
0answers
36 views

NTRUSign Hashing

I have some trouble understanding the inner workings of NTRUSign. So what I have understood so far is, that when Alice wants to sign a message she does the following steps Convert Alice's message ...
0
votes
0answers
30 views

How do I check if the secret key polynomial of the ATV-FHE (NTRU based) scheme is invertible?

I want to implement the ATV-FHE scheme as described here https://eprint.iacr.org/2014/039.pdf. To generate the secret key polynomial I compute f = 2*u + 1 , with scheme parameters chosen such that ...
0
votes
0answers
24 views

Which parameters of the ATV-FHE scheme should be kept private?

I try to implement the ATV-FHE scheme as it is described in section 2 of this paper. I also read this paper that says how parameters should be chosen. Are there some parameters that must be kept ...
0
votes
0answers
20 views

What is the bound for the probability distribution for ATV-FHE scheme?

I try to implement the ATV-FHE scheme as described in this paper https://eprint.iacr.org/2014/039.pdf. How do I choose the bound for the probability distribution chi? How do I choose standard ...
0
votes
0answers
17 views

How to choose moduli ladder for ATV-FHE scheme?

I try to implement the ATV-FHE scheme as mentioned in section 2 in this paper https://eprint.iacr.org/2014/039.pdf. In this paper, authors say this "For example, given a 256-bit prime q ..." in ...
0
votes
0answers
30 views

How to toggle a bit homomorphically ?

Suppose I want to use LTV scheme from this paper https://eprint.iacr.org/2013/094.pdf to compute homomorphically a function. But the multiplication operation is more expensive than the additive one. ...
-1
votes
1answer
125 views

Convert message to polynomial NTRU

How to make a message into a polynomial? I saw many answers to this question and yes, i know that here are some questions. But i did not get it. I think that i am making some mistakes. I took a word ...