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
4
votes
0answers
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 ...
4
votes
0answers
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 (...
3
votes
0answers
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 (...
3
votes
0answers
83 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 &...
3
votes
0answers
113 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
0answers
17 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 - ...
2
votes
0answers
142 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)...
2
votes
0answers
130 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 ...
2
votes
0answers
133 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
0answers
21 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$, ...
1
vote
0answers
63 views

Code implementation of NTRU lattice attack

As mentioned here, BKZ is one way to break the NTRU lattice What is the most efficient attack on NTRU? I was wondering if there are any source codes which actually implemented this on the weaker NTRU ...
1
vote
0answers
272 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)...
1
vote
0answers
50 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)*[...
0
votes
0answers
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 ...
0
votes
0answers
11 views

Sources about NTRUEncrypt implementations

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 ...
0
votes
1answer
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{...
0
votes
0answers
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.
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
53 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
83 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?