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

I'm currently prototyping something with the NTRU encryption scheme but I wish to use it in "reverse" -- distribute private keys so anyone can decrypt, but keep the public keys secret and thus only allow certain entities to create new messages. Is NTRU still secure under such a scheme? It seems from the literature that chosen-ciphertext attacks using decryption oracles (which essentially every entity would have) have had some success in breaking traditional NTRU. In general, does knowledge of the private key give us any information about the public key?

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 immediately compute $f^{-1}$; while they won't be able to recover the value $g$ (that's not actually referenced within the private key), what the attacker could do is just pick a legal $g$, and then use that to encrypt any message he wants (as no one else with the decryption key will be able to determine that's not the current $g$ value. It won't be the same key as the legitimate encryptor; however it will be accepted by anyone with the decryption key. Alternatively, he can just get any known text signed by the correct encryption key; that'll give him enough information to recover the correct $g$.

It sounds like what you want is a signature method; that is, a way where someone with the private key can 'sign' a message, and anyone with the public key can verify that signature (but cannot generate their own signatures). There are lots of signature methods known; some proposed methods are based on NTRU, but the unbroken ones are fairly new; I'd personally wait for cryptanalytic results against them, but if you have your heart set on an NTRU-based method, you can look at this paper. That would certainly be more secure than what you're doing now.

• Ah, darn. A digital signature system would suffice, but I was hoping not to have to do a symmetric key exchange -- if this worked the entire system would be stateless, and since it's all happening across microcontroller nodes the speed of NTRU was enticing. Thanks! Commented Sep 25, 2015 at 20:59
• @JeffreyQuesnelle: why would a digital signature system require a symmetric key exchange? Commented Sep 25, 2015 at 21:01
• Not all nodes would be given the private key (to decrypt), so I'd like the message itself to be encrypted as well. The idea is that some nodes can send a certain class of messages (they have the public key), a larger set of nodes can receive the message (so they have the private key, but can't generate messages of this class), and some nodes don't need to know about the message at all, so they get neither. If I use a regular DSA I still need to encrypt the messages to block out this third class -- I suppose I could use a hard-coded symmetric key based on the class... hmmm... :) Commented Sep 25, 2015 at 21:08

There's a signature scheme in the NIST Post-Quantum Cryptography Standardization project that's based on NTRU.

It's called Falcon, and it has more similarity to the original NTRUSign than the other 3rd-round signature scheme, which is Dilithium.

• Falcon is a very sophisticated scheme, and a correct implementation of it is very delicate;

• Dilithium has made many design decisions to make correct implementation easy, but the ciphergrams are not as compact as Falcon.

The status quo (as of Nov 2021) is that, the NIST will select one of Falcon and Dilithium at the end of 3rd round, but some people (e.g. Vadim Lyubashevsky, me) are hoping they both get selected even if one of them is primary and the other is a back up option.

As both of them have desirable properties that the other lack, and have somewhat different use cases in real-world applications. NIST had decided to select both lattice-based signatures for standardization.

The private key includes the public key with it on the top.