# Questions tagged [ntru]

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

21 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
239 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 ...
110 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 (...
181 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 (...
83 views

14 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 ...
11 views

I'm looking for any source that explains the final implementation of NTRUEncrypt for the NIST's third round as simple as possible. I have been trying to understand it directly from the submitted code ...
72 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{...
42 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.
62 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 ...
30 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 ...
### 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?