Hot answers tagged

17

The likelihood of a decryption failure can be made arbitrarily small. IEEE P1363.1 says in appendix A.4.10: For ternary polynomials with $d$ $+1$s and the same number of $-1$s, the chance of a decryption failure is given by [B30]: $$\operatorname{Prob}_{(q, d, N)}(\text{Decryption fails}) = P_{(d, N)} \left( \frac{q - 2}{6} \right)$$ where ...


11

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


8

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


7

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


7

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


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

Decryption in NTRU is probabilistic, however for correctly chosen parameters, the chance of a decryption failure is very small. It is not a worry in practice.


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


5

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


5

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


5

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


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

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.


4

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


4

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


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


3

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


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

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

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


2

Reducing mod 3 means indeed reducing each coefficient mod 3, and again we choose the representatives symmetrically around 0, so each coefficient becomes -1,0 or 1 (instead of, which is also possible, 0,1, and 2, or some other choice). $-7X$ becomes $-X$ because $-7 \equiv -1 \mod 3$. The starting constant 3, becomes 0, and disappears, $-10X^2$ becomes ...


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

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


2

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


2

NTRU private polynomial $f$, as described in Section 9.2.1 of IEEE Std. 1363.1, is computed as $f = 1 + p \cdot F \mod q$, where $F$ is a ternary polynomial of degree $N-1$ with a specific number of coefficients equal to -1, 1, and 0, determined by parameter $d_F$ (i.e., $d_F$ coefficients equal to 1, $d_F$ coefficients equal to -1, and the rest are 0's). ...


2

I've been looking for the test vectors also. https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/reference-code/Java/Encrypt/build.xml refers to ""com.securityinnovation.testvectors.NtruEncryptTestVectorGenerator" " I haven't looked any deeper than this, but it looks like they don't publish test vectors, but give you a means of generating them ...


1

Almost all lattice-based schemes that have somewhat practical performance use lattices from a subset of all lattices. Those lattices have additional structure and can be described using polynomials. The big advantage of doing this is that on the one hand the size of a description of the lattice is much smaller than for arbitrary lattices and on the other ...


1

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


1

I work for Security Innovation, which owns the NTRU algorithms. Glad to see this interest! You can look on this approach as two separate encryptions: one public-key encryption to transport $r_2$, and one symmetric encryption using $r_2$ as the key to encrypt $m$. This makes it look much more like standard practice in asymmetric crypto, where you typically ...


1

Since you referring to the LWE variant of Stehlé and Steinfeld, I will try to give you an answer to your question in that context. Note that these results are a mere extension of the correctness condition in Lemma 3.7 from the revised version of the paper [SS13]. As I said in the comments, at the end it all depends on the choice of parameters ($n, \alpha, ...



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