Group signatures and more from isogenies and lattices: generic, simple, and efficient

• Published in: Designs, codes, and cryptography codes, and cryptography, 2023-06, Vol.91 (6), p.2141-2200
• Main Authors: Beullens, Ward, Dobson, Samuel, Katsumata, Shuichi, Lai, Yi-Fu, Pintore, Federico
• Format: Article
• Language: English
• Subjects: Algorithms; Coding and Information Theory; Computer Science; Cryptography; Cryptology; Digital signatures; Discrete Mathematics in Computer Science; Encryption; Interactive systems; Lattices; Security
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-023-01192-x

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 .