# Tag Info

14

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

6

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

6

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

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.

5

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

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

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

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.

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.

2

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

2

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

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

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

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

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, ... 1 At least it checks out: $$(3 + 2X^2 - 3X^4 + X^6)(-2 + 4X + 2X^2 + 4X^3 - 4X^4 + 2X^5 - 2X^6) = -6 + X + 6X^2 + X^3 - X^4 + 6X^5 - 6X^6 - 4X^2 + 8X^3 + 4X^4 + 8X^5 - 8X^6 + 4 - 4X + 6X^4 - X^5 - 6X^6 - 1 + X - 6X^2 + 6X^3 - 2X^6 + 4 + 2X + 4X^2 - 4X^3 + 2X^4 - 2X^5 = 1$$ multiplying out all the terms, using$X^7 = 1, X^8 = X, X^9 = X^2$etc. and the fact ... 1 The secret key blob consist of 1718 bytes where the first 1500 indicates the corresponding public key. The last 200 ish bytes store the encoded secret key. The secret key is a trinary polynomial with coefficients -1,0,1. So we only need to store the position of non-zero coefficients. The last couple of hundreds of bytes in the encoded secret key suggest ... 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 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 ... 1 Currently, there is no formal proof of NTRU being based on a lattice problem, but you can find a description of NTRU in terms of lattices in Section 5.2 of [Ber09]. For lattice-based attacks for NTRU you can review [HPS98]. There is, however, a provably-secure variant of NTRU that is ultimately based on the hardness of the SVP problem [SS11]. References: ... 1 I work for Security Innovation, which owns the NTRU patents. We think the NTRU patents would cover this algorithm too -- the patents are written broadly enough to cover different types of keys. Note that although there are patents, we try to be reasonable about licensing terms. We have granted a free license for non-commercial use on many occasions and are ... 1 "how$-10+22X+22X^3-22X^6\$ may be 1 (modulo 11) if 22 = 0 mod 11?" Because when you reduce this mod 11 you get $$1 + 0 X + 0 X^3 + 0 X^6 = 1.$$ You seem to think that saying a polynomial is 1 mod 11 means that all its terms are 1 mod 11. What it actually means is that the constant term is 1 mod 11, and all the other terms are 0.

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