Substring Matching Solution 2

This is a solution to a problem discussed at the 2025 research workshop. The goal is to prove that $X$ contains $y_1, \dots, y_k$ as substrings.

We present a scheme for substring matching which uses $$O\left(n + \left(\sum m_j \right)\log k + k \log n + h \right)$$ gates, where $h$ is the complexity of a hash function on $k$ inputs (which formally we assume to be a PRF).

Problem statement / notation

We have input strings $X$ of length $n$ and $Y^j$ of length $m_j$ ($1 \le j \le k$), and want to write an arithmetic circuit (with nondeterministic inputs) to prove that all the $Y^j$ are substrings of $X$.

The Merkle tree algorithm can do this with complexity $O(h(n + \sum m_j + k \log n))$.

Algorithm

For each $j$, let $\ell_j$ be the index at which $Y^j$ appears in $X$. We provide these as witnesses to the circuit in binary decomposition.

We pick a "random" $\alpha = H(X, \{Y^j\}, \{k_j\})$. Define the sets: $$S = \{X_i \alpha^i\}_{1 \le i \le n}, \quad T_j = \{Y^j_i \alpha^{i+\ell_j}\}_{1 \le i \le m_i}.$$ We can compute the elements of these sets in $O(n + mk + k \log n)$ time (computing $\alpha^{\ell_j}$ using binary exponentiation). It is enough for us to prove that $T_j \subseteq S$ for all $j$ (this is sound with failure probability $\mathrm{poly}(n)/p$ as long as $H$ is a PRF).

Now define the polynomials $$p(x) = \prod_{s \in S}(x-s), \quad q_j(x) = \prod_{s \in T_j}(x-t).$$ We now wish to show that $q_j \mid p$ (as polynomials) for all $j$.

Polynomial divisibility protocol

We'll now show a protocol to prove polynomial divisibility; say we wish to show $p_2 \mid p_1$ for some polynomials $p_1, p_2$ of degree $d_1, d_2$. Let $p_1 = rp_2$ (as polynomials); we let the coefficients of $r$ (as elements of $\mathbb{F}_p$) be public inputs. Let $\beta$ be a hash of all the inputs (including $r$). Then, we simply check that $p_2(\beta) d(\beta) = p_1(\beta)$, using $O(\deg p_1)$ multiplications. By degree counting, as long as $H$ is a PRF, this is sound with probability $(\deg p_1) / p$.

Note that this protocol assumes no bounds on the coefficients of $p_1, p_2, d$; it works entirely in $\mathbb{F}_p$.

Remainder of the algorithm

The complexity of the polynomial divisibility protocol was the degree of the larger polynomial, so if we apply it naively, we would have complexity $O(kn)$, which is too much.

Instead, create a binary tree on all the $q_i$, and label each node with the least common multiple (as polynomials) of its descendants. For example, the node above $q_1, q_2$ will be labeled with the polynomial $\mathrm{lcm}(q_1, q_2)$. The prover can compute the polynomials at each node and then provide all their coefficients as witnesses. Finally, for the proof, we execute a divisibility proof for every node and its children, and a divisibility proof that the top node divides $p(x)$. By soundness of the divisibility proofs, a valid proof necessarily implies that all of the $q_i$ divide $p$. The total degree of all polynomials in the binary tree is at most $O((\sum m_i) \log k)$, and the degree of $q$ is $n$, so the total complexity of all the divisibility checks is $O(n + (\sum m_i) \log k)$, as desired.

Note that we can actually use the same value of $\beta$ for all of these divisibility checks (hashing all the inputs together), so we only take one hash for all this time. There are also probably ways to save constant factors by not actually computing the lcms.