How can one sign with NTRU? I am looking at implementing NTRU, but I noticed that while the encryption/decryption algorithm seems to be mature and well-documented, there is comparatively little information about how to sign using NTRU (and the proposed method apparently leaks information about the private key).

My question is, why can't I just sign in the same way one would sign an RSA message, i.e. the sender "decrypts" a known quantity using his private key, so that the recipient can "encrypt" the signature and easily verify it? (With any required padding of course.)

Are there any flaws in doing this?
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 basically:


Select a random point in the lattice
Add the message to that point as a small perturbation.


Decryption is then a matter of mapping back to the lattice point and recovering the message by subtracting the lattice point from the ciphertext. This only works because the message is chosen to have a particular form that means that the mapping back to the lattice point will always work. Well, almost always -- you may have read about decryption failures in NTRU. These occur when the mapping back to the lattice point doesn't work, but we can control their probability. But hold this thought.

For NTRUSign, the signing method is:


Hash the message to a random point in space
Find a lattice point close to that hash point and publish it as the signature


Verification is:


Hash the message to the same point in space
Verify that the signature point is a lattice point and is close to the message.


So this is the difference between decryption and signing. Decryption only works on messages with a very specific kind of structure, the structure that's produced by encryption. For decryption, those messages come out of encryption, so it's not a problem. But for signing, the "messages" (actually hashes) come out of a hash function, and creating a hash function that has the right structure but doesn't allow just anyone to sign is very hard. The obvious hash function to use is one that maps a message randomly to the integer vector space containing the lattice, and for this hash function decryption wouldn't work at all.