Unlocking the lookup singularity with Lasso

ePrint Report: Unlocking the lookup singularity with Lasso

Srinath Setty, Justin Thaler, Riad Wahby

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.


For $m$ lookups into a table …

eprint report family justin performance prove report untrusted