Paper 2026/008

A SNARK for (Non-)Subsequences with Text-Sub-Linear Proving Time

Abstract

A keyword $\mathbf{s}$ is a subsequence of a text $\mathbf{t}$ if $\mathbf{s}$ can be obtained by deleting some characters from $\mathbf{t}$; otherwise, $\mathbf{s}$ is a non-subsequence of $\mathbf{t}$. (Non-)subsequence relationships arise in various fields, including genetic analysis, blockchains, and natural language processing. Recently, Ling et al. (SCN 2024) proposed a succinct argument for non-subsequences based on multivariate sumcheck (Lund et al., FOCS 1990) whose prover's running time is at least $\mathcal{O}(n + N + |\Sigma|)$, where $n$ and $N$ are respectively the lengths of strings $\mathbf{s}$ and $\mathbf{t}$, and $\Sigma$ is the alphabet over which $\mathbf{s}$ and $\mathbf{t}$ are defined. As shown in their work, proving non-subsequence relationships is non-trivial since one needs to decompose such an argument into smaller components for sumcheck, permutation, and lookup. We propose a subsequence scheme that separates proving (non-)subsequences into the following two phases: (i) a preprocessing phase and (ii) a (non-)subsequence proving phase, assuming $n \ll N$ (i.e., $|\mathbf{s}| \ll |\mathbf{t}|$). Specifically, we can generate a one-time preprocessing proof with inputs $\mathbf{t}$ and $\Sigma$, without any knowledge of $\mathbf{s}$. When $\mathbf{s}$ is known, we can determine whether $\mathbf{s}$ is a subsequence of $\mathbf{t}$ and prove the corresponding statement. Employing cached quotients (IACR ePrint 2022/1763), we achieve a running time quasi-linear in $N + |\Sigma|$ for preprocessing, while the running time of proving a (non-)subsequence relationship is $\mathcal{O}(n \log_2 (N + |\Sigma|))$ for each query $\mathbf{s}$. Since $n \ll N$ and $\log_2(N + |\Sigma|)$ grows sub-linearly with the text size, this saves the prover's running time, assuming a preprocessing depending only on $\mathbf{t}$ is computed in advance. Hence, we achieve a \textit{text-sub-linear} proving time.