Theorem 7.5 — an average-case secure sketch for edit distance with loss $\lceil n/c\rceil\log_2(n-c+1) + (2c-1)t\lceil\log(F^c+1)\rceil$

Let $\mathcal F$ be a finite alphabet with $F = |\mathcal F|$ letters, and let $\mathrm{Edit}_{\mathcal F}(n)$ be the strings of length $n$ over $\mathcal F$, with distance the smallest number of character insertions and deletions transforming one string into the other. For all natural numbers $n, c, t$ with $1 \le c \le n$ and every real $m$, there is an average-case

secure sketch.

The first term of the entropy loss comes from the shingling embedding and its recovery information, the second from PinSketch run on the shingle set over the universe $\mathcal F^c$ embedded into $GF(2^\mu)^*$ with $\mu = \lceil \log(F^c + 1) \rceil$. The parameter $c$ trades the two terms off.

Formalization Note. The paper's statement carries "$0 < \epsilon \le 1$", a parameter that does not occur in the conclusion (a carry-over from Theorem 7.4); it is dropped. $t$ is universally quantified, and the implicit range $1 \le c \le n$ is made explicit. $\lceil \log(F^c + 1) \rceil$ is Nat.clog 2 (F ^ c + 1), the least $\mu$ with $F^c + 1 \le 2^\mu$, and $\lceil n/c \rceil$ is ⌈(n : ℝ) / c⌉₊. "Efficient" is dropped. The sketch type and the (possibly randomized) procedures are existentially quantified; the edit distance is the published weighted edit distance with cost $1$ per insertion or deletion and $2$ per replacement.