# Questions tagged [ntru]

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

72 questions
Filter by
Sorted by
Tagged with
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 ...
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.
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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)...
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 ...
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 ...
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 ...
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?
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 ...
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$ (...
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)...
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 ...
539 views

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?
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 (...
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 ...
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 ...
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)*[...
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 ...
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. ...
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 ...