Hot answers tagged

8 votes

Which attacks are possible against raw/textbook NTRU encryption?

Without a well-designed padding system it may be possible to craft a ciphertext that the decryptor may or may not be able to decrypt properly. Whether the decryptor is able to do so will depend on the ...
user avatar
  • 133k
8 votes
Accepted

NTRU Backdoor and NewHope TLS Protocol

My name is Zhenfei Zhang. I work for Security Innovation Inc., which acquired NTRU Inc. in 2010. The R-LWE based key exchange [1] uses a public matrix $a$ which may be manipulated. For instance, if $a$...
user avatar
7 votes

Which attacks are possible against raw/textbook NTRU encryption?

I am a cryptographic researcher at Security Innovation, which acquired NTRU. Apart from the aforementioned attack, there are two significant attacks, namely a chosen plaintext attack (CPA) and a ...
user avatar
7 votes
Accepted

Is reverse NTRU still secure? (Looking for a signature scheme)

No, this system is not secure. Knowledge of the private key immediately gives enough of the public key that we can immediately encrypt an arbitrary message. The NTRU decryption key includes a ...
user avatar
  • 133k
7 votes
Accepted

Multiple NTRU public keys for the same private key?

According to current knowledge, handing out multiple public keys (with independent numerators) for the same private key $f$ is not insecure, as long as the parameters are instantiated appropriately. ...
user avatar
7 votes
Accepted

Secure, patent-free alternative to NTRU

I work for Security Innovation, which owns the NTRU patents. All NTRU-related patents are freely usable under GPL 2.0 and 3.0 -- in other words, they should fit in with your license requirement as ...
user avatar
7 votes

Does NTRU provide Perfect Forward Secrecy?

