# Is reverse NTRU still secure?

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! – Jeffrey Quesnelle Sep 25 at 20:59
@JeffreyQuesnelle: why would a digital signature system require a symmetric key exchange? – poncho Sep 25 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... :) – Jeffrey Quesnelle Sep 25 at 21:08

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