Lookup Arguments over Rings and Applications to Batch-Verification of RAM Programs

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 an arithmetization-unfriendly 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 study lookup arguments over rings for tables containing arbitrary ring elements. We show that directly extending known lookup arguments over rings is susceptible to attacks. We then extend two central polynomial IOPs, Plookup and LogUp, over the ring R= Z_q[X]/(X^d + 1), 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.