Attribute-based signatures on lattices

Xianping Mao, Kefei Chen, Yu Long +1 more

Maharage Nisansala Sevwandi Perera, Toru Nakamura, Chen-Mou Cheng +1 more

Jan L. Camenisch, Gregory Neven, Markus Rückert

Anonymous authentication schemes such as group signatures and anonymous credentials are important privacy-protecting tools in electronic communications. The only currently known scheme based on assumptions that resist quantum attacks is the group signature scheme by Gordon et al. (ASIACRYPT 2010). We present a generalization of group signatures called anonymous attribute tokens where users are issued attribute-containing credentials that they can use to anonymously sign messages and generate tokens revealing only a subset of their attributes. We present two lattice-based constructions of this new primitive, one with and one without opening capabilities for the group manager. The latter construction directly yields as a special case the first lattice-based group signature scheme offering full anonymity (in the random-oracle model), as opposed to the practically less relevant notion of chosen-plaintext anonymity offered by the scheme of Gordon et al. We also extend our scheme to protect users from framing attacks by the group manager, where the latter creates tokens or signatures in the name of honest users. Our constructions involve new lattice-based tools for aggregating signatures and verifiable CCA2-secure encryption.

Miaomiao Tian, Liusheng Huang

Jinhong Chen, Xueguang Zhou, Wei Fu

Cross-organizational authentication often requires credentials from several authorities. We construct a lattice-based protocol with independently issued capabilities bound to a periodic pseudonym authenticated by a trusted user registry and aggregated locally into one proof. Setup requires no system-wide lattice master trapdoor or cross-authority joint lattice secret. Repartitioning a fixed witness among authorities preserves the aggregate relation and proof dimensions. We prove fixed-witness selective unforgeability of the ideal protocol under honest issuance, authentication-signature security, normal-form module learning with errors (Module-LWE), and homogeneous module short-integer solution (Module-SIS). The proof uses classical random oracles, a programmable extendable-output function (XOF), an integer norm certificate, and a reference sampler with quantified error. A C++17 research prototype was evaluated in 23 configurations. Its 78,522-byte token becomes smaller than the per-attribute Module-Lattice-Based Digital Signature Algorithm (ML-DSA)-44 reference at 33 attributes and is 49.51% smaller at 64 attributes. With 64 attributes and 64 authorities, online signing and prepared verification took 56.038 and 8.729 ms, respectively. Complete local cold signing took 370.050 ms, and public matrices for 64 capabilities occupied 29.75 mebibytes (MiB). Aggregation reduces repeated token communication for larger witnesses, at the cost of preparation, public-state storage, and higher measured computation than the ML-DSA references.

Markus Rückert