Paper 2026/2435

TenseUp: Doubly-Efficient Lookup Arguments from Tensor Codes and Applications to Dynamic SNARKs

Abstract

Doubly-Efficient Lookup Arguments are specialized argument systems that enable succinctly proving the correctness of a batch of $k$ lookup accesses to a large table $\textbf{x}$ in time proportional to $k$ and sublinear in $|\textbf{x}|$. All existing such schemes suffer from one of the following limitations. Either they rely on elliptic-curve-based assumptions for their security, hence they are not secure against quantum adversaries, or are rather impractical, as they rely on algorithms for fast polynomial evaluations (that are mostly of theoretical interest), or operate over fields of small characteristic---making them incompatible with most modern argument systems. In this work, we use tensor codes to construct transparent and post-quantum secure updatable doubly-efficient lookup arguments that asymptotically outperform all existing schemes with the same properties, in terms of prover time and/or preprocessing. By further optimizing this approach for a specific type of two-dimensional tensor codes, we build TenseUp, a concretely efficient lookup argument that, as shown in our experiments, has comparable or even better performance than state-of-the-art non-post-quantum secure prior doubly-efficient lookup arguments. As an independent contribution, we propose a general-purpose compiler for building dynamic SNARKs from any ``static'' SNARK, via judicious use of updatable doubly efficient lookup arguments to store and access witness updates. Applying our compiler with different SNARKs and lookup arguments can lead to different novel results; e.g., combining a hash-based SNARK with our lookup arguments yields the first transparent and post-quantum secure dynamic SNARK.