Group Signatures without NIZK: From Lattices in the Standard Model

In a group signature scheme, users can anonymously sign messages on behalf of the group

they belong to, yet it is possible to trace the signer when needed. Since the first proposal

of lattice-based group signatures in the random oracle model by Gordon, Katz, and Vaikuntanathan (ASIACRYPT 2010), the realization of them in the standard model from lattices

has attracted much research interest, however, it has remained unsolved. In this paper, we

make progress on this problem by giving the first such construction. Our schemes satisfy CCAselfless anonymity and full traceability, which are the standard security requirements for group

signatures proposed by Bellare, Micciancio, and Warinschi (EUROCRYPT 2003) with a slight

relaxation in the anonymity requirement suggested by Camenisch and Groth (SCN 2004). We

emphasize that even with this relaxed anonymity requirement, all previous group signature

constructions rely on random oracles or NIZKs, where currently NIZKs are not known to be

implied from lattice-based assumptions. We propose two constructions that provide tradeoffs

regarding the security assumption and efficiency:

• Our first construction is proven secure assuming the standard LWE and the SIS assumption. The sizes of the public parameters and the signatures grow linearly in the number

of users in the system.

• Our second construction is proven secure assuming the standard LWE and the subexponential hardness of the SIS problem. The sizes of the public parameters and the

signatures are independent of the number of users in the system.

Technically, we obtain the above schemes by combining a secret key encryption scheme with

additional properties and a special type of attribute-based signature (ABS) scheme, thus bypassing the utilization of NIZKs. More specifically, we introduce the notion of indexed ABS,

which is a relaxation of standard ABS. The above two schemes are obtained by instantiating

the indexed ABS with different constructions. One is a direct construction we propose and

the other is based on previous work.