A New Constant-Size Group Signature Scheme From Lattices

Abstract

A lattice-based group signature scheme (LGSS) is an active cryptographic primitive, where each group member can sign messages anonymously in the name of the entire group and each valid signature should be traced to some group member on the lattice. In each LGSS, the size of the group signature usually depends on the number of group members and the security parameter. Thus, designing a constant-size LGSS is an interesting problem. At PKC 2018, Ling, Nguyen, Wang and Xu presented the first constant-size group signature scheme under lattice assumptions. Its design is based on a zero-knowledge argument of the knowledge of a valid message-signature pair for the Ducas-Micciancio signature scheme, which follows the sign-then-encrypt-then-prove protocol. In contrast to this work, we construct a new constant-size LGSS. The scheme adopts the sign-hybrid-encrypt approach and makes use of the Lyubashevsky signature scheme. Our work is efficient in the signing algorithm, more precise on the open algorithm and shorter in public key, secret key and signature size than previous studies. Furthermore, we prove that the scheme has full anonymity and full traceability under the Ring Learning With Errors and Ring Short Integer Solution assumptions in the random oracle model.

Keywords

• Group signatures
• lattices
• Lyubashevsky signature scheme
• ring learning with errors
• ring short integer solution