Lattice-Based Group Signatures with Logarithmic Signature Size
Group signatures are cryptographic primitives where users can anonymously sign messages in the name of a population they belong to. Gordon et al. (Asiacrypt 2010) suggested the first realization of group signatures based on lattice assumptions in the random oracle model. A significant drawback of their scheme is its linear signature size in the cardinality N of the group. A recent extension proposed by Camenisch et al. (SCN 2012) suffers from the same overhead. In this paper, the authors describe the first lattice-based group signature schemes where the signature and public key sizes are essentially logarithmic in N (for any fixed security level).