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

摘要： 分析以往基于格的群签名方案，虽能有效抵抗量子攻击，但都存在计算复杂度高、通信代价大和系统公钥尺寸过大的弱点，而NRTU格是一类基于多项式环的特殊格，因只涉及多项式环上的乘法和小整数求模运算，与一般格相比，NTRU格密码体制所需公私钥长度更短，运算速度更快。方案中使用NTRU格上高效的参数生成算法，构建了一个新的基于NTRU格的群签名方案，缩短了系统公钥长度，且系统公钥、追踪密钥和签名密钥之间可并行计算，使得计算效率更高，降低了通信代价。方案安全性归约至判定性LWE问题和近似CVP问题的难解性，并给出方案详细的效率分析。

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