Questions tagged [ntru]

NTRU is an encryption algorithm which is based on the shortest vector problem in a lattice.

Filter by
Sorted by
Tagged with
1
vote
0answers
19 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
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{...
1
vote
0answers
62 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
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
1answer
43 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
328 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
179 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
37 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
49 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
143 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
150 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 ...
1
vote
1answer
134 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
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
1answer
116 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
129 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
270 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
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?
1
vote
1answer
124 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
173 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
271 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
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
1answer
557 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
483 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
2answers
164 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
152 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
790 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
171 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
616 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
196 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
97 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
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 (...
5
votes
1answer
821 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
411 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
475 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
715 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
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 ...
7
votes
1answer
653 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 ...
3
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
359 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
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 (...
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 ...
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
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 ...
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
217 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
226 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 ...