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^{...


11

I'm Chief Scientist at Security Innovation, which acquired NTRU, and one of the co-authors of NTRUSign. The difference between NTRUEncrypt and NTRUSign is in how they use the lattice. All the NTRU algorithms are based on solving the Close Vector Problem in a particular form of lattice known as an "ideal lattice". For NTRUEncrypt, the encryption method is ...


10

That's not possible. It just so happens that this works with RSA because of the unique properties of RSA, but the majority of other asymmetric schemes just don't happen to work this way. For other schemes, the signature and encryption algorithms can be completely different and there may be no way to "encrypt" with the private key or "sign" with the public ...


10

I'm Chief Scientist at Security Innovation, which owns NTRU, and have contributed to the design of NTRUEncrypt and NTRUSign. The headline answer here is: NTRUEncrypt doesn't necessarily require decryption failures; it's a tradeoff you make, trading off key and ciphertext size against decryption failure probabilities. Parameter sets that don't give ...


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

The open source version of CyaSSL contains code that calls into the commercial NTRU library -- the library itself is missing of course. You might be able to make CyaSSL work with the open source NTRU implementation at https://github.com/tbuktu/libntru ; it's alpha level software though.


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

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 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 ...


6

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 ...


6

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 ...


6

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 ...


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

According to Wikipedia: Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients {-1,0,1}. In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation. So, lets say you have a message encoded in base 2 as 101101, you'd set the ...


5

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 ...


5

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 ...


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 ...


4

$$(-10+22x+22x^3-22x^6) - 1 = -11+22x+22x^3-22x^6 \equiv 0 \mod 11.$$ When substracting a constant from a polynomial, you do not subtract it from every term, only from the constant term. If you need a refresher, see addition and subtraction of polynomials.


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 ...


4

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 ...


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

One reason why it won't work that I can think of is because NTRU encryption is probabilistic, so the encrypted message is not unique for a given plaintext. There is a signature scheme named NTRUSign which is described in Digital Signatures Using the NTRU Lattice. A Java implementation of NTRUSign exists at https://github.com/tbuktu/ntru. Edit: Yes, ...


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

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 ...


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