Arithmetic circuits for substring matching (proposed by Duru)

Can you write down an efficient arithmetic circuit to prove that a bunch of strings $Y^1, Y^2, ..., Y^r$ are substrings of a given string $X$?

See solutions here and here.

Arithmetic circuits (with nondeterminate witnesses)

We have chosen a large fixed prime number $p \approx 2^{64}$. An arithmetic circuit is a circuit (composed of wires and gates); each wire carries a value in the finite field $\mathbb{Z} / p \mathbb{Z}$, and each gate is either addition or multiplication. (Arithmetic circuits are analogous to Boolean circuits, which you may be familiar with.)

A string is a sequence of integers in, say, $\{1, ..., 26\}$ (note that $26 \ll p$).

The arithmetic circuit should take inputs $X_1, ..., X_n$ (the $n$ characters in $X$), $Y^i_j$ for $1 \leq i \leq k$ and $1 \leq j \leq m_i$ (the characters of the $k$ purported substrings; in practice, we have $m_i \ll n$); and some additional “nondeterminate witnesses” $Z_1, ..., Z_s$. The circuit should compute a single field element as output.

The circuit should have the following property, for any fixed $X$’s and $Y$’s:

• There exist $Z_1, ..., Z_s$ such that the circuit evaluates to $0$ if and only if each $Y^i$ is a substring of $X$.

We wish our arithmetic circuit to have the lowest possible complexity (which is defined as the number of multiplication gates).

Motivation

“Arithmetic circuits” are the basic model of computation used in zero-knowledge proofs. A solution to the problem will let us prove that some strings $Y^i$ are substrings of a string $X$ — while keeping the string $X$ (and potentially the substrings $Y^i$ as well) secret.

As a particular application, $X$ is a “mobile driver’s license” (MDL) — a serialization of the data on a California driver’s license — and the $Y$’s are substrings that one wants to publicize (e.g. name). Typical lengths for $X$ and the $Y^i$’s are 3000 and 32; the number $k$ of substrings might be 15.

Possible solutions

In the specific context of MDL pods, all the small strings are the same length – you can do it with Merkle trees of hashes of all possible substrings of that length

One possible solution: For each $Y^i$, if $Z^i$ is its position in $X$, we can shift $X$ by $Z^i$ in $O(n + m \log n)$ operations to be aligned with $Y^i$ and do $m$ comparisons. This is costly when $r$ and $n$ are large: its complexity is $O(r(n + m \log n))$.

Merkle tree solution: Here we prove that $Y^i$ exists in the Merkle tree of $X$ at contiguous indices. It can be done with complexity $O(P(rm + r\log n + n))$ where $P$ is the complexity of a single hash function.

What is a Merkle tree?

_A Merkle tree is a cryptographic binary-tree data structure that allows us to prove that an element exists in a list of size $n$ in complexity $O(\log n)$_ _For a deeper explanation see [this link](https://decentralizedthoughts.github.io/2020-12-22-what-is-a-merkle-tree/)_

Extension problem: What if you want subsequences instead of substrings?