Questions tagged [ntru]
NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.
72
questions
1
vote
0answers
47 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 ...
0
votes
0answers
40 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
1answer
39 views
Canonical inclusion map in subfield attack on overstretched NTRU
I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf authors used "canonical inclusion map" to lift vector to full lattice. What does ...
2
votes
1answer
250 views
How to find the inverse of a polynomial in NTRU-PKCS
I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key ...
1
vote
1answer
159 views
Fully Homomorphic Encryption - state of the art
What are the latest advances in fully homomorphic encryption? First of all, I am interested in cryptosystems based on LWE / RLWE and NTRU problems.
0
votes
0answers
23 views
NTRU value 'r' coefficients and degree
On Wikipedia, it says that
Alice chooses randomly a polynomial r with small coefficients (not
restricted to the set ...
1
vote
1answer
33 views
NTRUEncrypt polynomial $r$ Uniqueness
During the encryption process in NTRU, a random polynomial $r$ of small coefficients is generated to bind to the message to obscure it, and this polynomial must be kept secret. Does this polynomial ...
0
votes
0answers
42 views
NTRU Bilateral Key Exchange
With the NTRU scheme, is the key exchange only done by encrypting a symmetric key with the recipients public key (+ authentication) or can something similar to DH/ECDH be done, where public ...
0
votes
1answer
46 views
Does AES encryption of a NTRU pivate key reduce security?
The NTRU crypto system requires quite long keys. For example with parameters N=439 and q=2048 the security is 128 bits and the key_size is 4829 bits.
When the private key is encrypted with AES-256 ...
5
votes
1answer
136 views
NTRUencrypt in NIST competition
Why did the NTRUencrypt team not maintain the NTRU1024 release in the NIST second-round competition?
Is this because of the speed performance or security performance or other things?
1
vote
1answer
133 views
NTRUSign (considered broken) as a one or few time PQ signature scheme
As many know, original NTRUSign is considered broken as signatures leak information about the private key.
It takes a number of signatures to accomplish a break though, with the original break paper ...
0
votes
1answer
125 views
NTRU: Possible misunderstending of division and euclidean algorithm for polynomials
Please consider this answer before reading
I am trying to find GCD of two polynomials, but I have some troubles understanding division and euclidean algorithms:
1) In description of division ...
2
votes
0answers
125 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
1answer
114 views
Encrypt your ECDSA signature with NTRU to make them quantum secure, does that work?
I have a general question about quantum security. ECDSA is suppose to be broken by quantum computers. Whilst something like NTRU is suppose to be secure.
My question is: if we sign with ECDSA and ...
2
votes
1answer
120 views
Original NTRU : How to calculate the size of private key?
In the original NTRU paper：NTRU: A Ring-Based Public Key Cryptosystem,1996, the author proposes 3 choices of implementation parameters: moderate, high and highest. Let's take moderate security level ...
3
votes
2answers
258 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 ...
-1
votes
1answer
82 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?
1
vote
1answer
122 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 ...
2
votes
1answer
165 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$ (...
1
vote
0answers
263 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)...
2
votes
0answers
123 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
1answer
539 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 ...
0
votes
1answer
448 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.
5
votes
1answer
155 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 ...
-3
votes
1answer
148 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?
2
votes
2answers
724 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 ...
1
vote
1answer
168 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.
4
votes
1answer
607 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 ...
2
votes
1answer
193 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 ...
0
votes
1answer
96 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 ...
3
votes
0answers
176 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 (...
5
votes
1answer
779 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 ...
1
vote
2answers
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 ...
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 &...
2
votes
1answer
400 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?
8
votes
2answers
440 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 ...
0
votes
1answer
673 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
0answers
233 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 ...
7
votes
1answer
646 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 ...
2
votes
2answers
3k 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 ...
6
votes
2answers
347 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 ...
4
votes
0answers
109 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 (...
0
votes
0answers
61 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 ...
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)*[...
3
votes
0answers
111 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 ...
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.
...
4
votes
2answers
213 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 ...
2
votes
2answers
221 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 ...
6
votes
1answer
233 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 ...
