Constant-size Lattice-Based Group Signature with Forward Security in the Standard Model

Sébastien Canard, Adela Georgescu, Guillaume Kaim, Adeline Roux-Langlois, Jacques Traoré

Abstract

One important property of group signatures is forward-security which prevents an attacker, who is in possession of a group signing key, to make use of it in order to forge signatures produced in the past. In the case of exposure of one group member's signing key, group signatures lacking forward-security need to invalidate all group public and secret keys by re-initializing the whole system but also invalidate all previous issued group signatures. Most of the existing forward-secure group signatures (FS-GS) are built from number-theoretic security assumptions which are vulnerable against quantum computers. The only forward-secure group signature post-quantum secure is built from lattices [LNWX19] in the random oracle model following the classical framework of encrypt-then-prove using non-interactive zero-knowledge (NIZK) proofs. In this work, we achieve the first FS-GS from lattices in the standard model. Our starting point is the group signature of [KY19] which replaces NIZK with attribute-based signatures (ABS) removing the need of random oracles. We modify the underlying ABS of [Tsa17], equip it with forward-security property and prove that by plugging it back in the group signature framework of [KY19], we achieve a FS-GS in the standard model with public key and signature size constant in the number of users. The cost of achieving constant sizes comes from the need of relying on complexity leveraging which further implies relying on the subexponential hardness of the Short Integers Solution (SIS) assumption.