zbMATH — the first resource for mathematics

Lattice-based group signatures with logarithmic signature size. (English) Zbl 1314.94104
Sako, Kazue (ed.) et al., Advances in cryptology – ASIACRYPT 2013. 19th international conference on the theory and application of cryptology and information security, Bengaluru, India, December 1–5, 2013. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-42044-3/pbk). Lecture Notes in Computer Science 8270, 41-61 (2013).
Summary: Group signatures are cryptographic primitives where users can anonymously sign messages in the name of a population they belong to. S. D. Gordon et al. [Asiacrypt 2010, Lect. Notes Comput. Sci. 6477, 395–412 (2010; Zbl 1253.94071)] 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 J. Camenisch et al. [SCN 2012, Lect. Notes Comput. Sci. 7485, 57–75 (2012; Zbl 1310.94177)] suffers from the same overhead. In this paper, we 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). Our basic construction only satisfies a relaxed definition of anonymity (just like the Gordon et al. system) but readily extends into a fully anonymous group signature (i.e., that resists adversaries equipped with a signature opening oracle). We prove the security of our schemes in the random oracle model under the SIS and LWE assumptions.
For the entire collection see [Zbl 1275.94007].

94A60 Cryptography
Full Text: DOI