NTRUSign: Digital Signatures Using the NTRU Lattice

In this paper we introduce NTRUSign, an ew family of signature schemes based on solving the approximate closest vector problem (appr-CVP) in NTRU-type lattices. We explore the properties of general appr-CVP based signature schemes (e.g. GGH) and show that they are not immune to transcript attacks even in the random oracle model. We then introduce the idea of using carefully chosen perturbations to limit the information that is obtainable from an analysis of a large signature transcript. In the case of NTRUSign this can be achieved while maintaining attractive efficiency properties.