NTRUSign involves mapping a message to a random point in 2N-dimensional space, where N is one of the NTRUSign parameters, and solving the close vector problem in a lattice closely related to the NTRUEncrypt lattice. This lattice has the property that a private 2N-dimensional basis for the lattice can be described with 2 vectors, each with N coefficients, and a public basis can be described with a single N-dimensional vector. This enables public keys to be represented in O(N) space, rather than O(N2) as is the case with other lattice-based signature schemes. Operations take O(N2) time, as opposed to O(N3) for elliptic curve cryptography and RSA private key operations. NTRUSign is therefore claimed to be faster than those algorithms at low security levels, and considerably faster at high security levels.
NTRUSign is not a zero-knowledge signature scheme and a transcript of signatures leaks information about the private key, as first observed by Gentry and Szydlo. Nguyen demonstrated in 2006 that for the original unperturbed NTRUSign parameter sets an attacker can recover the private key with as few as 400 signatures.
The current proposals use perturbations to increase the transcript length required to recover the private key: the effect of this is that the point representing the message is displaced by the signer by a small secret amount before the signature itself is calculated. The contribution of the perturbations to the transcript is designed to be difficult to distinguish from the contribution of the private key. NTRU claim that at least 230 signatures are needed, and probably considerably more, before a transcript of perturbed signatures enables any useful attack.