Properly speaking, forward secrecy is a property of a protocol. The protocol is forward secret if compromise of the long term keys does not allow an attacker to decipher any past communications. (...
user avatar
  • 31.3k
7 votes
Accepted

Why does NTRUEncrypt lack a formal security proof?

NTRU, as it was originally introduced, is based on what people now call the "NTRU assumption", which really just assumes that it is difficult to break NTRU. Annoyingly circular, but that's how it is. ...
user avatar
7 votes
Accepted

NTRU key size (confused)

I've thourgh that 439 would represent the key size in bits. No, NTRU doesn't measure things like that. Instead, it's the number of elements in a ring. In addition, with the current parameter sets, ...
user avatar
  • 133k
6 votes
Accepted

Explain: An NTRU key for a lattice of dimension $d$ has size only $O(d\log{d})$

An NTRU public key is a polynomial of degree $d-1$ whose coefficients are elements in $\mathbb{Z}_q$. So the number of bits you need to represent it is $d\log{q}$. If q is of the same order as d, ...
user avatar
  • 1,126
5 votes
Accepted

what are the NTRU keysize and application in industry?

Usually, in public-key cryptography, the "key size" is implicitly referred to the size of the public key. In the case of NTRU, both public and private keys are conveyed by the same thing: polynomials ...
user avatar
  • 4,832
5 votes

Lightweight Asymmetric encryption algorithm

When an embedded device needs asymmetric crypto to encrypt, (e.g. measurements it makes) or check authenticity (e.g. of commands or firmware updates it receives), there is no need for a private key or ...
user avatar
  • 125k
5 votes

NTRU key size (confused)

Poncho's explanation is correct: the size is $N \log_2(q)$ rather than just $N$. A better open-source implementation to use is here: https://github.com/NTRUOpenSourceProject/ntru-crypto -- this is ...
user avatar
5 votes
Accepted

How to decide if an element is a public key in NTRU encryption scheme?

You can't under a standard assumption known as the "Decisional NTRU Assumption". This is essentially the statement that NTRU public keys are pseudorandom. The following is definition 4.4.4 ...
user avatar
  • 8,677
4 votes

What is the most efficient attack on NTRU?

I am a cryptographic researcher at Security Innovation, which acquired NTRU Cryptosystems. Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the ...
user avatar
4 votes

Is the IEEE 1363.1 standard of NTRU post-quantum secure?

what are the major differences between the IEEE 1363.1 NTRU standard vs. the NTRUEncrypt NIST PQ submission The only differences would be the parameters that are standardized. This answer gives one ...
user avatar
  • 13.5k
4 votes
Accepted

Is the combination of X25519 ECDH and NTRU in OpenSSH 9.X secure against quantum attacks?

Can the combination of X25519 ECDH and NTRU in OpenSSH 9.X defend me against quantum attacks? Actually, that version of OpenSSH uses NTRU Prime, rather than NTRU. However, that does not change the ...
user avatar
  • 133k
3 votes
Accepted

In NTRU digital envelope, do everyone know the hash function $H$ used?

Yes, these are public parameters of the system. Note that NTRU is not implemented exactly this way any more. The most up-to-date current spec is EESS#1, which can be obtained from https://github.com/...
user avatar
3 votes
Accepted

What is the most common encoding of messages to polynomials?

In NTRUEncrypt, a raw message m of octet string of length l octets is encoded through the following steps: Padded it with a random salt of b byte and a few extra information to form the actual octet ...
user avatar
3 votes
Accepted

NTRU less secure than previously thought?

No, this result (as it stands) is of no practical use against NTRU as typically used. To quote the paper: Note that there is a large value hidden in the o(1) term, so that our algorithm does not ...
user avatar
  • 133k
3 votes

NTRU and one failed example

I've searched about this problem these two days, considering the paper cygnusv mentioned, and finally after reading the problem related to the pqc implementation, I guess that's the condition which is ...
user avatar
  • 457
3 votes

Layered encryption in mixnets with post-quantum cryptography

Might I suggest using traditional hybrid cryptography to cut down on the ciphertext growth size? This is the straight-forward approach where you don't directly encrypt the message with the public key;...
user avatar
  • 133k
3 votes
Accepted

NTRU homomorphic rerandomization

The decryption error occurs for the following reason. In a classical NTRU decryption you compute $c = e * f \pmod q \pmod p \\ \ \ = p r*h*f + m*f \pmod q \pmod p\\ \ \ = p r*g + m*f \pmod q \...
user avatar
3 votes

NTRUencrypt in NIST competition

This has been answered on the PQC forum. The question was asked by El Hassane Laaji: Hello NTRU team Can you say me, why you didn't keep the NTRUencrypt-1024 release, is it because of speed ...
user avatar
  • 13.5k
3 votes
Accepted

How to find the inverse of a polynomial in NTRU-PKCS

Disclaimer: I'm not familiar with NTRU, and not in my comfort zon. Hence the many edits. The problem asked can be summarized as: given $n$, $q$ coprime to prime $p$, and for $0\le i<n$ the ...
user avatar
  • 125k
3 votes
Accepted

Significance of parameter q in NTRU lattice attack

Basically, the norm of the secret key does not depend on $q$, while the norm of the second minimum of the lattice does, so, when you increase $q$, you increase the gap between the first and the second ...
user avatar
3 votes
Accepted

Is NTRU still hard if $G$ is set to 1?

If $G$ is set to $1$, then the adversary can easily decrypt the ciphertext because in this case $h = pf^{-1} \mod q, p$ is coprime with $q$, then inverting $p \mod q$ is possible and after that he ...
user avatar
3 votes
Accepted

Volume of an NTRU lattice

This is a standard computation in number theory. The idea behind it is that the matrix you have written down is a basis of the lattice as an $\mathcal{O}_K$-module, but to find the volume you first ...
user avatar
  • 8,677
2 votes

Convert message to polynomial NTRU

What you are looking for is explicitly specified in the IEEE Standard 1363.1 [1], which covers NTRU. In particular, encoding a bit string into a polynomial is done in the following manner: Once you ...
user avatar
  • 4,832
2 votes

Does NTRU provide Perfect Forward Secrecy?

Yes. I'm not sure why others are saying "no". Forward secrecy is usually done by simply creating ephemeral keys for each connection. Thus, you will simply require a different NTRU keypair for each ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible