Paper 2026/494

GlueLUT: Efficient Lookup Table Arguments over Residue Rings

Abstract

Lookup table polynomial interactive oracle proofs (LUT PIOPs) make SNARK arithmetizations concise, yet almost all efficient constructions assume field arithmetic. We show that directly instantiating them over a composite residue ring \(\mathbb Z_Q\) can be unsound: component-wise set checks preserve the residue multiset in each CRT component but lose the alignment across components. We formalize this obstruction, which we call the CRT alignment ambiguity. To overcome this ambiguity, we present GlueLUT, a family of efficient LUT PIOPs over residue rings. GlueLUT runs the lookup over an auxiliary field while retaining the arithmetic proof over \(\mathbb Z_Q\), and then proves consistency between the two witness representations. Our first construction, GlueLUT-4Sq, introduces a cross-modulus consistency (CMC) PIOP, which proves that witnesses over two coprime moduli encode the same integer vector. We construct the CMC PIOP via a range-check PIOP over the product ring using the Lagrange four-square decompositions, structured Johnson–Lindenstrauss projections, and a GKR-style consistency check. For a witness of size \(n\), a table of size \(m\), and security parameter \(\lambda\), GlueLUT-4Sq has \(O(n+m)\) algebraic prover work after witness generation and \(O(\operatorname{poly}(\lambda,\log n,\log m))\) verifier work and proof size. Our second construction, GlueLUT-Fold, uses random rank-one folded consistency checks to achieve better concrete prover efficiency and has \(O(n+m)\) prover work, at the cost of \(O(\sqrt n+\operatorname{poly}(\lambda,\log n,\log m))\) verifier work; its proof size is \(O(\log n+\log m)\). We implement GlueLUT-4Sq and GlueLUT-Fold as stand-alone PIOPs and report prototype results that corroborate our theoretical efficiency analysis.