关键词: 格密码, NTRU格, 群签名, 容错学习问题, 近似最近向量问题

Abstract: The previous lattice-based group signature schemes are analyzed. Though those schemes can effectively resist the quantum attack, they have several weaknesses such as the computation complexity and communication cost are too high, and the group public key size is too large. NTRU lattice is a particular kind of lattice based on polynomial ring, and the schemes based on NTRU lattice require shorter public and private keys and compute faster than the general lattice because they only involve multiplication and small integer modulus calculation in polynomial ring. The proposed scheme gives the first construction of a group signature scheme based on NTRU lattice, using an algorithm which can efficiently generate parameters on NTRU lattice. The scheme shortens the length of group public key, group public key, tracking key and signing key can be calculated in parallel, which make the computation faster and reduce the communication cost. The security of the proposed scheme strictly reduces to the hardness of decisional learning with errors and approximate closest vector problem, and the performance analysis is given in detail.

Key words: lattice-based cryptography, NTRU lattice, group signature, learning with errors problem, approximate closest vector problem