NTRUSign With a New Perturbation

NTRUSign, a digital signature scheme, is suffering an effective attack. In this correspondence, we insert a new perturbation into NTRUSign primitive. With the new perturbation, each signature value is a linear combination of the private keys, and the combination coefficients have a hidden distribution. By a large number of signatures, the attacker obtains the value of some complicated function of the private keys. It appears as hard problem computing the private keys from this value. Our scheme is smaller in size, presents a higher efficiency, and provides a clearer security proof than NTRUSign with the old perturbation.