Improved Multimodal Private Signatures from Lattices

Multimodal private signatures (MPS), introduced by Nguyen et al. (CRYPTO’22), are a new cryptographic primitive that significantly generalizes the concept of tracing in traditional anonymity-oriented signature systems, and may enable appealing privacy-preserving applications. A construction of MPS from lattice assumptions was proposed by Nguyen et al., but it suffers from several limitations, in terms of efficiency, security and expressiveness. In the present work, we present an improved lattice-based MPS scheme that simultaneously offers improvements over Nguyen et al.’s scheme in all three mentioned aspects. Specifically, our scheme: (i) fully achieves post-quantum security via proofs in the quantum random oracle model (QROM), rather than the ROM; (ii) addresses more expressive signing and disclosing functions; and (iii) features smaller public key size and signature size. In other words, our scheme demonstrates a somewhat surprising win-win-win solution. In the process, we put forth several specialized techniques and optimizations that could be of independent interest.