Group Signatures and More from Isogenies and Lattices: Generic, Simple, and Efficient

We construct an efficient dynamic group signature (or more generally an accountable ring signature) from isogeny and lattice assumptions. Our group signature is based on a simple generic construction that can be instantiated by cryptographically hard group actions such as the CSIDH group action or an MLWE-based group action. The signature is of size O(log N ), where N is the number of users in the group. Our idea builds on the recent efficient OR-proof by Beullens, Katsumata, and Pintore (Asiacrypt'20), where we efficiently add a proof of valid ciphertext to their OR-proof and further show that the resulting non-interactive zero-knowledge proof system is online extractable.

Our group signatures satisfy more ideal security properties compared to previously known constructions, while simultaneously having an attractive signature size. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known post-quantum group signatures (e.g., 6.6 KB for 64 members). In comparison, our lattice-based construction has a larger signature size (e.g., either 126 KB or 89 KB for 64 members depending on the satisfied security property). However, since the O(•)-notation hides a very small constant factor, it remains small even for very large group sizes, say 2 20 .

• 128 bits of classical security and 60 bits of quantum security [Pei20].

malicious group manager can frame any honest members in the group by simply replacing the output of the opening algorithm. In contrast, our scheme remains secure even against malicious group managers since the validity of the output of the opening algorithm is verifiable. That is, even the group manager is held accountable in our group signature.

Not only our group signatures satisfy more ideal security properties compared to previous constructions, Tab. 1 shows that our signature size remains competitive. Our isogeny-based group signature based on CSIDH provides the smallest signature size among all post-quantum group signatures, which is 0.6 log 2 (N )+3 KB. In contrast, our lattice signature is larger; the scheme in the second (resp. third) row has signature size 0.5 log 2 (N ) + 123.5 KB (resp. 0.5 log 2 (N ) + 85.9 KB). It is smaller compared to [KKW18], while larger compared to [ESZ22]. Compared to the two constructions, our signature size grows much slower with the group size N (see also Footnote 1) and also satisfies stronger security. We thus leave it as an interesting open problem to lower the constants in our construction.