Protocols for "almost equality" with one-sided error
Here are two solutions. In both cases, the inputs are $x,y \in \{0,1\}^n$, and we are interested in checking whether the Hamming distance between $x$ and $y$ is at most $k$ or not.

Solution 1 (D.W.):

The two parties decide on a random string $z \in \mathbb{Z}_{2k+3}^n$, compute $\alpha = \langle x,z \rangle$ and $\beta = \langle y,z \rangle$, and accept if $\alpha - \beta \notin \{k+1,k+2\}$.

If the Hamming distance between $x$ and $y$ is $d$, then $\alpha - \beta$ is distributed as the sum of $d$ many $\pm 1$ random values. When $d \leq k$, clearly $\alpha - \beta \notin \{k+1,k+2\}$. Conversely, when $d &gt; k$, the probability that $\alpha - \beta \in \{k+1,k+2\}$ is $\Omega(2^{-k})$.

Solution 2 (Sa'ar Zehavi):

The two parties decide on a random partition of $\{1,\ldots,n\}$ into $k+1$ parts, and run the one-bit equality protocol on each of them. They accept if the equality protocol succeeds (declares "equal") on at least one of them.

If the Hamming distance between $x$ and $y$ is at most $k$, then clearly the parties always accept. Otherwise, with probability $\Omega(e^{-k})$ all the $k+1$ parts will be different, and so the equality protocol will fail on all of them with probability $\Omega(2^{-k})$.