Questions tagged [ntru]
NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.
87
questions
3
votes
1answer
302 views
How to decide if an element is a public key in NTRU encryption scheme?
First, I'm using the settings of https://en.wikipedia.org/wiki/NTRUEncrypt, with $L_f$ set of polynomials with $d_f+1$ coefficients equal to 1, $d_f$ equal to $-1$ and the remaining $N-2d_f-1$ equal ...
2
votes
0answers
42 views
Basic explanation of Falcon and Dilithium
I've been trying to search for toy examples of the round 3 digital signatures Rainbow, Falcon and Dilithium. Not a lot of actual implementation examples are out there. What I'm searching for are ...
1
vote
0answers
19 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 ...
1
vote
0answers
69 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 ...
2
votes
1answer
63 views
Volume of an NTRU lattice
Let $K$ be a number field of degree $n$ and $\Lambda^q_h=\{(f,g)\in\mathcal{O}_K\text{ : }fh-g = 0\bmod q\mathcal{O}_K\}$, where $h$ is an NTRU public key. Then $\{(1,h),(0,q)\}$ generates a lattice. ...
2
votes
0answers
82 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 ...
4
votes
1answer
75 views
Is NTRU still hard if $G$ is set to 1?
I'm looking at the description of NTRUEncrypt given on page 21 of http://archive.dimacs.rutgers.edu/Workshops/Post-Quantum/Slides/Silverman.pdf and using its notation. So in NTRU there are always two ...
3
votes
0answers
88 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 ...
0
votes
0answers
59 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 ...
3
votes
1answer
164 views
What is the NTRU parameter equivalent to security level 112, 128 and 192?
I came across this paper which mentions this table, which states that NTRU 347 is equivalent to 112 bit security level
However, in this paper, Choosing parameters for NTRU mentions that NTRU-401 is ...
1
vote
1answer
138 views
NTRU Euclidean algorithm the inverse of f modulo p
I am very new to the world of cryptography and have just began my research in the post quantum cryptography sector. I have been reading and trying to understand NTRU key generation and am struggling ...
3
votes
1answer
104 views
What is the largest parameter broken for NTRU?
The original secure parameters for NTRU shown below are from the original HPS98 paper. This is vastly different from the current secure suggested parameters in the NIST PQC round 3 submission.
...
2
votes
1answer
185 views
How to encode and decode message into polynomial form on NTRU
This question is based on a previously asked question. How to make a message into a polynomial on NTRU encryption?
I am tasked to implement NTRU with toy parameters such as $N=7$ or $N=11$ and I have ...
1
vote
1answer
84 views
Algebraic Variants of NTRU
There are a large number of algebraic NTRU variants: for example, in some (such as ETRU), the underlying ring has been changed to the ring of integers of a certain number field; there is GR-NTRU, ...
3
votes
1answer
124 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 ...
2
votes
0answers
52 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 - ...
1
vote
0answers
26 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$, ...
0
votes
1answer
108 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
50 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
50 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
680 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
247 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.
1
vote
1answer
49 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
1answer
89 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
177 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
191 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
156 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
205 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
125 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
164 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
326 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
92 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
129 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
194 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
301 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
138 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
674 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
572 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.
6
votes
2answers
176 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
175 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?
4
votes
2answers
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 ...
1
vote
1answer
180 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
648 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
221 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
108 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
204 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
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 ...
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
85 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
437 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?
