Paper 2026/1639

LUNA+: More Succinct Post-Quantum ZK-SNARKs from Computational Privacy

Abstract

We present LUNA+, a refinement of the LUNA designated-verifier lattice-based ZK-SNARG that achieves significantly improved concrete succinctness. While the original LUNA scheme achieves quasi-optimal asymptotic proof length ($O(\lambda)$), its practical parameters are constrained by its statistical privacy analysis. This analysis, founded on a Leftover Hash Lemma with Leakage (LHLL), necessitates the use of polynomially large, but still significant "smudging" noise to guarantee statistical uniformity. This noise inflation directly propagates to larger lattice dimension and modulus parameters and, consequently, larger proof and CRS sizes. Our core contribution is a new privacy analysis that replaces this statistical foundation with a computational one. We demonstrate that the circuit privacy of LUNA's re-randomization procedure can be securely based on the computational hardness of the Matrix Hint-Module Learning With Errors (MH-MLWE) problem. This computational approach avoids the need for large statistical noise and enables a key optimization: we decouple the secret re-randomization noise from the fresh masking noise. We then formalize and solve an optimization problem to find the minimal noise parameters that satisfy both correctness and the MH-MLWE security reduction. In the process, we also introduce a new problem called Coset Error Knapsack MH-MLWE in which the MLWE error is sampled from a coset of a lattice, which we show is as hard as the standard MH-MLWE problem, and may be of independent interest. This new analysis results in substantial concrete efficiency gains. For a 128-bit security level and an R1CS instance of size $2^{16}$, LUNA+ reduces the proof size by $\approx 25\%$ (from 5.60 KB to 4.22 KB) and the compressed CRS size by $\approx 73\%$ (from 2.06 GB to 0.54 GB) compared to the original LUNA. These succinctness improvements are also accompanied by performance gains, including up to a $\approx 1.73\times$ speedup in setup, a $\approx 1.53\times$ speedup in addition and a $1.44\times$ speedup in decryption for the implementation parameters.