Hot answers tagged

12

I'll comment only the statement referring to an AES-256 replacement with 4096-bit key: According to our engineers, this will take 23840 times longer to crack than aes256 Bob writing that is not able to correctly transcribe even the numbers that engineer Alice allegedly spelled: most likely, $23840$ is intended to be $2^{3840}$, which is the ratio $2^{...


8

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 private key. The concern is that an attacker may be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and finally deduce the ...


8

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$ is an NTRU style public key, i.e., $a = g/f$ where $g$ and $f$ are short, then one can break the system by recovering $f$. In particular, the cited paper ...


7

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. There is some small loss in concrete security, but nothing like an efficient attack is known. The standard NTRU lattice for just one public key $h$ is \begin{...


7

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 chosen ciphertext attack (CCA), when a proper padding scheme is not used. Recall that in an IND-CPA game, the challenger is given two plaintexts, suppose they are ...


7

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 polynomial $f$; the encryption key is essentially $f^{-1}g$, where $g$ is a polynomial with coefficients in the set $(0, p, -p)$. Anyone with the private key can ...


7

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 given above. If you have specific license requirements beyond GPL please let me know and we'll accommodate them if we can. There's an open-source C and Java ...


7

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. (Occasionally a distinction is made between that and perfect forward secrecy, with the latter secure when the attacker also knows e.g. all other session keys.) You ...


7

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. Similar to how breaking RSA is not provably as hard as factoring (technically it is based on the "RSA assumption"), but people still think it is hard, NTRU ...


7

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, each ring element is a value between 0 and 2047 (11 bits), and the public key consists of one ring, and so it takes up $11 \times 439 = 4829$ bits, which ...


6

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, then this gives you $d\log{d}$. The private key, on the other hand, can be represented with $O(d)$ bits since the coefficients are all in the set $\{-1,0,1\}$.


5

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 defined over a specific polynomial ring. These polynomials can be represented as vectors in $\mathbb Z_q$ of size $N$. Therefore, raw public and private key ...


5

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 key generation in the device, and nothing beats RSA and Rabin on simplicity and speed (for RSA: with $e=3$, which is safe when used with proper padding); plus ...


5

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 the implementation endorsed by the inventors of NTRU and by Security Innovation, which owns the NTRU patents (and which I work for). It should be preferred to ...


5

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 of A Decade of Lattice Cryptography. NTRU Learning Problem: For an invertible $s\in R_q^*$, and distribution $\chi$ on $R$, define $N_{s, \chi}$ to be the ...


4

The claims made are pretty much all nonsense or do not represent an accurate understanding of the state of the art. I'm not going to go into a point-by-point response; suffice it to say that I would not trust any advice or representations they may make about what is or isn't secure. Their system might be fine, or it might not be, but their public ...


3

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 string M that is to be encrypted. This M byte string is then converted to a binary string Mbin using octect-string-to-binary-string-primitive (OS2BSP). In ...


3

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 yield practical attacks for recommended NTRU parameters. In addition, while it is subexponential, it's just barely so; they estimate the time as $2^{ (\ln 2/2+o(...


3

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 not formally mentioned in NTRU papers. And this condition $$q > p(6d + 1)$$ must be true in order for the probability of unrecoverable messages to be less ...


3

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 meet-in-the-middle one? The most efficient attack (the terminology "best known attack" is often used here) is the hybrid attack of lattice reduction and meet-in-...


3

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/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf.


3

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; instead, you pick a random symmetric (e.g. AES) key, encrypt the symmetric with the public key, and then AES encrypt the message with the symmetric key. That ...


3

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 \pmod p$ By construction $f = 1 \bmod p$. Therefore, if the all the coefficients of $(p r*g + m*f)$ are within the interval of $0$ and $q-1$, (or $-q/2$ and $q/2$, ...


3

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 parameter set, specifically EES1087EP2. Unfortunately, the IEEE Std 1363.1-2008 document itself is behind a paywall, so I am unable to view the other parameter ...


3

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 performance or security performance. Best regards. The reply came from John Schanck: Thanks for your question. To clarify for others, the "NTRUencrypt-1024" ...


3

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 minima of the lattice, which makes the problem easier. For instance, if the secret key is composed by two degree-$(N-1)$ polynomials $f$ and $g$ with ...


3

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 calculates $f \mod q$ from $h$, then he calculates $f^{-1} \mod p$ from $f$


3

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 find a $\mathbb{Z}$-basis for the lattice, and then do "standard" computations with this. If $B$ is a $\mathbb{Z}$-basis of $\mathcal{O}_K$, then one ...


2

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 have processed the input message, you divide it into blocks of 3 bits, and transform each block in a pair of coefficients of a ternary polynomial according to a ...


2

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 connection. Another, related, question is "how fast is NTRU keypair generation?" Since forward secrecy requires the frequent creation of ephemeral keys, this ...


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