Questions tagged [ntru]
NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.
107
questions
3
votes
2
answers
436
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 ...
- 45
-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
1
vote
1
answer
143
views
Is there is a way to calculate the public key from the private key in pqNTRUSign algorithm?
There is source code of this algorithm (https://github.com/NTRUOpenSourceProject/NTRUMLS). But this algorithm does not provide a function for generating a public key from a private key. Studying the ...
- 125
2
votes
1
answer
240
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$ (...
- 123
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
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
1
answer
803
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 ...
- 3,577
0
votes
1
answer
787
views
How to find the inverse of f(x) in NTRU key generation?
I work on a project that depends on the NTRU cryptosystem, but I don't know how to find the inverse of $f(x)$.
Please see the picture:
Please help me to understand this problem.
- 11
6
votes
2
answers
195
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 ...
- 93
-3
votes
1
answer
209
views
Uniform Distribution and discrete Gaussian distribution for NTRU
I want to implement the NTRU cryptosystem. What is the method and algorithm to choose vectors elements from a uniform distribution and discrete Gaussian distribution?
- 87
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 ...
- 234
1
vote
1
answer
187
views
Explain: An NTRU key for a lattice of dimension $d$ has size only $O(d\log{d})$
The associated NTRU lattice is of dimension $d=2N$.
The public and private key sizes are both of length $O(N)=O(d/2)=O(d)$.
So where does the $d\log(d)$ appear?
Thanks in advance.
- 325
4
votes
1
answer
721
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 ...
- 214
2
votes
1
answer
249
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 ...
- 325
0
votes
1
answer
123
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 ...
- 325
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
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 ...
- 61
2
votes
2
answers
1k
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 ...
- 41
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
2
votes
1
answer
474
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?
- 6,140
10
votes
2
answers
795
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 ...
- 4,942
0
votes
1
answer
1k
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?
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
7
votes
1
answer
739
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 ...
- 961
4
votes
2
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 ...
- 41
7
votes
2
answers
588
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 ...
- 135
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
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
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
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
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
4
votes
3
answers
330
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 ...
2
votes
2
answers
292
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,837
6
votes
1
answer
312
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 ...
- 31
4
votes
1
answer
260
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 ...
- 135
3
votes
1
answer
644
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 $\...
- 487
4
votes
1
answer
915
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 ...
- 51
3
votes
1
answer
915
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 ...
- 465
1
vote
1
answer
541
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$?
2
votes
2
answers
692
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 ...
- 3,945
2
votes
1
answer
243
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 expansion. ...
- 135
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 ...
- 4,942
0
votes
1
answer
564
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 ...
- 29
5
votes
4
answers
986
views
Does NTRU provide Perfect Forward Secrecy?
Does NTRU provide Perfect Forward Secrecy if the world would use it in an HTTPS connection?
- 197
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
3
votes
1
answer
726
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 ...
- 31
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 ...
- 171
1
vote
1
answer
332
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?
- 394
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 ...
