Lemma 7.3 — $\mathrm{SH}_c$ is an average-case $(t_1, (2c-1)t_1, m_1, m_1 - \lceil n/c\rceil\log_2(n-c+1))$-biometric embedding

Let $\mathcal F$ be a finite alphabet and $1 \le c \le n$. Let $\mathrm{SH}_c$ map a string $w \in \mathrm{Edit}_{\mathcal F}(n)$ (length $n$, insertion/deletion distance) to its $c$-shingling, a subset of $\mathcal F^c$, compared in the set-difference metric $\mathrm{SDif}(\mathcal F^c)$. For every $t_1 \in \mathbb N$ and real $m_1$, $\mathrm{SH}_c$ is an average-case

biometric embedding of $\mathrm{Edit}_{\mathcal F}(n)$ into $\mathrm{SDif}(\mathcal F^c)$. That is:

1. if $w, w'$ are within $t_1$ insertions and deletions, then $|\mathrm{SH}_c(w) \triangle \mathrm{SH}_c(w')| \le (2c - 1)t_1$;
2. for every pair $(W, I)$ with $\tilde{\mathbf H}_\infty(W \mid I) \ge m_1$, we have $\tilde{\mathbf H}_\infty(\mathrm{SH}_c(W) \mid I) \ge m_1 - \lceil n/c \rceil \log_2(n - c + 1)$.

Shingling turns the edit metric, for which no direct secure sketch is known, into set difference while losing a controlled amount of entropy.

Formalization Note. The paper says "for any $c$"; $1 \le c \le n$ is made explicit (it is needed for $n - c + 1 \ge 1$ and for the shingles to exist). $\lceil n/c \rceil$ is ⌈(n : ℝ) / c⌉₊. The edit distance is the published weighted edit distance with insertion/deletion cost $1$ and replacement cost $2$; the intermediate strings of an edit sequence may have any length, and shingles is defined for every length.