(2026-03) Lookup Arguments over Rings and Applications to Batch-Verification of RAM Programs
2026-03-06
Lookup arguments are a key technique in SNARKs for reducing the cost of operations which are “arithmetization-unfriendly”, such as range checks and bitwise comparisons. The idea is to encode the valid outputs of the operation in a publicly known table, and then prove that every element of the SNARK witness belongs to the table. Existing constructions for lookup arguments, however, are designed for working over fields, making them incompatible with recent post-quantum lattice-based schemes that operate over rings.
In this work we formalize lookup arguments over rings for tables containing arbitrary ring elements. We bring attention to systematic issues that arise when translating techniques from fields to rings by showing several known lookup arguments are susceptible to attacks. We then extend two central polynomial IOPs, Plookup and LogUp, over the ring , and show how to compile them with polynomial commitments based on lattice assumptions to get succinct lattice-based lookup arguments. We additionally show how to apply ring lookups to obtain succinct arguments for batch-verification of RAM updates where the RAM entries are arbitrary ring elements.