Paper 2026/1885

Compact Lattice-Based NIZK Arguments for Set Membership and Ring Signatures without RO

Abstract

Zero-knowledge proofs of set membership underpin privacy-preserving constructions such as ring signatures and anonymous credentials. Existing succinct constructions rely mainly on the Fiat--Shamir transform in the Random Oracle Model (ROM), while standard-model non-interactive proofs from post-quantum assumptions remain either generic and inefficient or asymptotically compact yet concretely impractical. A key obstacle is that existing lattice-based zero-knowledge systems operate over a single ambient modulus, forcing heterogeneous components to be homogenized, inflating parameters and weakening reductions. We introduce the first \emph{compact lattice-based NIZK arguments for set membership in the standard model} with proof size logarithmic in the set cardinality. Our construction matches the logarithmic proof size of accumulator-based ROM constructions while achieving post-quantum security without random oracles. The main technical ingredient is a new trapdoor $\Sigma$-protocol supporting linear relations modulo multiple heterogeneous moduli, allowing such relations to be handled at their native moduli without homogenization. This yields a modular approach to compact proofs compatible with lattice accumulators. As an application, we construct lattice-based ring signatures of size $O(\log R)\cdot \widetilde{O}(\lambda^{2})$ bits, improving the dependence on the security parameter $\lambda$ quadratically over the plain-model construction of Chatterjee et al. (CRYPTO~2021) while retaining optimal logarithmic dependence on the ring size $R$. Our construction is in the CRS model, which partly enables this improvement. The scheme achieves statistical anonymity and unforgeability under standard Module-LWE and Module-SIS assumptions. We also develop two additional tools of independent interest: (i) a generalized Merkle-tree accumulator over module lattices with base-$B$ decomposition, enabling finer efficiency--assumption trade-offs; and (ii) a message-binding technique that removes the need for costly lattice one-time signatures in standard-model ring signatures.