Questions tagged [ntru]
NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.
29
questions with no upvoted or accepted answers
4
votes
0
answers
277
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 ...
- 681
4
votes
0
answers
123
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 (...
- 681
3
votes
0
answers
49
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 (...
- 219
3
votes
0
answers
390
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 ...
- 31
3
votes
0
answers
156
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 ...
- 381
3
votes
0
answers
365
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)...
- 123
3
votes
0
answers
243
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 (...
- 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 &...
- 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 ...
- 223
2
votes
0
answers
43
views
worst case to average case reduction in non-cyclotomic Ring LWE
I understand that we need 2-to-power cyclotomic ring to show that the solving decision RLWE is as hard as solving search RLWE.
Is there any chance to prove it without 'cyclotomic' property?
For ...
- 33
2
votes
0
answers
62
views
What is the exact assumption behind OW-CPA of NTRU?
As shown in this paper the IND-CPA of NTRU is based on both the decision key cracking problem and the decision ciphertext cracking problem. However, I often see claims (such as in this paper) that the ...
- 258
2
votes
0
answers
129
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 ...
- 421
2
votes
0
answers
191
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 - ...
- 237
2
votes
0
answers
169
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 ...
- 509
2
votes
0
answers
135
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: ...
- 29
1
vote
0
answers
53
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? ...
- 11
1
vote
0
answers
24
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 ...
- 9,001
1
vote
0
answers
134
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 ...
maciek
1
vote
0
answers
34
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$, ...
- 111
1
vote
0
answers
403
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)...
- 509
1
vote
0
answers
52
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)*[...
- 223
0
votes
0
answers
43
views
is it safe to reuse the public key in NTRUEncrypt?
Looking at https://github.com/tbuktu/libntru/blob/master/src/ntru.h, there are some functions that deal with having multiple public keys with the same private key. I don't believe I need such ...
- 1
0
votes
0
answers
51
views
The special case of NTRUEncrypt when N = q
I've found this task in the "Introduction Mathematical Cryptography by Jeffrey Hoffstein":
The guidelines for choosing NTRUEncrypt public parameters (N, p, q, d) in-clude the assumption that ...
- 21
0
votes
0
answers
124
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 ...
- 237
0
votes
0
answers
62
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
0
answers
65
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 ...
- 223
0
votes
0
answers
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 ...
- 223
0
votes
0
answers
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.
...
- 223
-1
votes
1
answer
148
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?
- 29