Unlocking the Lookup Singularity with Lasso

This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector \(a \in \mathbb {F}^m\) and prove that all entries of a reside in some predetermined table \(t \in \mathbb {F}^n\) . Lasso’s performance characteristics unlock the so-called “lookup singularity”. Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties.