Paper 2026/1540

Lattice-Based Shuffle Arguments using Subset Checking

Abstract

Shuffle arguments are a fundamental building block in mix-nets and related privacy-preserving systems, where they are used to prove that a set of ciphertexts or commitments is a permutation and rerandomization of another set without changing the underlying messages. Existing communication-efficient shuffle arguments rely on classical assumptions, whereas known lattice-based constructions are still significantly less efficient. In this paper, we present a lattice-based shuffle argument with short proofs by using the subset-checking approach of Abdolmaleki et al. (SCN 2024) in the lattice setting. Our main construction proves correct shuffles of Ajtai commitments and is built on the ABDLOP commitments and lattice-based zero-knowledge framework of Lyubashevsky et al. (Crypto 2022). The protocol is secure under the Module-SIS and Module-LWE assumptions in the random oracle model. A key technical ingredient is a rerandomization method for the derived commitment key, which restores the distributional properties needed for soundness even when the input commitments may depend on the prover. We further extend our approach to obtain shuffle arguments for ciphertexts and public keys, yielding applications to lattice-based mix-nets and single secret leader election. Finally, we implement our construction and compare it with prior lattice-based shuffle protocols, obtaining substantial improvements in communication, proving time, and verification time.