How can one sign with NTRU?

Question

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?

Answer 1

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

Answer 2

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.

Answer 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, NTRUSign leaks information about the private key which is why an "unperturbed" NTRUSign key becomes insecure after ~400 signatures. With one perturbation, a private key lasts millions to billions of signatures.

NTRUSign is currently broken even with pertubation. See: Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermeasures. Léo Ducas, Phong Q. Nguyen.