# Locality-Preserving Hashing for Shifts with
Connections to Cryptography††thanks: This is a full version of [9].

Elette Boyle IDC Herzliya, Israel and NTT Research, USA.
<EMAIL_ADDRESS>Itai Dinur Ben-Gurion University, Be’er Sheva, Israel.
<EMAIL_ADDRESS>Niv Gilboa Ben-Gurion University, Be’er Sheva, Israel.
<EMAIL_ADDRESS>Yuval Ishai Technion, Haifa Israel<EMAIL_ADDRESS>Nathan Keller Bar-Ilan University, Ramat Gan, Israel.
<EMAIL_ADDRESS>Ohad Klein Bar-Ilan University, Ramat Gan, Israel.
<EMAIL_ADDRESS>
###### Abstract

Can we sense our location in an unfamiliar environment by taking a sublinear-
size sample of our surroundings? Can we efficiently encrypt a message that
only someone physically close to us can decrypt? To solve this kind of
problems, we introduce and study a new type of hash functions for finding
shifts in sublinear time. A function $h:\\{0,1\\}^{n}\to\mathbb{Z}_{n}$ is a
$(d,\delta)$ locality-preserving hash function for shifts (LPHS) if: (1) $h$
can be computed by (adaptively) querying $d$ bits of its input, and (2)
$\Pr\left[h(x)\neq h(x\ll 1)+1\right]\leq\delta$, where $x$ is random and $\ll
1$ denotes a cyclic shift by one bit to the left. We make the following
contributions.

  * •

Near-optimal LPHS via Distributed Discrete Log. We establish a general two-way
connection between LPHS and algorithms for distributed discrete logarithm in
the generic group model. Using such an algorithm of Dinur et al. (Crypto
2018), we get LPHS with near-optimal error of $\delta=\tilde{O}(1/d^{2})$.
This gives an unusual example for the usefulness of group-based cryptography
in a post-quantum world. We extend the positive result to non-cyclic and
worst-case variants of LPHS.

  * •

Multidimensional LPHS. We obtain positive and negative results for a
multidimensional extension of LPHS, making progress towards an optimal
2-dimensional LPHS.

  * •

Applications. We demonstrate the usefulness of LPHS by presenting
cryptographic and algorithmic applications. In particular, we apply
multidimensional LPHS to obtain an efficient “packed” implementation of
homomorphic secret sharing and a sublinear-time implementation of location-
sensitive encryption whose decryption requires a significantly overlapping
view.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contribution
      1. 1.1.1 Near-Optimal LPHS via Distributed Discrete Log
      2. 1.1.2 Multidimensional LPHS
      3. 1.1.3 Applications
  2. 2 Preliminaries
    1. 2.1 Locality-Preserving Hash Functions for Shifts
    2. 2.2 Simple LPHS Properties and Reductions
  3. 3 LPHS and Distributed Discrete Log
    1. 3.1 Generic Group Model and Distributed Discrete Log
    2. 3.2 Reductions Between LPHS Variants and DDL
  4. 4 Multidimensional LPHS
    1. 4.1 Upper bounds on 2D-LPHS algorithms
      1. 4.1.1 A simple 2D-LPHS with error rate $\delta=O(d^{-1/2})$
      2. 4.1.2 An IRW-based 2D-LPHS with error rate $\delta=O(d^{-4/5})$
      3. 4.1.3 3-Stage-Hash: a 2D-LPHS algorithm with $\delta=\tilde{O}(d^{-7/8})$
      4. 4.1.4 Conjectured optimal algorithm
    2. 4.2 Lower bounds on 2D-LPHS algorithms
  5. 5 LPHS for Worst-Case Inputs
    1. 5.1 Cyclic LPHS for Worst-Case Inputs
    2. 5.2 Non-Cyclic LPHS for Worst-Case Inputs
  6. 6 Applications
    1. 6.1 Packed Homomorphic Secret Sharing
      1. 6.1.1 Multidimensional DDL
      2. 6.1.2 $k$D-DDL from $k$D-LPHS
      3. 6.1.3 From $k$D-DDL to Packed HSS
    2. 6.2 Location-Sensitive Encryption
      1. 6.2.1 Building Sublinear LSE
    3. 6.3 Algorithmic Applications
      1. 6.3.1 Succinct sublinear-time sketching for shifts
      2. 6.3.2 Locality-sensitive hashing and near-neighbor data structures for shifts
  7. A LPHS Results Based on Iterative Random Walks [23]
    1. A.1 The Basic LPHS
    2. A.2 The Random Walk LPHS
    3. A.3 The Iterated Random Walk LPHS
      1. A.3.1 Details of the Iterated Random Walk LPHS
      2. A.3.2 The Cyclic Random Walk LPHS
      3. A.3.3 Las Vegas LPHS for Big Shifts

##  1 Introduction

A locality-preserving hash function [35, 33] is a distance-respecting mapping
from a complex input space to a simpler output space. Inspired by recent
results in cryptography, we study a new kind of locality-preserving hash
functions that map strings to integers while respecting the shift distance
between pairs of input strings with high probability. A distinctive feature of
these hash functions is that they can be computed in sublinear time with low
error probability.

##### Why shifts? Why sublinear?

Our hash functions for shifts can be thought of as sublinear-time location
sensors that measure a relative position in an unfamiliar environment by
taking a sublinear-size sample of the surroundings. This can apply in a
variety of settings. For instance, “surroundings” may refer to a local view of
an unexplored territory, a long string such as a DNA sequence, an external
signal such as a GPS synchronization sequence, a digital document such as big
pdf file or a virtual world, or a huge mathematical object such as a
cryptographic group. See [7, 36] for applications of shift finding to GPS
synchronization, image alignment, motion estimation, and more.111While
previous related works study a noise tolerant variant of shift distance, which
arises naturally in the applications they consider, in this work we focus on
the simpler noiseless case. Beyond theoretical interest, the simpler notion is
motivated by applications. For instance, a local view of a digital document or
a mathematical object is noiseless. The noisy case is studied in a follow-up
work [10], which obtains nearly tight bounds on the (sublinear) amount of
random noise that can be tolerated.  We will discuss additional cryptographic
and algorithmic applications in Section 1.1.3 below. We are motivated by
scenarios in which the local view contains an enormous amount of relevant
information that cannot be naively sub-sampled or compressed. This calls for
sublinear-time solutions.

##### Simple shift-finding solutions.

To motivate the new primitive, consider the following simple shift-finding
problem. An $n$-bit string $x$ is picked uniformly at random, and then
cyclically shifted by $s$ bits the left, for some $0\leq s<n$. Let $y$ be the
resulting string. For instance, $x,y$ may be obtained by measuring the same
periodic signal at different phases. We write $y=x\ll s$. The shift-finding
problem is to find the shift amount $s$ given $x$ and $y$.

In a centralized setting, where $x$ and $y$ are both given as inputs, it is
easy to solve the problem in sublinear time (with small error probability),
querying only $\tilde{O}(n^{1/2})$ bits of the input, by matching substrings
of $x$ of length $\ell=O(\log n)$ starting at positions $1,2,\ldots,\sqrt{n}$
with length-$\ell$ substrings of $y$ whose starting position is a multiple of
$\sqrt{n}$. (This is a simplified version of a noise-resilient algorithm from
[7].) This algorithm is nearly optimal, since any shift-finding algorithm for
an unbounded shift amount $s$ should read $\Omega(\sqrt{n})$ bits of the input
[8].

In a distributed setting, a natural goal is to design a sketching algorithm
that compresses a single input into a short sketch, such that given the
sketches of $x$ and $y$ one can recover $s$ with high probability. Note that
the previous centralized algorithm does imply such a sublinear-size sketch,
but only with $\tilde{O}(\sqrt{n})$ output size, which is far from optimal.
Instead, one could use the following classical approach [21]: let the sketch
of $x$ be an integer $0\leq z_{x}<n$ that minimizes $x\ll z_{x}$ (viewed as an
$n$-bit integer), and similarly for $y$. It can be easily seen that
$s=z_{x}-z_{y}\mod n$ whenever the minimum is uniquely defined.

The logarithmic sketch size of this simple solution is clearly optimal.
Moreover, it realizes something even stronger than sketching: a hash function
$h:\\{0,1\\}^{n}\to\mathbb{Z}_{n}$ that respects cyclic shifts in the sense
that for a random input $x$, we have $h(x)=h(x\ll s)+s$ except with small
probability. That is, shifting the input by $s$ changes the output by $s$ in
the same direction. This is useful for applications. For instance, given $t$
hashes $z_{i}=h(y_{i})$, where $y_{i}=x\ll s_{i}$ for $i=1,\ldots,t$, one can
easily compute in time $\tilde{O}(t)$ the relative offsets of all $y_{i}$.

The main downside of the above hashing-based solution compared to the
centralized algorithm is its linear running time. A natural question is
whether one can enjoy the best of both worlds:

> Can we combine the sublinear running time of the centralized algorithm with
> the optimal sketch size and locality-sensing features of the hashing-based
> solution?

###  1.1 Our Contribution

We initiate a study of hashing-based solutions to the shift-finding problem.
We capture such solutions via the following notion of locality-preserving hash
function for shifts.

######  Definition 1.1.

A function $h:\\{0,1\\}^{n}\to\mathbb{Z}_{n}$ is a $(d,\delta)$ locality-
preserving hash function for shifts (LPHS) if: (1) $h$ can be computed by
(adaptively) querying $d$ bits of its input, and (2) $\Pr\left[h(x)\neq h(x\ll
1)+1\right]\leq\delta$, where $x$ is random and $\ll 1$ denotes a cyclic shift
by one bit to the left.

Note that, by a union bound, an LPHS as above satisfies $\Pr\left[h(x)\neq
h(x\ll s)+s\right]\leq s\cdot\delta$ for any shift amount $0\leq s<n$. Thus,
an LPHS has a better accuracy guarantee for smaller shifts. Intuitively, an
LPHS can be thought of as a sublinear-time computable location identifier that
suffices (with high probability) for determining the exact relative location
with respect to adjacent identifiers.

##### Other LPHS flavors.

The above notion of LPHS addresses the basic shift-finding problem as
discussed above, but is limited in several important ways: it only considers
cyclic shifts and 1-dimensional inputs, and it only guarantees average-case
correctness for uniformly random inputs. To address these limitations, we
additionally consider other flavors of the basic LPHS notion defined above
that are more suitable for applications. These include a non-cyclic variant,
where instead of $x\ll 1$ we remove the leftmost bit of $x$ and add a random
bit on the right; a $k$-dimensional variant, where the input is a
$k$-dimensional matrix and the output is in $\mathbb{Z}_{n}^{k}$; and a worst-
case variant where the quantification is over an arbitrary $x$ that is “far
from periodic” and the probability is over the choice of $h$. (The latter
variant better corresponds to the typical notion of a randomized hash
function.) The applications we present crucially depend on these extensions.

####  1.1.1 Near-Optimal LPHS via Distributed Discrete Log

We establish a general two-way connection between LPHS and algorithms for the
distributed discrete logarithm (DDL) problem [12]. Before explaining this
connection, we start with relevant background.

The traditional discrete logarithm (DL) problem is parameterized by a cyclic
group $\mathbb{G}$ of order $n$ with a generator $g$, where $n$ is typically a
large prime. The challenge is to recover a random $u\in\mathbb{Z}_{n}$ from
$g^{u}$. Many cryptographic applications rely on the conjectured
intractability of the DL problem in special types of groups, including
subgroups of $\mathbb{Z}^{*}_{p}$ and certain families of elliptic curves.

The DDL problem is a distributed variant of the DL problem that was recently
introduced in the context of group-based homomorphic secret sharing [12]. In
DDL there are two parties, where the first party’s input is $g^{u}$ for a
random $u$, and the second party’s input is $g^{u+s}$ where $s\in\\{0,1\\}$
(more generally, $s$ can be a small integer). The goal is for each party to
locally output an integer, such that the difference between the two outputs is
$s$. One can assume without loss of generality that the two parties run the
same algorithm.

Note that a DL algorithm can be used to perfectly solve the DDL problem.
However, this is computationally infeasible in a cryptographically hard group,
where $n$ is enormous. Instead, a DDL algorithm uses a bounded running time
(typically polylogarithmic in the group order $n$) to obtain the correct
difference except with error probability $\delta$. For instance, the initial
solution proposed in [12] uses a pseudorandom function to mark each group
element as “distinguished” with probability $\delta$, and makes each party, on
input $v$, output the smallest $z\geq 0$ such that $v\cdot g^{z}$ is
distinguished. The (expected) running time of this algorithm is roughly
$1/\delta$, and the error probability is $\delta$ (corresponding to the case
where $s=1$ and $g^{u}$ is distinguished).

The DDL problem can be related to the LPHS problem (over a non-binary
alphabet) by associating each party’s DDL input $v$ with an LPHS input
consisting of the sequence of group elements
$x=(v,gv,g^{2}v,\ldots,g^{n-1}v)$. Indeed, multiplication of the DDL input by
$g$ corresponds to a cyclic shift of $x$ by one symbol to the left. We
formalize this intuition by proving a general two-way relation between LPHS
and DDL algorithms in the generic group model [41], where group elements are
assigned random labels and the algorithm is only given oracle access to the
group operation.222Specifically, in Section 3 we prove that any LPHS gives a
DDL algorithm (in the generic group model) with similar parameters, while any
DDL algorithm gives an LPHS with a negligible cost in error probability
assuming $d=O(n^{1/4})$ and $n$ is prime.

The applications we derive from the above connection give an unusual example
for the usefulness of results on group-based cryptography in a post-quantum
world. Indeed, all traditional applications of group-based cryptography are
subject to quantum polynomial-time attacks using Shor’s algorithm, and are
thus useless in a post-quantum world. If scalable quantum computers become a
reality, cryptosystems that are “quantum broken” will become obsolete. In
contrast, sublinear-time classical algorithms will still be meaningful even in
a post-quantum world.

##### LPHS constructions.

The simple DDL algorithm from [12] corresponds to a $(d,\delta)$-LPHS where
$\delta=\tilde{O}(1/d)$. Another simple LPHS construction with similar
parameters, implicit in a DDL algorithm from [13], makes a simple use of
MinHash [15]: let $h(x)$ output the index $i$, $1\leq i\leq d$, that minimizes
the value of a MinHash applied to a polylogarithmic-length substring of $x$
starting from $x_{i}$.

It is tempting to conjecture that the above simple LPHS constructions are
near-optimal, in the sense that $\delta=o(1/d)$ is impossible. It turns out,
however, that a quadratic improvement can be obtained from a recent optimal
DDL algorithm due to Dinur et al. [23]. Their _Iterated Random Walk (IRW)_
algorithm, whose self-contained description appears in Appendix A is based on
a carefully chosen sequence of random walks in the group. It can be viewed as
a non-trivial extension of Pollard’s classical “kangaroo” DL algorithm [39],
which runs in time $\tilde{O}(\sqrt{n})$ and has low space complexity.
Applying the LPHS vs. DDL connection to the positive and negative results on
DDL from [23], we get the following theorem.

######  Theorem 1.2 (Near-optimal LPHS).

There exist $(d,\delta)$-LPHS with: (1) $\delta=\tilde{O}(d^{-2})$ for
$d\leq\sqrt{n}$, and (2) $\delta=n^{-\omega(1)}$ for $d=\tilde{O}(\sqrt{n})$.
Furthermore, both “$\delta=\tilde{O}(d^{-2})$” in (1) and
“$d=\tilde{O}(n^{1/2})$” in (2) are optimal up to polylogarithmic factors.

Interestingly, any sublinear-time LPHS must inherently make adaptive queries
to its input. Adaptive queries are unusual in the context of sublinear metric
algorithms, but were previously used in sublinear algorithms for approximating
edit distance [40, 17, 31]. A random walk technique was recently used in [34]
to obtain a sublinear-time embedding of edit distance to Hamming distance.

##### Additional variants.

We prove similar bounds for the worst-case and non-cyclic variants of LPHS,
which are motivated by the applications we discuss in Section 1.1.3. The
result for the worst-case variant is obtained via a general reduction, and
inevitably excludes a small set of inputs that are close to being periodic.
The result for the non-cyclic case does not follow generically from the cyclic
case (except when $d<n^{1/3}$), and requires a special analysis of the IRW
algorithm [23]. Also, in this case only (1) holds, since the error probability
of a non-cyclic LPHS must satisfy $\delta=\Omega(1/n)$ regardless of $d$. In
fact, whereas $d=\sqrt{n}$ is the hardest case for Theorem 1.2 in the non-
cyclic case (in that (1) for $d=\sqrt{n}$ easily implies (1) for smaller $d$),
it is the easiest for the cyclic case (in that it is implied by the simpler
algorithm of Pollard [39]).

In the context of sketching for shifts, the above results imply solutions that
simultaneously achieve near-optimal sketch size of at most polylog$(n)$, near-
optimal running time of $\tilde{O}(\sqrt{n})$, and negligible error
probability, for both cyclic and non-cyclic shifts, and for arbitrary “far-
from-periodic” inputs.

####  1.1.2 Multidimensional LPHS

Viewing LPHS as a location identifier, it is natural to consider a
generalization to two dimensions and beyond. Indeed, a 2-dimensional (non-
cyclic) LPHS can be useful for aligning or sequencing local views of a big
2-dimensional (digital or physical) object. A $k$-dimensional LPHS maps a
$k$-dimensional matrix (with entries indexed by $\mathbb{Z}_{n}^{k}$) into a
vector in $\mathbb{Z}_{n}^{k}$ so that (cyclically) shifting the input matrix
by 1 in axis $i$ changes the output vector by the unit vector $e_{i}$, except
with $\delta$ error probability. As before, this guarantees recovering an
arbitrary shift vector with error probability that scales with the $\ell_{1}$
norm of the shift.

##### Upper bounds.

In the 2-dimensional case, the algorithm can be viewed as allowing two non-
communicating parties, who are given points $(x,y)$ and $(x+\alpha,y+\beta)$
in the same random for unknown $\alpha,\beta\in\\{0,1\\}$, to maximize the
probability of synchronizing at the same point, where only $d$ queries are
allowed. A straightforward approach is to use a MinHash algorithm in which the
parties take the minimal hash value computed on values of a $d^{1/2}\times
d^{1/2}$ matrix of elements beginning at the location of each party, resulting
in a $(d,\delta)$-LPHS with $\delta=\tilde{O}(d^{-1/2})$. A better error bound
of $\delta=\tilde{O}(d^{-2/3})$ can be obtained by combining the application
of MinHash on one axis with the application of the aforementioned optimal IRW
algorithm on the other axis.

We present three improved algorithms in Section 4. The simplest of those, with
a bound of $\delta=\tilde{O}(d^{-4/5})$, is obtained by applying IRW on both
axes. A natural idea is to first synchronize on the column; then,
synchronizing on the row is easy, using the 1-dimensional IRW algorithm. To
synchronize on the column, the parties perform the 1-dimensional IRW algorithm
with $d/d^{\prime}$ ‘horizontal’ steps, where the information used to
determine each step is distilled from the column in which the current point
resides by using an IRW algorithm with $d^{\prime}$ ‘vertical’ steps. The
analysis in Section 4 (Lemma 4.2) shows that the bound
$\delta=\tilde{O}(d^{-4/5})$ is obtained for the parameter
$d^{\prime}=d^{3/5}$.

Our main upper bound is obtained by a more complex algorithm, which – perhaps,
surprisingly – does not rely on the optimal 1-dimensional IRW algorithm at
all. We prove:

######  Theorem 1.3.

For $n=\tilde{\Omega}(d)$, there is a 2-dimensional $(d,\delta)$-LPHS with
$\delta=\tilde{O}(d^{-7/8})$. There is also a non-cyclic 2-dimensional LPHS
with the same parameters.

The algorithm we use to prove Theorem 1.3 consists of three stages. After each
stage the parties either converge to the same location, in which case they
stay synchronized to the end of the algorithm, or the two walks are within a
bounded distance from each other. Stage 1 begins with a distance of at most
$1$ on each axis, and is a straightforward application of the 2-dimensional
MinHash-based algorithm. Stage 2 begins with a distance of at most $\sqrt{d}$
on each axis and uses an asymmetric deterministic walk that consists of
$\sqrt{d}$ horizontal steps of size $\sim d^{1/4}$, where each step is pseudo-
randomly determined by information distilled from a vertical walk of length
$\sqrt{d}$ and step sizes $\sim d^{1/4}$. Stage 3 begins with a distance of at
most $d^{3/4}$ on each axis and uses a different deterministic walk. This
time, the horizontal steps are of size $1$, while the vertical steps are of
size about $d^{3/8}$, and unlike all other steps, can be negative. The
analysis of the algorithm relies on martingale techniques.

Finally, we present another 2-dimensional LPHS algorithm, which seems harder
to analyze, but for which we conjecture that the error rate is at most
$\tilde{O}(d^{-1})$. This bound is essentially the best one can hope for given
the lower bound discussed below. The idea behind this algorithm is to not
treat the axes separately but rather to perform a series of deterministic
walks over $\mathbb{Z}^{2}$, with step sizes of about
$d^{1/4},d^{3/8},d^{7/16},\ldots,\sqrt{d}/2$. Our experiments suggest that the
error rate of this algorithm is indeed $\tilde{O}(d^{-1})$. However, the
analysis (and especially deterministic resolution of cycles in the random
walk) is quite involved, and settling our conjecture is left open for future
work. Nevertheless, the heuristic algorithm can be used in cryptographic
applications (such as packed homomorphic secret sharing which is described
next) without compromising their security. Moreover, the worst-case scenario
in which the error is larger than predicted by our experiments can be easily
detected by applications.

##### Lower bound.

We complement our positive results by proving the following lower bound,
extending in a nontrivial way the lower-bound for 1-dimensional LPHS obtained
from [23] via the DDL connection.

######  Theorem 1.4.

For $n=\Omega(d^{2/k})$, any $k$-dimensional $(d,\delta)$-LPHS satisfies
$\delta=\Omega(d^{-2/k})$.

The intuition is related to the birthday bound. A $k$-dimensional box with
edge length $d^{2/k}$ contains $d^{2}$ points. If the $k$-dimensional shift is
uniform within this box, we expect the $d$ queries of the two parties not to
intersect with constant probability, implying that $\delta=\Omega(1)$. Given
this, the proof for smaller shifts follows by a union bound. While the
intuition is simple, is it not clear how to directly apply the birthday bound,
and the formal proof is based on an argument involving Minkowski sums and
differences of sets in $\mathbb{R}^{k}$.

####  1.1.3 Applications

We present several cryptographic and algorithmic applications that motivate
different variants of LPHS, exploiting both the functionality and the
sublinearity feature. All of the applications can benefit from our
2-dimensional LPHS constructions, and most require the non-cyclic, worst-case
variant. See Section 6 for a taxonomy of the LPHS variants required by
different applications.

##### Packed homomorphic secret sharing.

We demonstrate a cryptographic application of _$k$ -dimensional_ LPHS in
trading computation for communication in group-based homomorphic secret
sharing (HSS). In a nutshell, we use LPHS to further improve the succinctness
of the most succinct approach for simple “homomorphic” computations on
encrypted data, by packing 2 or more plaintexts into a single ciphertext.
Compared to competing approaches (see, e.g., [1, 37] for recent examples),
group-based packed HSS can provide much better succinctness and client
efficiency. The key technical idea is to use a non-cyclic $k$-dimensional LPHS
for implementing a $k$-dimensional variant of DDL, where $k$ independent group
generators are used for encoding $k$ small integers by a single group element,
and where multiplication by each generator is viewed as a (non-cyclic) shift
in the corresponding direction. This $k$-dimensional generalization of DDL can
be potentially useful for other recent applications of DDL that are unrelated
to HSS [26, 29, 14]. See Section 6.1 for a detailed discussion of this
cryptographic application of LPHS along with the relevant background.

##### Location-sensitive encryption.

We apply LPHS to obtain a sublinear-time solution for location-sensitive
encryption (LSE), allowing one to generate a public ciphertext that can only
be decrypted by someone in their (physical or virtual) neighborhood. Here
proximity is defined as having significantly overlapping views, and security
should be guaranteed as long as a non-overlapping view is sufficiently
unpredictable. The above goal can be reduced to realizing a sublinear-time
computable fuzzy extractor [24]333There are two differences from the standard
notion of fuzzy extractors: the “distance” is not a strict metric, and the
notion of unpredictability needs to ensure that the source is far from
periodic with high probability.  for shift distance. Obtaining such fuzzy
extractors from LPHS constructions requires an understanding of their behavior
on entropic sources. It turns out that even for high-entropy sources, an LPHS
provides no unpredictability guarantees. We get around this problem by
defining a hash function that combines the output of an LPHS with a local
function of the source. Using this approach, we obtain a sublinear-time LSE
whose security holds for a broad class of mildly unpredictable sources. See
Section 6.2 for the LSE application of LPHS.

##### Algorithmic applications.

As discussed above, algorithmic applications of LPHS follow from the vast
literature on sketching, locality-preserving and locality-sensitive hashing,
and metric embeddings. Indeed, our different LPHS flavors can be roughly
viewed as probabilistic isometric embeddings of certain shift metrics into a
Euclidean space. Thus, for example, an LSH for the same shift metric can
potentially follow by concatenating the LPHS with an LSH from the literature.
However, some care should be taken in applying this high-level approach. One
issue is the average-case nature of LPHS, which makes the failure probability
input-dependent. We get around this via a worst-case to average-case reduction
that restricts the input space to “non-pathological” inputs that are far from
periodic. Another issue is that LPHS provides no explicit guarantees for
inputs that are too far apart. We get around this by using the fact that an
LPHS must have a well-spread output distribution on a random input. As
representative examples, we demonstrate how LPHS can be applied in the
contexts of communication complexity and LSH-based near-neighbor data
structures for shifts. The algorithmic applications of LPHS are discussed in
Section 6.3.

##### Open questions.

Our work leaves several open questions. The main question, on which we make
partial progress, is obtaining optimal parameters for $k$-dimensional LPHS.
Other questions concern the optimality of the LPHS-based approach to
sketching. A negative result from [23], which can be used to rule out
sublinear-time LPHS with non-adaptive queries, in fact holds even for
sketching. Do LPHS-based sketches also provide an optimal tradeoff between
sketch size and error probability?

##### Organization.

In Section 2 we introduce necessary preliminaries and notation, including the
definition of Locality-Preserving Hash functions for Shifts (LPHS), and simple
properties of and relations between LPHS variants. In Section 3, we present
the general two-way connection between LPHS and algorithms for distributed
discrete logarithm in the generic group model. In Section 4 we provide our
results on multidimensional LPHS. Section 6 contains applications of LPHS.
And, for completeness, in Appendix A, we provide LPHS results based on the
Iterative Random Walk algorithms of Dinur, Keller, and Klein [23].

##  2 Preliminaries

We denote by $\mathbb{Z}_{n}$ the additive group of integers modulo $n$. We
will typically consider strings of length $n$ over an alphabet
$\Sigma_{b}=\left\\{0,1\right\\}^{b}$, indexing string entries by
$i\in\mathbb{Z}_{n}$. We will use the notation $x^{(b)}$ when we want to make
the alphabet size explicit. When the alphabet is binary or when $b$ is clear
from the context, we will typically omit the superscript and use the notation
$x$. For $x^{(b)}\in\Sigma_{b}^{n}$ we denote by $x^{(b)}[i]$ the $i$’th
symbol of $x^{(b)}$, for $i\in\mathbb{Z}_{n}$.

We denote by $x^{(b)}\ll r$ the cyclic rotation of $x^{(b)}$ by $r$ symbols to
the left, namely the string $y^{(b)}$ defined by $y^{(b)}[i]=x^{(b)}[i+r]$
with addition modulo $n$. We will also consider a non-cyclic shift, denoted by
$x^{(b)}\lll r$, where the $r$ leftmost symbols of $x$ are chopped and $r$
random symbols are added on the right. Note that unlike the cyclic shift
operator, which is deterministic, the non-cyclic version is randomized. We use
$\Delta(x,y)$ to denote the Hamming distance between $x$ and $y$, namely the
number of symbols $i$ in which $x[i]$ and $y[i]$ differ.

We use the notation $x^{(2,b)}$ to denote a 2-dimensional string (i.e.,
matrix) over alphabet $\Sigma_{b}$ and denote by $x^{(2,b)}[i,j]$ its $(i,j)$
entry. We denote by $x^{(2,b)}\ll(r_{1},r_{2})$ the cyclic rotation of
$y^{(2,b)}$ by $r_{1}$ symbols to the left on the first axis and $r_{2}$
symbols to the left on the second axis. That is, $y=x^{(2,b)}\ll(r_{1},r_{2})$
is defined by $y[i_{1},i_{2}]=x^{(2,b)}[i_{1}+r_{1},i_{2}+r_{2}]$, where
addition is modulo $n$. We will also consider the natural $k$-dimensional
generalization $x^{(k,b)}\ll(r_{1},r_{2},\ldots,r_{k})$ and its non-cyclic
variant $x^{(k,b)}\lll(r_{1},r_{2},\ldots,r_{k})$.

###  2.1 Locality-Preserving Hash Functions for Shifts

We now define our main notion of LPHS and some of its useful variants.

######  Definition 2.1 (LPHS: main variants).

Let ${h}\colon{\Sigma_{b}^{n}}\to{\mathbb{Z}_{n}}$ be a function. We say that
$h$ is a (cyclic) $(d,\delta)$-LPHS if $h$ can be computed by making $d$
adaptive queries (of the form $x[i]$) to an input $x\in\Sigma_{b}^{n}$ and
moreover $\Pr_{x\in_{R}\Sigma_{b}^{n}}\left[h(x)\neq h(x\ll
1)+1\right]\leq\delta$.

We will consider the following modifiers (that can be combined in a natural
way):

  * •

Non-cyclic LPHS: replace $\mathbb{Z}_{n}$ by $\mathbb{Z}$ and $x\ll 1$ by
$x\lll 1$;

  * •

$k$-dimensional LPHS: let $x$ be a random $k$-dimensional string
$x\in\Sigma_{b}^{\mathbb{Z}^{k}_{n}}$ and
${h}\colon{\Sigma_{b}^{\mathbb{Z}^{k}_{n}}}\to{\mathbb{Z}_{n}^{k}}$. We
require that $\Pr_{x}\left[h(x)\neq h(x\ll e_{i})+e_{i}\right]\leq\delta$ for
every unit vector $e_{i}\in\mathbb{Z}_{n}^{k}$.

We will sometimes make more parameters explicit in the notation. For instance,
an $(n,b,d,\delta)$-LPHS is a $(d,\delta)$-LPHS
${h}\colon{\Sigma_{b}^{n}}\to{\mathbb{Z}_{n}}$.

######  Remark (On computational complexity).

A $(d,\delta)$-LPHS ${h}\colon{\Sigma_{b}^{n}}\to{\mathbb{Z}_{n}}$ can be
viewed as a depth-$d$ decision tree over $n$ input variables taking values
from the alphabet $\Sigma_{b}$. In all of our positive results, $h$ is semi-
explicit in the sense that it can be realized by a randomized polynomial-time
algorithm having oracle access to the input $x$. (In fact, our algorithms can
be implemented in probabilistic $\tilde{O}(d)$ time.) Here the same randomness
for $h$ is used in the two invocations $h(x)$ and $h(x\ll 1)$. Alternatively,
our positive results imply a deterministic $h$ in a non-uniform setting. Our
negative results apply to the existence of $h$ with the given parameters,
irrespective of the computational complexity of generating it.

######  Remark (Worst-case vs. average-case LPHS).

Our default notions of LPHS assume a uniformly random input $x$. While this
suffices for some applications, a worst-case notion of LPHS is more desirable
for most applications. Since shift detection is impossible for highly periodic
inputs (such as the all-0 string), or even for approximately periodic in the
context of sublinear-time algorithms, the notion of worst-case LPHS is
restricted to a set of “typical” inputs that are far from being periodic. Our
notion of “typical” is very broad and arguably captures essentially all
naturally occurring inputs in our motivating applications. In Section 5 we
present a simple reduction of this worst-case flavor of LPHS to our default
notion of LPHS for random inputs. This applies both to the cyclic and non-
cyclic variants. The reduction only incurs a polylogarithmic loss in the
parameters. Note that, unlike our main notion of LPHS, here it is inherent
that the function $h$ be randomized. A useful related byproduct of the worst-
case variant is that the failure events of two independently chosen $h_{1}$
and $h_{2}$ are independent. This is useful for algorithmic applications of
LPHS.

For some applications, we will be interested in the following additional LPHS
variants.

######  Definition 2.2 (LPHS: additional variants).

We consider the following additional variants of the main notion of LPHS from
Definition 2.1.

  * •

Shift-bounded LPHS with shift bound $R$: requires that for every $1\leq r\leq
R$, we have

$\Pr_{x\in_{R}\Sigma_{b}^{n}}\left[h(x)\neq h(x\ll r)+r\right]\leq\delta,$

and similarly for the non-cyclic case.

  * •

Las Vegas LPHS: allow $h$ to output $\bot$ with probability $\leq\delta$, and
require that $h$ never fail in the event that neither of its two invocations
outputs $\bot$.

A generic way of obtaining a Las Vegas LPHS $h^{\prime}$ from an LPHS $h$ is
to invoke $h$ on both $x$ and $x^{\prime}=x\ll 1$ and output $\bot$ if
$h(x)\neq h(x^{\prime})+1$. However, an extension of this to a shift-bounded
LPHS is inefficient, since it requires invoking $h$ on $x\ll r$ for every
$0\leq r\leq R$. In Appendix A.3.3 (Lemma A.5) we show that an optimal shift-
bounded LPHS admits a Las Vegas variant with better parameters.

###  2.2 Simple LPHS Properties and Reductions

In this section we prove simple properties of LPHS and reductions between
different LPHS variants that will be useful in what follows.

The following lemma is immediate.

######  Lemma 2.3 (Conversion between non-cyclic and cyclic LPHS).

Any $k$-dimensional non-cyclic $(n,b,d,\delta)$-LPHS that queries the last
symbol $(n-1)\cdot e_{i}\in\mathbb{Z}_{n}^{k}$ in every dimension with
probability 0 gives a cyclic $(n,b,d,\,\delta)$-LPHS and vice versa.

The following lemma shows the usefulness of LPHS for detecting arbitrary shift
amounts.

######  Lemma 2.4 (Bigger shifts).

For any positive integer $r$, an $(n,b,d,\delta)$-LPHS $h$ satisfies

$\Pr_{x^{(b)}}\left[h(x^{(b)})\neq h(x^{(b)}\ll r)+r\right]\leq r\cdot\delta.$

The same holds for non-cyclic LPHS, where $x^{(b)}\ll r$ is replaced by the
string $x^{(b)}\lll r$ obtained from $x^{(b)}$ by chopping the $r$ left-most
symbols and adding $r$ uniformly random symbols to the right. In the
$k$-dimensional case, we have

$\Pr_{x^{(k,b)}}\left[h(x^{(k,b)})\neq
h(x^{(k,b)}\ll(r_{1},\ldots,r_{k}))+(r_{1},\ldots,r_{k})\right]\leq\left(\sum_{i=1}^{k}r_{i}\right)\cdot\delta.$

Proof. We give the proof for the cyclic 1-dimensional case for simplicity. The
proof for the non-cyclic and $k$-dimensional cases is similar.

$\displaystyle\Pr_{x^{(b)}}\left[h(x^{(b)})\neq h(x^{(b)}\ll r)+r\right]\leq$
$\displaystyle\Pr_{x^{(b)}}\left[\exists i\in[0,r-1]:h(x^{(b)}\ll i)\neq
h(x^{(b)}\ll i+1)+1\right]\leq$
$\displaystyle\sum_{i=0}^{r-1}\Pr_{x^{(b)}}\left[h(x^{(b)})\neq h(x^{(b)}\ll
1)+1\right]\leq r\cdot\delta.$

$\blacksquare$

As a simple corollary, we get a lower bound on the error probability of non-
cyclic LPHS.

######  Claim 2.5 (Error bound for non-cyclic LPHS).

For any non-cyclic $(n,b,d,\delta)$-LPHS we have $\delta\geq 1/(2n)$.

Proof. Suppose towards contradiction that $\delta<1/(2n)$. Applying Lemma 2.4
with $r=n$ we get that for two random and independent strings
$x,x^{\prime}\in_{R}\Sigma_{b}^{n}$ we have
$\Pr_{x,x^{\prime}}[h(x)=h(x^{\prime})+n]>1/2$, where addition is taken over
the integers. By symmetry, we also have
$\Pr_{x,x^{\prime}}[h(x^{\prime})=h(x)+n]>1/2$. Since the two events cannot
co-occur, we get a contradiction. $\blacksquare$

The above lower bound does not apply to cyclic LPHS. Indeed, when $d>n^{1/2}$
one can use discrete logarithm techniques to get cyclic LPHS in which $\delta$
is negligible in $n$. The proof of Claim 2.5 extends naturally to the
$k$-dimensional case, where we have $\delta\geq 1/(2kn)$.

The following lemma shows a simple way to trade alphabet size for input
length.

######  Lemma 2.6 (Bigger alphabet).

For any positive integer $r$ such that $n/r$ is an integer, if there exists an
$(n,b,d,\delta)$-LPHS, then there exists an $(n/r,b\cdot
r,d,r\cdot\delta)$-LPHS.

Proof. On input $x^{(b\cdot r)}$, the $(n,b\cdot r,d,\delta\cdot k)$-LPHS
(denoted by $h_{1}$) runs the $(n,b,d,\delta)$-LPHS (denoted by $h_{2}$) on
$x^{(b)}$, and outputs $\lfloor h_{2}(x^{b})/r\rfloor$. Clearly, each query of
$h_{2}$ to $x^{(b)}$ can be answered by a single query of $h_{2}$ to
$x^{(b\cdot r)}$. Based on Lemma 2.4,

$\displaystyle\Pr_{x^{(b\cdot r)}}\left[h_{1}(x^{(b\cdot r)})\neq
h_{1}(x^{(b\cdot r)}\ll 1)+1\right]\leq\Pr_{x^{(b)}}\left[h_{2}(x^{(b)})\neq
h_{2}(x^{(b)}\ll r)+r\right]\leq r\cdot\delta.$

$\blacksquare$

The following lemma can be used to decrease the alphabet size of LPHS. In
particular, it is useful for obtaining near-optimal LPHS over a binary
alphabet from LPHS over a bigger alphabet $\Sigma_{b}$, such as the one
derived directly from [23].

######  Lemma 2.7 (Smaller alphabet).

For any positive integers $r,k$, if there exists an $(n,b\cdot
r,d,\delta)$-LPHS, then there exists an $(n,b,d\cdot k,\delta+4\cdot
d^{2}/2^{b\cdot k})$-LPHS.

Proof. Given a function $f:\left\\{0,1\right\\}^{b\cdot
k}\rightarrow\left\\{0,1\right\\}^{b\cdot r}$ selected uniformly at random, on
input $x^{(b)}$, the $(n,b,d\cdot k,\delta+4\cdot d^{2}/2^{b\cdot k})$-LPHS
(denoted by $h_{1}$) runs the $(n,b\cdot r,d,\delta)$-LPHS (denoted by
$h_{2}$) and answers query $i$ by querying a $k$-tuple of elements and
applying $f(x^{(b)}[i],\ldots,x^{(b)}[i+k-1])$. Finally, it outputs the same
value as $h_{2}$.

We define the bad event $\mathcal{E}$, where two $k$-tuple queries of
$h_{1}(x^{(b)})$ or $h_{1}(x^{(b)}\ll 1)$ for $i\neq j$ satisfy
$(x^{(b)}[i],\ldots,x^{(b)}[i+k-1])=(x^{(b)}[j],\ldots,x^{(b)}[j+k-1])$.
Conditioned on $\neg\mathcal{E}$,

$\displaystyle\Pr_{x^{(b)}}\left[h_{1}(x^{(b)})\neq h_{1}(x^{(b)}\ll
1)+1\right]=\Pr_{x^{(b\cdot r)}}\left[h_{2}(x^{(b\cdot r)})\neq
h_{2}(x^{(b\cdot r)}\ll 1)+1\right]\leq\delta.$

For any $i\neq j$, the probability that
$(x^{(b)}[i],\ldots,x^{(b)}[i+k-1])=(x^{(b)}[j],\ldots,x^{(b)}[j+k-1])$ is
$2^{-b\cdot k}$, and taking a union bound on all $\binom{2d}{2}$ query pairs
of $h_{1}(x^{(b)})$ and $h_{1}(x^{(b)}\ll 1)$ gives $\Pr[\mathcal{E}]<4\cdot
d^{2}/2^{b\cdot k}$.

Note that this requires both executions of $h_{1}(x^{(b)})$ and
$h_{1}(x^{(b)}\ll 1)$ to have shared randomness. In a non-uniform setting, we
can use an averaging argument to fix this randomness and obtain a
deterministic $h$. To make $h$ semi-explicit, pick $f$ from an efficient
family of $n$-wise independent hash functions. $\blacksquare$

Next, we observe that any cyclic LPHS implies a non-cyclic LPHS with a higher
error probability $\delta$. Concretely, the error probability grows by $d/n$.
For $d=n^{1/3}$, this can yield a non-cyclic LPHS with (near-optimal)
$\delta=\tilde{O}(n^{-2/3})$. But for $n^{1/3}<d<n^{1/2}$ this generic
construction is subsumed by the direct construction from Section A.3 that can
achieve the near-optimal parameters $d=n^{1/2}$ and $\delta=\tilde{O}(1/n)$.

######  Lemma 2.8 (From cyclic to non-cyclic).

If there exists a cyclic $(n,b,d,\delta)$-LPHS, then there exists a non-cyclic
$(n,b,d,\delta+d/n)$-LPHS.

Proof. Let $h$ be a cyclic $(n,b,d,\delta)$-LPHS. We define a randomized non-
cyclic LPHS $h^{\prime}_{\rho}(x)=h(x\ll\rho)$ where
$\rho\in_{R}\mathbb{Z}_{n}$ is a uniformly random cyclic shift. Since the
difference between $x\ll 1$ and the corresponding string $x^{\prime}$ for non-
cyclic shift is restricted to the $(n-1)$-th position, after cyclically
shifting by $\rho$ the difference will be restricted to a single random
position $\rho^{*}=(n-1-\rho)\mod n$. Since $h$ (adaptively) queries $d$
symbols of its input, the probability of querying the differing position
$\rho^{*}$ is bounded by $d/n$, from which the lemma follows. $\blacksquare$

Finally, several of our results will rely on the following “smoothness”
feature of LPHS.

######  Lemma 2.9.

Let $m>1$ be a natural number. Then any $(n,b,d,\delta)$-LPHS satisfies

$\Pr_{x}[h(x)\bmod m=a]\leq m^{-1}+\delta+O(1/n)$

for every $a\in\mathbb{Z}_{m}$.

Proof. We assume that $b=1$. The proof for $b>1$ is similar.

Consider the set $S$ of inputs $x$ for which the minimal $r$ such that $x=x\ll
r$ is $n$. The set $S$ contains a fraction of $1-o(1/n)$ of the inputs
$x\in\\{0,1\\}^{n}$. Suppose first that $m$ divides $n$. Partition the set $S$
into sequences of length $m$ of the form $x,x\ll 1,\ldots,x\ll(m-1)$ and
consider the executions $h(x)\bmod m,\ldots,h(x\ll(m-1))\bmod m$. Note that if
$a$ appears $t>1$ times in an execution sequence, then $h$ must err on at
least $t-1$ inputs in this sequence. Consequently,

$\Pr_{x}[h(x)\bmod m=a]\leq m^{-1}+\delta+o(1/n).$

If $m$ does not divide $n$, then the set $S$ cannot be accurately partitioned
as above. Consequently, each set of cyclic shifts of any input $x$ (of size
$n$) in $S$ may contain at most one additional input $y$ such that $h(y)\bmod
m=a$, contributing to the additional $O(1/n)$ factor. $\blacksquare$

##  3 LPHS and Distributed Discrete Log

In this section we introduce the Generic Group Model (GGM) and Distributed
Discrete Logarithm (DDL) problem, and present a general two-way relation
between (cyclic) LPHS and generic-group algorithms for DDL. We discuss and
define the GGM and DDL problem in Section 3.1, and we provide the
correspondence with LPHS in Section 3.2.

###  3.1 Generic Group Model and Distributed Discrete Log

Our notion of LPHS is closely related to variants of the discrete logarithm
problem: given a group generator $g\in\mathrm{G}$ and a group element $g^{v}$,
find $v$. More concretely, we will be interested in algorithms for problems
related to discrete logarithm in the so-called generic group model (GGM). The
GGM assigns random labels to group elements and treats the group operation as
an oracle. We formalize this below.

Let $n$ be a positive integer parameter (corresponding to the group order) and
$b\geq 3\log n$ an integer (representation length of group elements). The GGM
setting can be described as a game, where at the beginning, a string
$x^{(b)}\in\Sigma_{b}^{n}$ is chosen uniformly at random.444We require $b\geq
3\log n$ to ensure that for each $i\neq j$, $x[i]\neq x[j]$ (except with $\leq
1/n$ probability). In the discrete log problem for $\mathbb{Z}_{n}$, a value
$v\in\mathbb{Z}_{n}$ is chosen uniformly at random. A generic algorithm $A$
for the discrete log problem in $\mathbb{Z}_{n}$ is a probabilistic algorithm
that issues $d$ (adaptive) queries of the form
$(i,j)\in\mathbb{Z}_{n}\times\mathbb{Z}_{n}$. The answer to query $(i,j)$ is
$x^{(b)}[\ell_{v}(i,j)]$, where
$\ell:\mathbb{Z}_{n}\times\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ is the
affine query evaluation function defined by $\ell_{v}(i,j)=i\cdot v+j$ (where
arithmetic operations are performed modulo $n$). Using the group notation, the
query $(i,j)$ corresponds to group element $(g^{v})^{i}\cdot g^{j}$.

The algorithm $A$ succeeds to solve the discrete log problem if
$A^{\mathrm{G}}(x^{(b)},v)=v$,555We use the notation
$A^{\mathrm{G}}(x^{(b)},v)$ to indicate that $A$ is a generic algorithm with
no direct access to the parameters $x^{(b)},v$. and its success probability is
taken over the uniform choices of $x^{(b)}$ and $v$ (and possibly additional
randomness of its own coin-tosses).

The flavor of GGM we use in this paper is similar to the one of Shoup [41].
Besides differences in notations, there are two additional technical
differences which are generally minor. First, in [41], strings are uniformly
assigned to elements of $\mathbb{Z}_{n}$ without replacement, whereas in our
model, we assign strings with replacement. However, a collision $x[i]=x[j]$
for some pair $(i,j)$ is possible with probability $\leq 1/n$, which is
negligible in our context. Second, in [41] queries of $A$ are limited to
linear combinations with coefficients of $\pm 1$ to previously queried
elements (where the initial queried elements consist of $g$ and $g^{v}$). We
note that any query $(i,j)$ can be issued in Shoup’s original GGM after at
most $O(\log n)$ queries (using the double-and-add algorithm). Therefore,
although our model is slightly stronger, any algorithm in our model can be
simulated by an algorithm in the model of [41] by increasing the query
complexity by a multiplicative factor of $O(\log n)$.

The following success probability upper bound was proved in [41].

######  Theorem 3.1 ([41], Theorem 1 (adapted)).

For a generic discrete log algorithm $A$ with $d$ queries and prime $n$, we
have $\Pr_{x^{(b)},v}[A^{\mathrm{G}}(x^{(b)},v)=v]=O(d^{2}/n)$.

Although our model is slightly different than the one of [41], this result
holds in our model as well (by a straightforward adaptation of the proof of
[41]). The assumption that $n$ is prime ensures that $\mathbb{Z}_{n}$ does not
contain any non-trivial subgroup. It is necessary in general, since for
composite $n$, the Pohlig-Hellman algorithm [38] breaks the discrete log
problem into smaller problems in subgroups of $\mathbb{Z}_{n}$, beating the
bound of Theorem 3.1.

We now define a restricted class of GGM algorithms that better correspond to
LPHS.

######  Definition 3.2.

A GGM algorithm $A$ is called query-restricted if it only issues queries of
the form $(i,j)\in\mathbb{Z}_{n}\times\mathbb{Z}_{n}$ with $i=1$.

Thus, $A$ is restricted to query group elements with a known shift $j$ from
$v$, analogously to the way an LPHS algorithm queries elements at a known
offset. Query-restricted algorithms cannot exploit the subgroup structure of
composite groups, and thus Theorem 3.1 holds for them regardless of whether
$n$ is prime. For a similar reason, the factorization of $n$ will not play any
role in our results on LPHS.

LPHS is closely related to query-restricted GGM algorithms for a variant of
discrete log called distributed discrete log (DDL) [12, 23] that we describe
next. The syntax is identical to that of discrete log. However, the goal here
is different: rather than output $v$ when the (implicit) input is $v$, the
goal here is to maintain the difference between the outputs on $v$ and $v+1$,
except with error probability $\delta$. More formally:

######  Definition 3.3.

A GGM algorithm $A$ is an $(n,b,d,\delta)$-DDL algorithm if it makes $d$
(potentially adaptive) queries to $x^{(b)}$ and
$\Pr_{x^{(b)},v}[A^{\mathrm{G}}(x^{(b)},v)-A^{\mathrm{G}}(x^{(b)},v+1)\neq
1]\leq\delta$.

######  Remark.

The original definition of DDL in [12] involves two parties $A$ and $B$ that
may potentially run two different algorithms. The parties are placed within an
unknown distance $r\in\\{-1,0,1\\}$ from each other and their goal is to
minimize the error probability defined as
$\Pr_{x^{(b)},v}[A^{\mathrm{G}}(x^{(b)},v)-B^{\mathrm{G}}(x^{(b)},v+r)\neq
r].$ However, it was shown in [23, Lemma 9], that if both parties use $A$’s
algorithm, then the multiplicative loss in error probability is bounded by a
constant. Hence, the above restricted definition of DDL is essentially
equivalent to the original one of [12].

While LPHS is only directly related to query-restricted GGM algorithms for
DDL, Lemma 3.7 asserts that when $n$ is prime and $d$ is sufficiently small
compared to $n$, any unrestricted GGM algorithm for DDL can be converted to a
query-restricted one at a negligible cost in error probability. This gives
rise to Corollary 3.8 that establishes a reduction which converts any
unrestricted GGM algorithm for DDL to an LPHS with a negligible cost in error
probability.

###  3.2 Reductions Between LPHS Variants and DDL

In this section we show that a query-restricted DDL algorithm in the GGM is
equivalent to our basic notion of (cyclic) LPHS, and then describe
consequences of this equivalence. We then show that for most parameters, any
DDL algorithm can be converted into a query-restricted one at a negligible
cost.

We use this correspondence to derive asymptotically tight bounds on the
parameters of LPHS, using the Iterative Random Walk algorithm from [23].

##### Equivalence of LPHS and query-restricted DDL.

The equivalence in the query-restricted model is formally captured by the
following two-way relation.

######  Lemma 3.4.

There exist reductions that convert an $(n,b,d,\delta)$-LPHS to a query-
restricted $(n,b,d,\delta)$-DDLA and vice versa.

Proof. Given access to an $(n,b,d,\delta)$-LPHS denoted by $h$, we construct a
query-restricted $(n,b,d,\delta)$-DDLA, denoted by $A$ as follows. We run $h$
and translate query $j$ into query $(1,j)$ for $A^{\mathrm{G}}(x^{(b)},v)$. We
then feed the answer $x^{(b)}[v+j]$ to $h$. Finally, we output the same value
as $h$. Since $x^{(b)}[v+j]=(x^{(b)}\ll v)[j]$, we have
$A^{\mathrm{G}}(x^{(b)},v)=h(x^{(b)}\ll v)$, where $x^{(b)}\ll v$ is a uniform
string. Therefore,

$\displaystyle\Pr_{x^{(b)},v}[A^{\mathrm{G}}(x^{(b)},v)-A^{\mathrm{G}}(x^{(b)},v+1)\neq
1]=$ $\displaystyle\Pr_{x^{(b)},v}[h(x^{(b)}\ll v)-h(x^{(b)}\ll v+1)\neq 1]=$
$\displaystyle\Pr_{x^{(b)}}[h(x^{(b)})-h(x^{(b)}\ll 1)\neq 1]=\delta.$

In a similar way, a query-restricted $(n,b,d,\delta)$-DDLA can be used to
construct a $(n,b,d,\delta)$-LPHS. $\blacksquare$

The DDL algorithm based on the Iterated Random Walk (IRW) from [23] is query-
restricted. Therefore, combining Lemma 3.4 with the parameters of IRW, we get
the positive result below for cyclic LPHS. The result for non-cyclic LPHS
follows from the fact that the random walk makes queries within an interval of
size bounded by $O(d^{2})$, hence if $n=\Omega(d^{2})$ is large enough, the
LPHS gives both cyclic and non-cyclic LPHS with the same parameters.

######  Theorem 3.5 (LPHS Upper Bounds).

For $n=\Omega(d^{2})$ and $b\geq 3\log n$ there is an $(n,b,d,\delta)$-LPHS
such that $\delta=O(1/d^{2})$. Moreover, for $n=\Omega(d^{2})$ and any $b\geq
1$ there is an $(n,b,d,\delta)$-LPHS with $\delta=\tilde{O}(1/d^{2})$. There
are also non-cyclic LPHS with the same parameters.

We can similarly convert the main negative result for DDLA from [23, Theorem
5] to a nearly tight lower bound on the error probability of LPHS.

######  Theorem 3.6 (LPHS Lower Bound).

For $n=\Omega(d^{2})$, any (cyclic or non-cyclic) $(n,1,d,\delta)$-LPHS
satisfies $\delta\geq\Omega(1/d^{2})$.

##### From GGM to query-restricted GGM.

In this section we show that, when $n$ is prime and $d$ is sufficiently small
compared to $n$, any DDL algorithm can be converted into a query-restricted
one with similar parameters.

######  Lemma 3.7.

For $b\geq 3\log b$, there exists a reduction that converts any
$(n,b,d,\delta)$-DDLA, for prime $n$, to a query-restricted
$(n,b,d,\delta+O(d^{2}/n))$-DDLA.

If $d=O(n^{1/4})$, then since $\delta=\Omega(d^{-2})$ by Theorem 3.6, we have
$\delta+O(d^{2}/n)=\delta+O(d^{-2})=O(\delta)$. Hence the reduction is almost
without loss.

Proof. (sketch) Given black-box access to an $(n,b,d,\delta)$-DDLA denoted by
$A$, we construct a query-restricted $(n,b,d,\delta+O(d^{2}/n))$-DDLA, denoted
by $B$. We will define a query mapping
$map:\mathbb{Z}_{n}\times\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ below and
run $A$, while translating query $(i,j)$ into query $(1,map(i,j))$ for
$B^{\mathrm{G}}(x^{(b)},v)$ for which the answer $x^{(b)}[v+map(i,j)]$ is fed
back into $A$. Finally, we output the same value as $A$.

Our goal in defining $map$ is to simulate the joint distribution of query
answers for $A^{\mathrm{G}}(y^{(b)},v)$ and $A^{\mathrm{G}}(y^{(b)},v+1)$ (for
uniform $y^{(b)},v$), while making only restricted queries. The simulation
will be perfect unless some bad event (which happens with probability
$O(d^{2}/n)$) occurs. This will assure that the error probability of $h$ is
bounded by $\delta+O(d^{2}/n)$.

The query answers of $A^{\mathrm{G}}(y^{(b)},v)$ and
$A^{\mathrm{G}}(y^{(b)},v+1)$ are uniform in $\Sigma_{b}$, unless they query
the same element, namely,
$\ell_{v+a_{0}}(i,j)=\ell_{v+a_{1}}(i^{\prime},j^{\prime})$ for
$i,j,i^{\prime},j^{\prime}\in\mathbb{Z}_{n}$ and $a_{0},a_{1}\in\\{0,1\\}$. We
thus require that the mapping preserves equality, namely,

$\displaystyle\ell_{v+a_{0}}(i,j)=\ell_{v+a_{1}}(i^{\prime},j^{\prime})\Leftrightarrow\ell_{v+a_{0}}(1,map(i,j))=\ell_{v+a_{1}}(1,map(i^{\prime},j^{\prime})).$
(1)

Considering the left-hand side, if $i\neq i^{\prime}$, then the discrete log
$v$ can be computed (e.g., for $a_{0}=a_{1}=0$,
$v=(j^{\prime}-j)\cdot(i-i^{\prime})^{-1}$). We refer to this first bad event
as a collision, and can bound its probability by $O(d^{2}/n)$ using Theorem
3.1. Hence, the analysis will assume that if
$\ell_{v+a_{0}}(i,j)=\ell_{v+a_{1}}(i^{\prime},j^{\prime})$, then
$i=i^{\prime}$.

The second bad event is that
$\ell_{v+a_{0}}(1,map(i,j))=\ell_{v+a_{1}}(1,map(i^{\prime},j^{\prime}))$, but
$\ell_{v+a_{0}}(i,j)\neq\ell_{v+a_{1}}(i^{\prime},j^{\prime})$. The
probability of this event will be bounded by $O(d^{2}/n)$ below.

In order to define $map$,666This mapping was defined in a slightly different
context in [23]. assume that we fix elements $D_{0},D_{1},\ldots,D_{n-1}$,
where $D_{i}\in\mathbb{Z}_{n}$. We set

$map(i,j)=\begin{cases}D_{i}+j\cdot i^{-1},&\text{if }i\neq 0\\\
D_{i}+j,&\text{otherwise},\end{cases}$

where $i^{-1}$ is the multiplicative inverse of $i$ modulo $n$.

Observe that for $i\neq 0$, if $\ell_{v}(i,j)=\ell_{v+1}(i,j^{\prime})$, then
$j=j^{\prime}+i$ implying that

$\ell_{v}(1,map(i,j))=v+D_{i}+j\cdot i^{-1}=v+D_{i}+(j^{\prime}+i)\cdot
i^{-1}=v+1+D_{i}+j^{\prime}\cdot i^{-1}=\ell_{v+1}(1,map(i,j^{\prime})),$

and the same equality holds for $i=0$. Hence, assuming no collision, the first
(right) part of Equation (1) holds for $a_{0}\neq a_{1}$ (it also holds
trivially for $a_{0}=a_{1}$).

For the second part, observe that if
$\ell_{v+a_{0}}(1,map(i,j))=\ell_{v+a_{1}}(1,map(i^{\prime},j^{\prime})$ for
$i,i^{\prime}\neq 0$, then $v+a_{0}+D_{i}+j\cdot
i^{-1}=v+a_{1}+D_{i^{\prime}}+j^{\prime}\cdot(i^{\prime})^{-1}$. If
$i=i^{\prime}$, we get $i\cdot a_{0}+j=i\cdot a_{1}+j^{\prime}$. Hence,

$\ell_{v+a_{0}}(i,j)=i\cdot(v+a_{0})+j=i\cdot(v+a_{1})+j^{\prime}=\ell_{v+a_{1}}(i,j^{\prime}),$

as required (a similar equality holds when $i=i^{\prime}=0$). When $i\neq
i^{\prime}$, we get a second bad event and we choose each
$D_{i}\in\mathbb{Z}_{n}$ uniformly at random to bound its probability (for any
specific $a_{0},i,j,a_{1},i^{\prime},j^{\prime}$) by $1/n$. Summing over all
$\binom{2d}{2}$ query pairs of $B^{\mathrm{G}}(x^{(b)},v)$ and
$B^{\mathrm{G}}(x^{(b)},v+1)$, we bound the probability of the second bad
event by $O(d^{2}/n)$.

Note that this requires both executions of $B^{\mathrm{G}}(x^{(b)},v)$ and
$B^{\mathrm{G}}(x^{(b)},v+1)$ to have shared randomness. However, this
requirement can be removed since our model is non-uniform, and
$D_{i}\in\mathbb{Z}_{n}$ can be fixed by a standard averaging argument.
$\blacksquare$

Combined with Lemma 3.4, we obtain the following corollary.

######  Corollary 3.8.

For $b\geq 3\log b$, there exists a reduction that converts any
$(n,b,d,\delta)$-DDLA, for prime $n$, to an $(n,b,d,\delta+O(d^{2}/n))$-LPHS.

##  4 Multidimensional LPHS

In this section we study the $k$–dimensional generalization of LPHS, focusing
mainly on the case $k=2$ (2D-LPHS). First, in Section 4.1, we consider the
upper bound side. We start with simple constructions achieving error
$\delta=\tilde{O}(d^{-1/2})$ (Section 4.1.1) and $\delta=\tilde{O}(d^{-4/5})$
(Section 4.1.2). The latter makes a black-box use of the 1-dimensional IRW
algorithm of [23]. More concretely, for $n=\Omega(d^{6/5})$, any $b\geq 3\log
n$ and any $(r_{1},r_{2})\in\\{0,1\\}\times\\{0,1\\}$, we have

$\Pr_{x\in_{R}\Sigma_{b}^{\mathbb{Z}_{n}\times\mathbb{Z}_{n}}}\left[h(x)-h(x\ll(r_{1},r_{2}))\neq(r_{1},r_{2})\right]=O(d^{-4/5}).$
(2)

Since our construction only makes queries in a limited box of dimensions
$O(d^{6/5})\times O(d^{4/5})$ while $n=\Omega(d^{6/5})$, it gives both a
cyclic and a non-cyclic LPHS with the same parameters.

This proves a weak version of Theorem 1.3. In Section 4.1.3 we obtain the
improved upper bound of Theorem 1.3 by presenting a more intricate algorithm
that achieves error rate of $\delta=\tilde{O}(d^{-7/8})$. Finally, in Section
4.1.4 we present a heuristic algorithm that we conjecture to achieve the near-
optimal error probability of $\delta=\tilde{O}(d^{-1})$. This conjecture is
supported by experimental evidence.

In Section 4.2 we study limitations of $k$-dimensional LPHS. We prove Theorem
1.4, which for $k=2$ implies that the error probability of a 2D-LPHS must
satisfy $\delta=\tilde{\Omega}(d^{-1})$.

###  4.1 Upper bounds on 2D-LPHS algorithms

We present and analyze 2D-LPHS algorithms achieving error
$\delta=\tilde{O}(d^{-1/2}),\tilde{O}(d^{-4/5}),\tilde{O}(d^{-7/8})$,
respectively, as well as a heuristic algorithm conjectured to achieve optimal
error $\delta=\tilde{O}(d^{-1})$.

####  4.1.1 A simple 2D-LPHS with error rate $\delta=O(d^{-1/2})$

We begin by describing a very simple 2D-LPHS algorithm called Min-Hash.

Notation All integer operations in algorithms within this section are assumed
to be floored. For example, we write $x/y$ for $\lfloor x/y\rfloor$ and
$\sqrt{n}$ for $\lfloor\sqrt{n}\rfloor$.

1begin

2 return $\mathrm{arg\,min}_{i,j\in[0,\sqrt{d}]}\\{x[i,j]\\}$

3 end

4

Algorithm 1 Min-Hash$(x\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d\in\mathbb{N})$

The following lemma captures the performance of Min-Hash.

######  Lemma 4.1.

For $n=\Omega(d^{1/2})$ and any $b\geq 3\log n$ and
$(r_{1},r_{2})\in\\{0,1\\}\times\\{0,1\\}$,

$\Pr\left[\textsc{Min-Hash}(x,d)-\textsc{Min-
Hash}(x\ll(r_{1},r_{2}),d)\neq(r_{1},r_{2})\right]=O(d^{-1/2}).$ (3)

Proof. Notice that no matter what the values of $r_{1},r_{2}\in\\{0,1\\}$ are,
both applications of Min-Hash on $x$ and $y$ query the values
$G=\\{x[i,j]\\}_{i,j\in[1,\sqrt{d}]}$, together with some other $2\sqrt{d}-1$
values. Hence $\textsc{Min-Hash}(x,d)$ and $\textsc{Min-Hash}(y,d)$ together
read at most $4\sqrt{d}$ values outside of $G$. Under the uniformity
assumption of $x$, the probability the minimum of all the symbols read by the
two applications of Min-Hash is not in $G$, is bounded by
$4\sqrt{d}/d=O(1/\sqrt{d})$. Hence, assuming that the minimum $x[i_{0},j_{0}]$
is in $G$, and that this minimum is unique, we have

$\begin{gathered}\textsc{Min-Hash}(x,d)=(i_{0},j_{0}).\\\ \textsc{Min-
Hash}(y,d)=\mathrm{arg\,min}_{i,j\in[0,\sqrt{d}]}\\{x[i+r_{1},j+r_{2})\\}=(i_{0}-r_{1},j_{0}-r_{2}),\end{gathered}$

in which case, $\textsc{Min-Hash}(x,d)-\textsc{Min-Hash}(y,d)=(r_{1},r_{2})$.

The only thing left for the proof is showing that with a very high
probability, the minimum of Algorithm 1 is uniquely attained. It can be easily
verified (e.g., by induction on $d$) that the probability that the minimum is
not unique, is upper bounded by $d/2^{b}$. Under the assumption $b\geq
3/2\lg(d)$, this probability is dominated by the $O(1/\sqrt{d})$ error in (3).
$\blacksquare$

####  4.1.2 An IRW-based 2D-LPHS with error rate $\delta=O(d^{-4/5})$

In this subsection we demonstrate how an 1D-LPHS may be used in order to
construct a 2D-LPHS with $\delta=O(d^{-4/5})$. Let us recall the functionality
of an optimal 1D-LPHS (see Theorem 3.5).

Optimal 1D-LPHS, rephrased. For $b\geq 3\log n$, there exists an algorithm
$\textsc{optimal1D}\colon\Sigma_{b}^{\mathbb{Z}_{n}}\times\mathbb{Z}\to\mathbb{Z}_{n}$
with the following properties. If $n=\Omega(d^{2})$, then

$\Pr_{x\sim\Sigma_{b}^{\mathbb{Z}_{n}}}[\textsc{optimal1D}(x,d)-\textsc{optimal1D}(x\ll
1,d)\neq 1]<O(1/d^{2}).$

The 2D-LPHS is described in the Recursive-Hash algorithm (Algorithm 3). The
algorithm works in two stages, first returning a column $i_{1}$ and then a row
$j_{1}$. Namely, the parties first try to synchronize on a column via a random
walk along their input rows, and then try to synchronize on a row via a random
walk along this common column.

Specifically, the column $i_{1}$ is located by a walk along the fixed input
row. The walk uses the optimal1D algorithm with $d/d^{\prime}-1$ queries (for
a parameter $d^{\prime}$). A query in this algorithm on any column $i_{0}$ is
answered by the rec1D algorithm, which executes optimal1D with $d^{\prime}$
queries on column $i_{0}$.

After the column $i_{1}$ is returned, the Recursive-Hash algorithm runs the
optimal1D algorithm along this column, starting from the input row to return
the output row $j_{1}$.

1begin

2 Define $u\in\Sigma_{b}^{\mathbb{Z}_{n}}$ by $u[j]\leftarrow z[i_{0},j]$

3 $j_{0}\leftarrow\textsc{optimal1D}(u,d^{\prime})$

4 return $z[i_{0},j_{0}+10d^{\prime 2}]$

5 end

6

Algorithm 2
rec1D$(z\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d^{\prime}\in\mathbb{N},i_{0}\in\mathbb{Z}_{n})$

1begin

2
$i_{1}\leftarrow\textsc{optimal1D}(i\mapsto\textsc{rec1D}(z,d^{3/5}-1,i),d^{2/5})$

3 $j_{1}\leftarrow\textsc{optimal1D}(j\mapsto z[i_{1},j],d^{2/5})$

4 return $(i_{1},j_{1})$

5 end

6

Algorithm 3 Recursive-
Hash$(z\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d\in\mathbb{N})$

######  Lemma 4.2.

For $n=\Omega(d^{6/5})$ and any $b\geq 3\log n$ and
$(r_{1},r_{2})\in\\{0,1\\}\times\\{0,1\\}$,

$\Pr\left[\textsc{Rec2D}(x,d)-\textsc{Rec2D}(x\ll(r_{1},r_{2}),d)\neq(r_{1},r_{2})\right]=O(d^{-4/5}).$

Proof. First, notice $\textsc{Recursive-Hash}(x,d)$ makes at most $d$ queries
to $x$. This is because all but $d^{2/5}$ queries are made inside rec1D. This
procedure is called at most $d^{2/5}$ times, and queries $u$ at most
$d^{3/5}-1$ times, which in turn makes exactly one query to $x$.

Second, denoting $y=x\ll(r_{1},r_{2})$, notice that since $r_{1}\in\\{0,1\\}$,
we have from Theorem 3.5,

$\Pr\left[\textsc{rec1D}(x,d^{3/5}-1,i+r_{1})\neq\textsc{rec1D}(y,d^{3/5}-1,i)\right]\leq
O(d^{-6/5}).$

Since Recursive-Hash makes at most $d^{2/5}$ calls to rec1D, then except for
probability $O(d^{-6/5}\cdot d^{2/5})=O(d^{-4/5})$, we have
$\textsc{rec1D}(x,d^{3/5},i+r_{1})=\textsc{rec1D}(y,d^{3/5},i)$ for all $i$’s
such that both sides were computed in $\textsc{Recursive-Hash}(x,d)$ and
$\textsc{Recursive-Hash}(y,d)$, respectively. If the output of
$\textsc{rec1D}(x,d^{3/5},i)$ would be uniformly distributed in $\Sigma_{b}$
(and independent of all other queries), Theorem 3.5 would imply
$i_{1}^{x}+r_{1}=i_{1}^{y}$ except for probability $O(d^{-4/5})$, where
$i_{1}^{z}$ is the value of $i_{1}$ computed during $\textsc{Recursive-
Hash}(z,d)$, and $z\in\\{x,y\\}$. Similarly, $j_{1}$ is synchronized except
for probability $O(d^{-4/5})$. In conclusion, the total error probability of
the algorithm is $O(d^{-4/5})$. Finally, $x[i_{0},j_{0}+10d^{\prime 2}]$ is
indeed uniformly distributed in $\Sigma_{b}$ independently of all other
queries, as optimal1D does not query that value. $\blacksquare$

####  4.1.3 3-Stage-Hash: a 2D-LPHS algorithm with
$\delta=\tilde{O}(d^{-7/8})$

In this subsection we prove Theorem 1.3, by presenting the algorithm 3-Stage-
Hash which achieves error rate of $\delta=\tilde{O}(d^{-7/8})$. 3-Stage-Hash
is composed of 3 stages. The first is Min-Hash and we refer to the other two
as stage2 and stage3.

1begin

2 $(i_{0},j_{0})\leftarrow\textsc{Min-Hash}(z,\ d/3)$

3 $(i_{1},j_{1})\leftarrow\textsc{stage2}(z,\ d/3,\ i_{0}+2\sqrt{d},\
j_{0}+2\sqrt{d})$

4 $(i_{2},j_{2})\leftarrow\textsc{stage3}(z,\ d/3,\ i_{1}+2d^{3/4},\
j_{1}+2d^{3/4})$

5 return $(i_{2},j_{2})$

6 end

7

Algorithm 4 3-Stage-Hash$(z\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d\in\mathbb{N})$

1 begin

2 $L\leftarrow\sqrt[4]{d^{\prime}}$

3 Let $\psi_{1},\psi_{2}\colon\Sigma_{b}\to\mathbb{Z}_{L}$ be $\psi_{1}(t)=t\
\mathrm{mod}\,L$ and $\psi_{2}(t)=\lfloor t/L\rfloor\ \mathrm{mod}\,L$

4 $P,P^{\prime}\leftarrow\emptyset,\emptyset$

5 $i\leftarrow i_{0}$

6 for  _$s=1$ to $\sqrt{d^{\prime}}$_ do

7 $j\leftarrow j_{0}$

8 for  _$t=1$ to $\sqrt{d^{\prime}}$_ do

9 $P^{\prime}\leftarrow P^{\prime}\cup\\{(i,j)\\}$

10 $j\leftarrow j+1+\psi_{1}(z[i,j])$

11 end for

12 $i\leftarrow i+1+\psi_{2}(\min_{p^{\prime}\in
P^{\prime}}\\{z[p^{\prime}]\\})$

13 $P,P^{\prime}\leftarrow P\cup P^{\prime},\emptyset$

14 end for

15 return $\mathrm{arg\,min}_{p\in P}\\{z[p]\\}$

16 end

17

Algorithm 5
stage2$(z\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d^{\prime}\in\mathbb{N},i_{0}\in\mathbb{Z}_{n},j_{0}\in\mathbb{Z}_{n})$

1begin

2 Let $\psi\colon\Sigma_{b}\to\\{-d^{\prime 3/8},\ldots,d^{\prime 3/8}\\}$ be
$\psi(t)=(t\ \mathrm{mod}\,(2d^{\prime 3/8}+1))-d^{\prime 3/8}$

3 $P\leftarrow\emptyset$

4 $(i,j)\leftarrow(i_{0},j_{0})$

5 for  _$s=1$ to $d^{\prime}$_ do

6 $P\leftarrow P\cup\\{(i,j)\\}$

7 $(i,j)\leftarrow(i+1,j+\psi(z[i,j]))$

8 end for

9 return $\mathrm{arg\,min}_{p\in P}\\{z[p]\\}$

10 end

11

Algorithm 6
stage3$(z\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d^{\prime}\in\mathbb{N},i_{0}\in\mathbb{Z}_{n},j_{0}\in\mathbb{Z}_{n})$

######  Lemma 4.3.

Let $2^{b}\geq d^{4}$, $n\geq\Omega(d)$, and $r_{1},r_{2}\in\\{0,1\\}$. Then,

$\Pr\left[\textsc{3-Stage-Hash}(x,d)-\textsc{3-Stage-
Hash}(y,d)\neq(r_{1},r_{2})\right]<O(d^{-7/8}),$ (4)

In order to prove Lemma 4.3, we need the following facts, which we prove
later.

######  Lemma 4.4.

Let $S_{1},S_{2},\ldots$ be a sequence of i.i.d. geometric random variables:
$S_{i}\sim\mathrm{Geom}(p)$. If $K$ is the minimal integer with
$\sum_{k=1}^{K}S_{k}\geq r$, then $\operatorname*{\mathbb{E}}[K]\leq rp+1$.

######  Lemma 4.5.

Let $I_{0},I_{1},I_{2},\ldots$ be a random walk with $I_{k+1}-I_{k}$ being
i.i.d. variables distributed as the difference of two independent random
variables uniformly distributed in $\\{0,1,\ldots,m\\}$, with
$m\in\mathbb{N}$. If $T$ is the minimal time with $I_{T}=0$, then
$\operatorname*{\mathbb{E}}[\min(T,r)]\leq
O\left((m+|I_{0}|/m)\sqrt{r}\right)$.

Given these facts, we turn to Lemma 4.3.

Proof (of Lemma 4.3, sketch). Let $(i_{k}^{z},j_{k}^{z})$ be the values
computed as $(i_{k},j_{k})$ at $\textsc{3-Stage-Hash}(z,d)$, for
$k\in\\{0,1,2\\}$ and $z\in\\{x,y\\}$. We say that $(i_{k}^{x},j_{k}^{x})$ and
$(i_{k}^{y},j_{k}^{y})$ are synchronized if
$(i_{k}^{x},j_{k}^{x})-(i_{k}^{y},j_{k}^{y})=(r_{1},r_{2})$. Observe that if
$(i_{k}^{x},j_{k}^{x})$ and $(i_{k}^{y},j_{k}^{y})$ are synchronized, then so
are $(i_{k+1}^{x},j_{k+1}^{x})$ and $(i_{k+1}^{y},j_{k+1}^{y})$. This is
because each stage $k+1$ of $\textsc{3-Stage-Hash}(z,d)$ deterministically
depends on values queried from $z$ with offset $(i_{k}^{z},j_{k}^{z})$, so
that evaluations keep being aligned. Overall,

$\displaystyle\begin{split}\delta\doteqdot&\Pr_{x,y,r_{1},r_{2}}[\textsc{3-Stage-
Hash}(x,d)-\textsc{3-Stage-Hash}(y,d)\neq(r_{1},r_{2})]\\\
&\leq\Pr[(i_{0}^{x},j_{0}^{x})-(i_{0}^{y},j_{0}^{y})\neq(r_{1},r_{2})]\cdot\\\
&\cdot\prod_{k=1}^{2}\Pr\left[(i_{k}^{x},j_{k}^{x})-(i_{k}^{y},j_{k}^{y})\neq(r_{1},r_{2})\,\middle|\,(i_{k-1}^{x},j_{k-1}^{x})-(i_{k-1}^{y},j_{k-1}^{y})\neq(r_{1},r_{2})\right].\end{split}$
(5)

Hence, to bound $\delta$ it is sufficient to verify the following three
claims:

  1. 1.

$\Pr[(i_{0}^{x},j_{0}^{x})-(i_{0}^{y},j_{0}^{y})\neq(r_{1},r_{2})]\leq
O(1/\sqrt{d})$.

  2. 2.

$\Pr\left[(i_{1}^{x},j_{1}^{x})-(i_{1}^{y},j_{1}^{y})\neq(r_{1},r_{2})\,\middle|\,(i_{0}^{x},j_{0}^{x})-(i_{0}^{y},j_{0}^{y})\neq(r_{1},r_{2})\right]\leq
O(1/\sqrt[4]{d})$.

  3. 3.

$\Pr\left[(i_{2}^{x},j_{2}^{x})-(i_{2}^{y},j_{2}^{y})\neq(r_{1},r_{2})\,\middle|\,(i_{1}^{x},j_{1}^{x})-(i_{1}^{y},j_{1}^{y})\neq(r_{1},r_{2})\right]\leq
O(1/\sqrt[8]{d})$.

Claim 1) Follows from Lemma 4.1.

Claim 2) Since $\textsc{Min-Hash}(z,d)$ scans a $\sqrt{d}\times\sqrt{d}$ area
and outputs a point inside it, we are guaranteed that
$|i_{0}^{x}-i_{0}^{y}|\leq\sqrt{d}+1$ and
$|j_{0}^{x}-j_{0}^{y}|\leq\sqrt{d}+1$. Because stage2 is fed with the output
point of Min-Hash shifted by $2\sqrt{d}$ in each axis, its queries do not
overlap these of Min-Hash, and its performance is independent of the Min-Hash
phase. Moreover, stage2 can be modeled as a random walk on the $i$ axis, whose
steps are integers uniformly distributed in $[1,\sqrt{d^{\prime}}]$ (with
$d^{\prime}=d/3$, as in stage2), which are determined by some random walk on
the $j$ axis. Denote by $I_{1}^{x},\ldots,I_{\sqrt{d^{\prime}}}^{x}$ and
$I_{1}^{y},\ldots,I_{\sqrt{d^{\prime}}}^{y}$ the sequences of $i$’s observed
by stage2 applied on $x$ and on $y$.

In order to compute the probability that the outputs of
$\textsc{stage2}(x,d^{\prime})$ and $\textsc{stage2}(y,d^{\prime})$ are not
synchronized, it is sufficient (following the proof of Lemma 4.1) to count the
number of queries that the two processes make, which are not shared. These
queries can be classified into two categories: queries with non-shared $i$,
and queries with shared $i$ and non-shared $j$. Our goal is to show each class
contains on average $O(d^{\prime 3/4})$ such queries, implying that the
probability of the outputs not being synchronized is $O(d^{\prime
3/4}/d^{\prime})$ (similarly to Lemma 4.1). We start by reasoning about the
first class of queries, and then proceed to the second.

Let $U_{1}$ denote the total number of $i$-steps until $i^{x}$ and $i^{y}$ are
synchronized (i.e. $U_{1}=k+k^{\prime}$ when $k,k^{\prime}$ are minimal with
$I_{k}^{x}-I_{k^{\prime}}^{y}=r_{1}$). Up to this point, the two stage2
applications act independently, as their queries do not overlap. Using [23,
Lemmas 3,5] with $b\leq\sqrt{d}+1$ and $L=\sqrt[4]{d^{\prime}}$ we see
$\operatorname*{\mathbb{E}}[U_{1}]\leq O(d^{1/4})$. Next, we note that once
$I_{k}^{x}-I_{k^{\prime}}^{y}=r_{1}$, it is likely that
$I_{k+1}^{x}-I_{k^{\prime}+1}^{y}=r_{1}$. Specifically, we will show

$\Pr\left[I_{k+1}^{x}-I_{k^{\prime}+1}^{y}\neq
r_{1}\,\middle|\,I_{k}^{x}-I_{k^{\prime}}^{y}=r_{1}\right]\leq O(1/\sqrt{d}).$

Assuming this, the two walks make $U_{1}$ unsynchronized steps, then $S_{1}$
synchronized steps with $S_{1}\sim\mathrm{Geom}(O(1/\sqrt{d}))$ distributed
geometrically. The walks then make another $U_{2}$ unsynchronized steps, with
[23, Lemma 5] yielding $\operatorname*{\mathbb{E}}[U_{2}]\leq O(d^{1/4})$,
followed by $S_{2}$ synchronized steps with
$S_{2}\sim\mathrm{Geom}(O(1/\sqrt{d}))$. The process continues this way until
one of the walks has completed its $\sqrt{d^{\prime}}$ steps. Using Lemma 4.4,
the expected number of such phases of synchronization-unsychronization is
$\leq O(\sqrt{d^{\prime}}\cdot\sqrt{1/d}+1)=O(1)$. Combining this with the
fact that $\operatorname*{\mathbb{E}}[U_{k}]=O(d^{1/4})$, we deduce that the
expected number of unsynchronized $i$-steps is $O(d^{1/4})$. Each such step
involves $\sqrt{d^{\prime}}$ $j$-steps, so the total number of queries with
non-shared $i$ is $O(d^{3/4})$.

Regarding the steps with shared $i$ and non-shared $j$, random-walk arguments
similar to the above argument imply that since on each shared $i$, the two
$j$-walks start with distance $O(\sqrt{d})$, and have steps of size
$\Theta(d^{1/4})$, they are expected to meet after $O(d^{1/4})$ queries
(follows from [23, Lemmas 3,5]). Since there are $O(\sqrt{d})$ $i$-steps, the
total number of non-shared such queries is $O(d^{3/4})$ as well.

Claim 3) Similarly to the previous claim, the queries made by stages before
stage3 are confined to a square area of size
$(d^{3/4}+3\sqrt{d})\times(d^{3/4}+3\sqrt{d})$, and since the input is shifted
by $2d^{3/4}$, the queries of stage3 do not overlap previous stages. Note that
the queries made by stage3 are confined to a $2d\times 2d$ square except for a
negligibly small error prbobability ($\exp(-\Omega(d^{1/4}))$) due to
Hoeffding’s inequality, and since $n\geq\Omega(d)$ (recall
$x,y\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}}$), the queries of the different stages
do not overlap (with high probability) even though the index space of $x,y$ is
cyclic.

It is clear that once the two walks of stage3 on $x$ and on $y$ are
synchronized, they remain synchronized. Let $T$ be the total number of steps
until the two walks share a point. There are at most $\min(2T,d^{\prime})$
steps which are not shared, and the failure probability is
$\leq\min(2T,d^{\prime})/d^{\prime}$, similarly to the proof of Lemma 4.1.
Thus, it is sufficient to verify $\operatorname*{\mathbb{E}}[\min(T,d)]\leq
d^{7/8}$. Clearly, after $|i_{1}^{x}-i_{1}^{y}|$ steps, the walks are being
synchronized with respect to the $i$-axis. Let $J$ denote the random variable
measuring their distance on the $j$-axis, once the walks first share this same
$i$. Since each of the advances of $j$ are independent of the other steps,

$\operatorname*{\mathbb{E}}[J^{2}]=|j_{1}^{x}-j_{1}^{y}|^{2}+\sum_{t=0}^{|i_{1}^{x}-i_{1}^{y}|}\operatorname*{\mathbb{E}}[S_{t}^{2}],$

where $S_{t}$ is the jump on the $j$-axis on the $t$-step of the runner-up
walk. In particular
$\operatorname*{\mathbb{E}}[S_{t}^{2}]\leq((d/3)^{3/8})^{2}\leq d^{3/4}$.
Since $|i_{1}^{x}-i_{1}^{y}|\leq 2d^{3/4}$, we overall deduce
$\operatorname*{\mathbb{E}}[J^{2}]\leq O(d^{3/2})$.

From this point on, the walks of $\textsc{stage3}(x,d^{\prime})$ and
$\textsc{stage3}(y,d^{\prime})$ keep being aligned with respect to the
$i$-axis. Once they meet on the $j$-axis, they will remain synchronized. The
distance on the $j$-axis between the walks can be modeled as a one dimensional
random walk, starting at $J$, and having independent steps whose lengths are a
difference of two independent variables uniformly distributed in
$\\{0,1,\ldots,2d^{\prime 3/8}\\}$. Once this difference walk hits $0$, the
walks keep being synchronized. Lemma 4.5 then immediately yields

$\operatorname*{\mathbb{E}}[\min(T,d^{\prime})]\leq|i_{1}^{x}-i_{1}^{y}|+O\left((d^{\prime
3/8}+\operatorname*{\mathbb{E}}|J|/d^{\prime 3/8})\sqrt{d^{\prime}}\right).$

Substituting
$\operatorname*{\mathbb{E}}[J]^{2}\leq\operatorname*{\mathbb{E}}[J^{2}]=O(d^{3/2})$,
we obtain $\operatorname*{\mathbb{E}}[\min(T,d^{\prime})]\leq d^{7/8}$, as
required. $\blacksquare$

We now fill in the proofs of the above-stated facts.

Proof (of Lemma 4.4). Since each $S_{i}$ counts the number of Bernoulli-$p$
variables until success, $K$ distributes as $1+$ the number of successful
Bernoulli-$p$ variables, out of $r$. This interpretation immediately gives
$\operatorname*{\mathbb{E}}[K]=p(r-1)+1$. $\blacksquare$

Proof (of Lemma 4.5). Let $T_{0},T_{1},T_{2},\ldots$ be the sequence of times
$t\geq 0$ with $|I_{t}|\leq\frac{m+1}{2}$ (in increasing order). Observe that
for all $i$, the event $I_{T_{i}+1}=0$ happens with probability
$\geq\frac{1}{2(m+1)}$, even when conditioning on the trajectory
$\\{I_{t}\\}_{t\leq T_{i}}$ up to time $T_{i}$. Let $K$ be minimal with
$I_{T_{K}+1}=0$. Using the (probabilistic) chain rule this observation means
that

$\Pr[K\geq k]\leq(1-1/(2m+2))^{k}.$

When combined with

$\operatorname*{\mathbb{E}}[\min(T_{K},r)]\leq\operatorname*{\mathbb{E}}[\min(T_{0},r)]+\sum_{k=1}^{\infty}\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{K\geq
k-1\\}}\cdot\min(T_{k}-T_{k-1},r)\right],$

we deduce

$\operatorname*{\mathbb{E}}[\min(T_{K},r)]\leq\operatorname*{\mathbb{E}}[\min(T_{0},r)]+\sum_{k=1}^{\infty}\left(\frac{2m+1}{2m+2}\right)^{k-1}\operatorname*{\mathbb{E}}\left[\min(T_{k}-T_{k-1},r)\,\middle|\,K\geq
k-1\right].$ (6)

Clearly, upper bounding $\operatorname*{\mathbb{E}}[\min(T_{K},r)]$ is
relevant, as if $T$ is the minimal time with $I_{T}=0$, then $T\leq T_{K}+1$,
and in particular, $\min(T,r)\leq\min(T_{K},r)+1$. We claim the following:

  1. 1.

$\operatorname*{\mathbb{E}}[\min(T_{0},r)]\leq O(1+|I_{0}|\sqrt{r}/m)$.

  2. 2.

For all $i$, and all values of $\\{I_{t}\\}_{t\leq T_{i}}$,
$\operatorname*{\mathbb{E}}\left[\min(T_{i+1}-T_{i},r)\,\middle|\,I_{0},I_{1},\ldots,I_{T_{i}}\right]\leq
O(\sqrt{r})$.

These claims together with (6) and $\min(T,r)\leq\min(T_{K},r)+1$ give

$\operatorname*{\mathbb{E}}[\min(T,r)]\leq
O(1+|I_{0}|\sqrt{r}/m)+\sum_{k=1}^{\infty}\left(\frac{2m+1}{2m+2}\right)^{k-1}O(\sqrt{r})\leq
O(|I_{0}|\sqrt{r}/m+m\sqrt{r}),$

as required. Let us verify the above claims.

Claim 2) This is a specialization of Claim 1 to the walk
$I_{T_{i}+1},I_{T_{i}+2},\ldots$, satisfying
$|I_{T_{i}+1}|\leq\frac{3m+1}{2}$.

Claim 1) Without loss of generality assume $I_{0}\geq 0$ (due to symmetry).
Write $L=m\sqrt{r}$. Instead of the stopping time $\min(T_{0},r)$, consider
the stopping time $T^{\prime}$ which is the minimal (time) $t\geq 0$ with
$I_{t}\leq(m+1)/2$ or $I_{t}>L$. It is standard to show that
$\Pr[T^{\prime}>k]$ decreases exponentially fast with $k$ (albeit with
deficient constants), and so all quantities presented in the proof will turn
out to be finite (in particular, $\operatorname*{\mathbb{E}}[T^{\prime}]$).

Since the definition of $T_{0}$ is similar to that of $T^{\prime}$, except
that the latter allows to stop also when $I_{t}>L$, we may upper bound
$\operatorname*{\mathbb{E}}[\min(T_{0},r)]$ by
$\operatorname*{\mathbb{E}}[T^{\prime}]+r\Pr[I_{T^{\prime}}>L]$, i.e., we
compensate by $r$ in all cases when $T^{\prime}$ is not identical to $T_{0}$.

Since $I_{k+1}-I_{k}$ is a symmetric random variable, and is independent of
$I_{0},\ldots,I_{k}$, the sequence $I_{0},I_{1},\ldots$ constitutes a
martingale. In particular, by the _Optional stopping theorem_ ,
$\operatorname*{\mathbb{E}}[I_{T^{\prime}}]=I_{0}$. This implies, together
with that $|I_{k+1}-I_{k}|\leq m$

$I_{0}=\operatorname*{\mathbb{E}}[I_{T^{\prime}}]\geq-(m+1)/2\cdot\Pr[I_{T^{\prime}}\leq(m+1)/2]+L\Pr[I_{T^{\prime}}>L]\geq
L\Pr[I_{T^{\prime}}>L]-m,$

and in particular, $\Pr[I_{T^{\prime}}>L]\leq(m+I_{0})/L$. Recall that our
goal of proving _claim 1_ is non-trivial only when $I_{0}>(m+1)/2$, and so we
may assume $\Pr[I_{T^{\prime}}>L]\leq O(I_{0}/L)$. In particular,

$\operatorname*{\mathbb{E}}[\min(T_{0},r)]\leq\operatorname*{\mathbb{E}}[T^{\prime}]+r\cdot
O(I_{0}/L)\leq\operatorname*{\mathbb{E}}[T^{\prime}]+O(I_{0}\sqrt{r}/m).$

Thus the claim is implied from $\operatorname*{\mathbb{E}}[T^{\prime}]\leq
O(I_{0}\sqrt{r}/m)$ which we now prove.

Write $s=\operatorname*{\mathbb{E}}[(I_{k+1}-I_{k})^{2}]=(m^{2}+2m)/6$, and
consider the sequence of random variables

$\left(I_{k}^{2}-sk\right)_{k=0}^{\infty}.$

We claim it is a martingale. Indeed:

$\displaystyle\operatorname*{\mathbb{E}}\left[I_{k+1}^{2}-s(k+1)\,\middle|\,I_{0},\ldots,I_{k}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[I_{k}^{2}+2I_{k}(I_{k+1}-I_{k})+((I_{k+1}-I_{k})^{2}-s)-sk\,\middle|\,I_{0},\ldots,I_{k}\right]$
$\displaystyle=I_{k}^{2}-sk$

The first equality uses $(a+b)^{2}=a^{2}+2ab+b^{2}$, and the second uses the
fact that $I_{k+1}-I_{k}$ is a symmetric random variable independent of
$I_{0},\ldots,I_{k}$, having variance $s$. The _Optional stopping theorem_
thus implies
$I_{0}^{2}=\operatorname*{\mathbb{E}}[I_{T^{\prime}}^{2}-sT^{\prime}]$,
yielding
$\operatorname*{\mathbb{E}}[T^{\prime}]\leq\operatorname*{\mathbb{E}}[I_{T^{\prime}}^{2}]/s$.
To bound $\operatorname*{\mathbb{E}}[I_{T^{\prime}}^{2}]$, we recall that
$I_{T^{\prime}}$ has absolute value $\leq(m+1)/2$ with probability $\leq 1$
(trivially), and is between $L$ and $L+m$ with probability $\leq O(I_{0}/L)$.
Hence $\operatorname*{\mathbb{E}}[I_{T^{\prime}}^{2}]\leq
m^{2}+(L+m)^{2}O(I_{0}/L)$. Since $L\geq m$, we deduce
$\operatorname*{\mathbb{E}}[I_{T^{\prime}}^{2}]\leq O(s+I_{0}L)$. Overall,

$\operatorname*{\mathbb{E}}[T^{\prime}]\leq O(1+I_{0}L/s)\leq
O(1+I_{0}\sqrt{r}/m),$

and the proof is complete. $\blacksquare$

####  4.1.4 Conjectured optimal algorithm

The 2D-LPHS algorithms presented in the previous sections have the property of
not treating both axes symmetrically. For example, Recursive-Hash iterates
over several $i_{0}$’s, and for each of them it makes many queries of the form
$x[i_{0},j]$ for different $j$’s. Except for not being aesthetic, this
asymmetry has other disadvantages. For example, it is not obvious how to
generalize these algorithms to higher dimensions. More importantly, these
algorithms (that we considered) do not have optimal dependence of $\delta$ on
$d$.

We conjecture that the following symmetric algorithm (Random-Walk-Hash) has
the optimal performance of $\delta=\widetilde{O}(1/d)$. However, we were not
able to rigorously analyze it.

1Let $\psi_{1},\psi_{2}\colon\Sigma_{b}\to\\{-L,\ldots,L\\}$ be independent
random functions

2 begin

3 $P\leftarrow\mathrm{list}()$

4 for  _$s\leftarrow 0\ldots d-1$_ do

5 $P[s]\leftarrow(i,j)$

6 $v\leftarrow z[i,j]$

7 $(i,j)\leftarrow(i+\psi_{1}(v),j+\psi_{2}(v))$

8 if  _$(i,j)\in P$_ then

9 Let $t$ be the only index satisfying $P[t]=(i,j)$

10 $k\leftarrow\mathrm{arg\,min}_{u\in[t,s]}\\{z[P[u]]\\}$

11 $(i,j)\leftarrow P[k]$

12 while  _$(i,j)\in P$_ do

13 $j\leftarrow j+1$

14 end while

15

16 end if

17

18 end for

19 return $\mathrm{arg\,min}_{(i^{\prime},j^{\prime})\in
P}\\{z[i^{\prime},j^{\prime}]\\}$

20 end

21

Algorithm 7 rw-
stage$(z\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d\in\mathbb{N},L\in\mathbb{N},i\in\mathbb{Z}_{n},j\in\mathbb{Z}_{n})$

1 begin

2 $I\leftarrow\lg\lg(d)$

3 $d^{\prime}\leftarrow d/I$

4 $(i_{0},j_{0})\leftarrow\textsc{Min-Hash}(z,\ d^{\prime})$

5 $(i_{1},j_{1})\leftarrow\textsc{rw-stage}(z,\ d^{\prime},\ d^{\prime 1/4},\
i_{0},\ j_{0})$

6 $(i_{2},j_{2})\leftarrow\textsc{rw-stage}(z,\ d^{\prime},\ d^{\prime 3/8},\
i_{1},\ j_{1})$

7 $(i_{3},j_{3})\leftarrow\textsc{rw-stage}(z,\ d^{\prime},\ d^{\prime 7/16},\
i_{2},\ j_{2})$

8
$\vdots\qquad\vdots\qquad\vdots\qquad\vdots\qquad\vdots\qquad\vdots\qquad\vdots\qquad\vdots\qquad\vdots$

9 $(i_{I},j_{I})\leftarrow\textsc{rw-stage}(z,\ d^{\prime},\
\sqrt{d^{\prime}/2},\ i_{I-1},\ j_{I-1})$

10 return $(i_{I},j_{I})$

11 end

12

Algorithm 8 Random-Walk-
Hash$(z\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}},d\in\mathbb{N})$

##### Heuristic performance.

Here we heuristically describe why we expect the algorithm Random-Walk-Hash to
achieve $\delta=\widetilde{O}(1/d)$.

The main heuristic assumption we make is that each $\textsc{rw-
stage}(x,d,L,i,j)$ can be modeled by a random walk on $\mathbb{Z}^{2}$,
starting at $(i,j)$ and having independent steps which are uniformly
distributed on each axis as $\sim U(-L,L)$. We further assume that once the
two walks of $\textsc{rw-stage}(x)$ and $\textsc{rw-stage}(y)$ are
synchronized (collided), they remain synchronized. Moreover, we recall that
the output location of a $\textsc{rw-stage}(x)$ is the point visited in this
walk having the minimal $x$-value.

######  Remark.

These assumptions are not precise mainly because we need the steps to be both
deterministic and independent (with respect to the input’s randomness) of the
previous steps. In practice we cannot guarantee independence, since the random
walk occasionally runs into loops. We try to break these in a canonical way,
which complicates the analysis. If the algorithm would make monotone queries
along (at least) one axis (as the one-dimensional algorithm), then it would
avoid loops and its analysis would be much simpler. Unfortunately, we do not
know how to design such an algorithm with similar performance.

Based on the heuristic assumptions above, an analysis of Random-Walk-Hash
would follow from the following two claims:

  * •

Let $T$ be (a random variable measuring) the meeting time of two random walks
on $\mathbb{Z}^{2}$, starting at distance $D$ (in $L_{1}$ norm), and making
steps uniformly distributed in $\\{-L,-L+1,\ldots,L\\}$ on both axis. Then
$\operatorname*{\mathbb{E}}[\min(d^{\prime},T)]\leq
O(\sqrt{d^{\prime}}(L+D/L))$.777The parameters are chosen so that the parties
meet within an expected number of $O(\sqrt{d^{\prime}}(L+D/L))$ steps, while
they do not meet within $d^{\prime}$ steps with probability
$O((L+D/L)/\sqrt{d^{\prime}})$. We say that walks $A,B$ ‘meet’ in time $t$ if
$t$ is minimal so that $\exists i,j\leq t$ with
$\mathrm{location}_{i}(A)=\mathrm{location}_{j}(B)$.

  * •

The expected (Manhattan) distance between the start and final point of a
2D-walk with $d^{\prime}$ steps uniformly distributed in
$\\{-L,-L+1,\ldots,L\\}$ on both axis, is $O(L\cdot\sqrt{d^{\prime}})$.

Let us analyze the first few stages of Random-Walk-Hash using these claims
(which we do not prove here).

Just after the first stage, which is Min-Hash, the walks of $\textsc{Random-
Walk-Hash}(x)$ and Random- $\textsc{Walk-Hash}(y)$ are synchronized except for
probability $O(1/\sqrt{d^{\prime}})$ (Lemma 4.1), and in case of this failure
event, the distance of the two walks has expected value
$O(\sqrt{d^{\prime}})$.

At the second stage, $\textsc{rw-stage}(x,d^{\prime},d^{\prime 1/4})$, the
initial distance between the walks is $D=O(d^{\prime 1/2})$ and $L=d^{\prime
1/4}$. Using the above claims, and a Markov inequality, the random walks would
synchronize except for probability
$O(D/L+L)\sqrt{d^{\prime}}/d^{\prime}=O(d^{\prime-1/4})$, and in case of
failure, the expected distance is $O(d^{\prime 3/4})$.

At the third stage, $\textsc{rw-stage}(x,d^{\prime},d^{\prime 3/8})$,
$D=O(d^{\prime 3/4}),L=d^{\prime 3/8}$ and the failure probability becomes
$O(d^{\prime 3/8})/\sqrt{d^{\prime}}=O(d^{\prime-1/8})$, and the distance upon
failure is $=O(d^{\prime 7/8})$.

Continuing this heuristic to later stages we get that the total failure
probability, which is the product of failure probabilities of all the stages,
is $2^{O(I)}/d^{\prime}=\widetilde{O}(d^{-1})$.

###  4.2 Lower bounds on 2D-LPHS algorithms

In this section we prove Theorem 1.4 for $k=2$ (i.e., 2D-LPHS). The proof for
any other value of $k>1$ is similar. In particular, we show that any 2D-LPHS
algorithm satisfies $\delta\geq\Omega(1/d)$, given $n\geq 2d$.

######  Lemma 4.6 (Bigger shifts).

Let $h$ be a 2D $(n,b,d,\delta)$-LPHS. Let
$r_{1}^{\prime},r_{2}^{\prime}\in\mathbb{N}$, and
$y^{\prime}=x^{\prime}\ll(r_{1}^{\prime},r_{2}^{\prime})$ where
$x^{\prime}\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}}$ is a uniformly random string.
Then,

$\Pr\left[h(x^{\prime},d)-h(y^{\prime},d)\neq(r_{1}^{\prime},r_{2}^{\prime})\right]\leq\max\\{r_{1}^{\prime},r_{2}^{\prime}\\}\delta.$

Proof. Write $I=\max\\{r_{1}^{\prime},r_{2}^{\prime}\\}$ and set
$r_{1}^{\prime(i)}=\min(r_{1}^{\prime},i),r_{2}^{\prime(i)}=\min(r_{2}^{\prime},i)$.
Note $\forall
i\colon(r_{1}^{\prime(i+1)}-r_{1}^{\prime(i)}),(r_{2}^{\prime(i+1)}-r_{2}^{\prime(i)})\in\\{0,1\\}$.
Define the strings $x^{\prime}_{i}\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}}$ by
$x^{\prime}_{i}=x^{\prime}\ll(r_{1}^{\prime(i)},r_{2}^{\prime(i)})$ for
$i=0,\ldots,I$. Since each $x^{\prime}_{i}$ is a uniformly random function
(because $x^{\prime}$ is), we may use (2) to deduce

$\delta_{i}\doteqdot\Pr\left(A(x^{\prime}_{i},d)-A(x^{\prime}_{i+1},d)\neq(r_{1}^{\prime(i+1)}-r_{1}^{(i)},r_{2}^{\prime(i+1)}-r_{2}^{\prime(i)})\right)\leq\delta.$

Notice $x^{\prime}=x^{\prime}_{0}$ and $y^{\prime}=x^{\prime}_{I}$. Using a
union-bound argument, we conclude

$\Pr\left[A(x^{\prime},d)-A(y^{\prime},d)\neq(r_{1}^{\prime},r_{2}^{\prime})\right]\leq\sum_{i=0}^{I-1}\delta_{i}\leq
I\delta$

as required. $\blacksquare$

The following lemma implies Theorem 1.4 for $k=2$.

######  Lemma 4.7.

For $n>2d$ and any $b>0$, every 2D (cyclic or non-cyclic)
$(n,b,d,\delta)$-LPHS satisfies $\delta\geq 1/(3d)$.

Proof. Consider the set of queries $P$ made to a uniformly random string
$x\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}}$ by an $(n,b,d,\delta)$-LPHS $h(x,d)$.
That is, $P$ is a random variable whose values are sets of sizes $\leq d$ of
$(i,j)$ pairs.

Let $x^{\prime},y^{\prime}\in\Sigma_{b}^{\mathbb{Z}_{n}^{2}}$ be two uniformly
random strings related by
$y^{\prime}=x^{\prime}\ll(r_{1}^{\prime},r_{2}^{\prime})$ for independent
uniform variables $r_{1}^{\prime},r_{2}^{\prime}\sim\\{0,1,\ldots,2d\\}$.
Using Lemma 4.6,

$\begin{split}\Pr[h(x^{\prime},d)-h(y^{\prime},d)\neq(r_{1}^{\prime},r_{2}^{\prime})]&=\operatorname*{\mathbb{E}}_{r_{1}^{\prime},r_{2}^{\prime}}\left[\Pr\left[h(y^{\prime},d)-h(x^{\prime},d)\neq(r_{1}^{\prime},r_{2}^{\prime})\,\middle|\,r_{1}^{\prime},r_{2}^{\prime}\right]\right]\\\
&\leq\operatorname*{\mathbb{E}}_{r_{1}^{\prime},r_{2}^{\prime}}\left[\max(r_{1}^{\prime},r_{2}^{\prime})\delta\right]\leq
2d\delta.\end{split}$ (7)

Let $P_{x^{\prime}},P_{y^{\prime}}$ be copies of $P$ which are the sets of
queries issued by $h(x^{\prime},d),h(y^{\prime},d)$, respectively. Generally,
the random variables $P_{x^{\prime}},P_{y^{\prime}}$ are dependent. However,
we are going to see they are only slightly dependent. Indeed, suppose
$P_{1},P_{2}$ are two values of $P$. We claim that given specific values of
$r_{1}^{\prime},r_{2}^{\prime}$ (call these
$r_{1}^{\prime\prime},r_{2}^{\prime\prime}$) so that $P_{1}$ and (the
Minkowski sum) $P_{2}+\\{(r_{1}^{\prime\prime},r_{2}^{\prime\prime})\\}$ are
disjoint, we have

$\Pr\left[P_{x^{\prime}}=P_{1}\wedge
P_{y^{\prime}}=P_{2}\,\middle|\,(r_{1}^{\prime},r_{2}^{\prime})=(r_{1}^{\prime\prime},r_{2}^{\prime\prime})\right]=\Pr\left[P=P_{1}\right]\cdot\Pr\left[P=P_{2}\right].$
(8)

This is because the event $P_{x^{\prime}}=P_{1}$ depends only on
${\left.\kern-1.2ptx^{\prime}\vphantom{\big{|}}\right|_{P_{1}}}$ (i.e. lies
inside the $\sigma$-algebra generated by
${\left.\kern-1.2ptx^{\prime}\vphantom{\big{|}}\right|_{P_{1}}}$)888If the
LPHS is probabilistic, then we should add the algorithm’s randomness into the
$\sigma$-algebra. Since this randomness is independent of all other random
variables, the proof applies verbatim., which is independent of
${\left.\kern-1.2pty^{\prime}\vphantom{\big{|}}\right|_{P_{2}}}$, given that
$P_{1}$ and (the Minkowski sum)
$P_{2}+\\{(r_{1}^{\prime\prime},r_{2}^{\prime\prime})\\}$ are disjoint, as
different entries of $x^{\prime}$ are independent. Consider the ‘conditional’
random variable

$X_{r_{1}^{\prime\prime},r_{2}^{\prime\prime},P_{1},P_{2}}\doteqdot\left[h(x^{\prime},d)-h(y^{\prime},d)\,\middle|\,r_{1}^{\prime}=r_{1}^{\prime\prime},r_{2}^{\prime}=r_{2}^{\prime\prime},P_{x^{\prime}}=P_{1},P_{y^{\prime}}=P_{2}\right],$

which is defined on the part of the probability space in which
$r_{1}^{\prime}=r_{1}^{\prime\prime},r_{2}^{\prime}=r_{2}^{\prime\prime},P_{x^{\prime}}=P_{1},P_{y^{\prime}}=P_{2}$.
We use the law of total probability to compute

$\begin{split}\Pr[h(x^{\prime},d)&-h(y^{\prime},d)=(r_{1}^{\prime},r_{2}^{\prime})]\\\
&=\operatorname*{\mathbb{E}}_{r_{1}^{\prime},r_{2}^{\prime},P_{x^{\prime}},P_{y^{\prime}}}\left[\Pr\left[h(x^{\prime},d)-h(y^{\prime},d)=(r_{1}^{\prime},r_{2}^{\prime})\,\middle|\,r_{1}^{\prime},r_{2}^{\prime},P_{x^{\prime}},P_{y^{\prime}}\right]\right]\\\
&=\operatorname*{\mathbb{E}}_{r_{1}^{\prime},r_{2}^{\prime}}\left[\sum_{P_{1},P_{2}}\Pr\left[X_{r_{1}^{\prime},r_{2}^{\prime},P_{1},P_{2}}=(r_{1}^{\prime},r_{2}^{\prime})\right]\cdot\Pr\left[P_{x^{\prime}}=P_{1},P_{y^{\prime}}=P_{2}\,\middle|\,r_{1}^{\prime},r_{2}^{\prime}\right]\right]\\\
&\stackrel{{\scriptstyle(a)}}{{\leq}}\underbrace{\operatorname*{\mathbb{E}}_{r_{1}^{\prime},r_{2}^{\prime}}\left[\sum_{\begin{subarray}{c}P_{1},P_{2}\colon\\\
((r_{1}^{\prime},r_{2}^{\prime})\in
P_{1}-P_{2})\end{subarray}}\Pr\left[P_{x^{\prime}}=P_{1},P_{y^{\prime}}=P_{2}\,\middle|\,r_{1}^{\prime},r_{2}^{\prime}\right]\right]}_{Q_{1}}+\\\
&+\underbrace{\operatorname*{\mathbb{E}}_{r_{1}^{\prime},r_{2}^{\prime}}\left[\sum_{\begin{subarray}{c}P_{1},P_{2}\colon\\\
((r_{1}^{\prime},r_{2}^{\prime})\notin
P_{1}-P_{2})\end{subarray}}\Pr\left[X_{r_{1}^{\prime},r_{2}^{\prime},P_{1},P_{2}}=(r_{1}^{\prime},r_{2}^{\prime})\right]\cdot\Pr[P=P_{1}]\Pr[P=P_{2}]\right]}_{Q_{2}}\\\
&\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{d^{2}}{(2d+1)^{2}}+\frac{1}{(2d+1)^{2}}=\frac{d^{2}+1}{(2d+1)^{2}},\end{split}$

where $P_{1}-P_{2}$ is a Minkowski difference. Inequality $(a)$ follows from
(8) and the fact that probabilities are upper bounded by $1$. Inequality $(b)$
is the key argument. To bound $Q_{1}$ (by $d^{2}/(2d+1)^{2}$) we use

$Q_{1}+\underbrace{\operatorname*{\mathbb{E}}_{r_{1}^{\prime},r_{2}^{\prime}}\left[\sum_{\begin{subarray}{c}P_{1},P_{2}\colon\\\
((r_{1}^{\prime},r_{2}^{\prime})\notin
P_{1}-P_{2})\end{subarray}}\Pr[P=P_{1}]\Pr[P=P_{2}]\right]}_{Q_{3}}=1.$

Exchanging summation order and using
$\left|P_{1}-P_{2}\right|\leq|P_{1}|\cdot|P_{2}|\leq d^{2}$, which holds since
$h(x,d)$ makes at most $d$ queries, we see that $Q_{3}\geq
1-d^{2}/(2d+1)^{2}$. Notice we use here $n>2d$. This proves $Q_{1}\leq
d^{2}/(2d+1)^{2}$.

To bound $Q_{2}$, we note that every $(P_{1},P_{2})$ contributes at most

$\Pr[P=P_{1}]\Pr[P=P_{2}]/(2d+1)^{2}$

to $Q_{2}$. To see this, observe that the distribution of the random variable
$X_{r_{1}^{\prime\prime},r_{2}^{\prime\prime},P_{1},P_{2}}$ does not depend on
the particular value of $r_{1}^{\prime\prime},r_{2}^{\prime\prime}$ (given
that $P_{1}+(r_{1}^{\prime\prime},r_{2}^{\prime\prime})$ is disjoint from
$P_{2}$), and this random variable always attains a single value (that is, a
random variable $X$ and a set $E$ always satisfy $\sum_{e\in E}\Pr[X=e]\leq
1$). Hence

$Q_{2}\leq\sum_{P_{1},P_{2}}\frac{\Pr[P=P_{1}]\Pr[P=P_{2}]}{(2d+1)^{2}}=\frac{1}{(2d+1)^{2}}.$

Overall, we deduce $2d\delta+(d^{2}+1)/(2d+1)^{2}\geq 1$, implying $\delta\geq
3/(8d)$. $\blacksquare$

######  Remark (Extending Lemma 4.7 to higher dimensions).

The proof of Lemma 4.7 for $k=2$ readily extends to a lower bound on the error
probability of any $k$-dimensional LPHS with $k>2$ (the case $k=1$ follows
from the lower bound in [23] and our generic model equivalence with LPHS).
Concretely, for a $k$-dimensional LPHS we have $\delta\geq 1/(3d^{2/k})$
whenever $n>(2d)^{2/k}$, implying Theorem 1.4.

The extension to a general dimension $k$ requires the following modifications.
First, we use a distance-extension lemma, analogous to Lemma 4.6, in a way
similar to (7). This step reduces our task to showing that no algorithm can
synchronize on random inputs $x,y\in\Sigma_{b}^{\mathbb{Z}_{n}^{k}}$ with
probability higher than, say $1/2$, where $y$ is a random $k$-dimensional
shift of $x$ by about $(2d)^{2/k}$ in every axis.

Then, we observe that in the event that the LPHS applied on $x$ and $y$
queries disjoint input cells (we think of $x$ and $y$ as inlaid in a common
landscape), synchronization is unlikely, as expressed by the bound on $Q_{2}$
in the proof of Lemma 4.7. Hence, the synchronization probability is dominated
by the probability that the LPHS queries a shared input cell. To bound this
latter probability we use a birthday-paradox argument similar to the bound on
$Q_{1}$ in the proof of Lemma 4.7: there are at least
$((2d)^{2/k})^{k}=4d^{2}$ possible shifts, while there are only $d\times d$
pairs of queries that may collide – any of the $d$ queries made to $x$ may
collide with any of the $d$ queries made to $y$. It follows that there is a
probability of at most $1/4$ to have a shared query, concluding the argument.

##  5 LPHS for Worst-Case Inputs

The basic definition of LPHS provides guarantees for random input strings.
This directly aligns with some applications, where the strings to synchronize
can be chosen in such manner (e.g., when broadcasting a random synchronization
string). In many other application settings, however, we may wish to perform
locality-sensitive hashing on inputs whose structure is not uniform, e.g.
location coordination given substrings of an existing DNA string or image.
Here, it is not sufficient to provide small error probability over a random
input; rather, the input will be fixed, and we will wish to obtain small error
over a random choice of hash function. In this section, we address this notion
of locality-preserving hashing for shifts (LPHS) for worst-case inputs.

The main result in this section is showing how to use an underlying LPHS for
average-case inputs to obtain LPHS for worst-case inputs that do not exhibit
too much regularity (in which case one cannot hope to synchronize shifts
effectively). Our approach first embeds the input space endowed with shift
metric into an intermediate space over a larger alphabet also endowed with
shift metric, with the promise of _all symbols being distinct_. This can be
viewed as an analog of approaches taken, e.g. by [19], for the case of edit
distance and so-called _Ulam distance_ over permutations; however, for our
relaxation to shift metric as opposed to edit distance, we can accommodate
weaker restrictions on input strings.

In the following subsections, we address LPHS for worst-case inputs in the
settings of cyclic and non-cyclic shifts, respectively. For simplicity, we
restrict attention to the case of alphabet $\left\\{0,1\right\\}$; that is,
inputs $x\in\left\\{0,1\right\\}^{n}$.

###  5.1 Cyclic LPHS for Worst-Case Inputs

We begin with the somewhat simpler setting of cyclic shifts. To ensure that
our worst-case definition extends from a single shift to multiple shifts, it
will be convenient to define the following closure operator.

######  Definition 5.1.

[Closure under cyclic shifts] For a set of inputs
$X\subseteq\left\\{0,1\right\\}^{n}$, we let

${\hat{X}}=\\{x\ll i\,:\,x\in X,\,0\leq i<n\\}.$

######  Definition 5.2.

[Worst-case cyclic LPHS] Let $X\subseteq\left\\{0,1\right\\}^{n}$ be a set of
inputs. A family $\mathcal{H}$ of hash functions
$h:\left\\{0,1\right\\}^{n}\to\mathbb{Z}_{n}$ is an $(n,d,\delta)$-cyclic LPHS
for worst-case inputs in $X$ if each $h$ makes $d$ (adaptive) queries (of the
form $x[i]$), for every $x\in\hat{X}$, it holds that

$\Pr_{h\in_{R}\mathcal{H}}[h(x)\neq h(x\ll 1)+1]\leq\delta.$

Unlike the case of LPHS for random inputs, in the worst-case setting the
choice of hash function must necessarily be randomized in order to achieve low
per-input error.

A first observation is that one cannot hope to synchronize shifts of inputs
$x$ that exhibit too much regularity: for example, the all-0 string. We
formalize this requirement as $\alpha$-goodness, such that any cyclic shift of
$x$ differs in at least an $\alpha$-fraction of positions from $x$. In what
follows, $\Delta(x,y)$ denotes the Hamming distance of strings
$x,y\in\left\\{0,1\right\\}^{n}$.

######  Definition 5.3 ($\alpha$-good inputs).

An input $x\in\left\\{0,1\right\\}^{n}$ is said to be $\alpha$-good if for
every $i\in[n]$ it holds that $\Delta(x\ll i,x)\geq\alpha n$. We denote the
set of all $\alpha$-good inputs in $\left\\{0,1\right\\}^{n}$ by ${\sf
Good}^{\alpha}_{n}$.

Note that ${\sf Good}^{\alpha}_{n}$ is closed under shifts. The above goodness
requirement is necessary, in the sense that even if it is only violated by a
single shift $0<i<n$, it requires a notable deterioration of the LPHS
parameters. For example, if $x$ is a random string with period $n/2$ (i.e.,
$x=(x\ll n/2)$), then for any choice of hash function $h$ necessarily
$h(x)=h(x\ll n/2)$, meaning one cannot achieve $\delta$ better than $2/n$.

######  Remark (Biased random inputs).

As an example application, inputs that occur as the result of _biased_ random
sampling satisfy the above $\alpha$-goodness with high probability, for
$\alpha$ that is a function of the bias.

Namely, consider the distribution $\mathcal{D}_{\beta}$ over
$\left\\{0,1\right\\}^{n}$ where each bit $x_{i}$ is selected as biased i.i.d.
bits, equalling 1 with (constant) probability $0<\beta<1$. Then if $n$ is
prime (or, more generally, without too many factors), then for every constant
$\alpha<\min\\{\beta,1-\beta\\}$, it holds that

$\Pr_{x\in_{R}\mathcal{D}_{\beta}}[x\in{\sf Good}^{\alpha}_{n}]\geq
1-ne^{-\Omega(n)}.$

To see this, observe that since $n$ is prime, then for any given nonzero shift
$0<i<n$, it holds that $(1,1+i,1+2i,\dots,1+ni)$ forms a permutation of $[n]$.
Consider the string $y:=(x_{1},x_{1+i},x_{1+2i},\dots,x_{1+ni})$, formed by
appropriately permuting $x\in\left\\{0,1\right\\}^{n}$. Then $\Delta(x,x\ll
i)$ is equal to the number of positions $j\in[n]$ for which $y_{j}\neq
y_{j+1}$ (taking $y_{n+1}:=y_{1}$). For each $j\in[n]$, conditioned on the
values of $y_{1},\dots,y_{j}$, the value of $y_{j+1}$ is randomly sampled with
bias $\beta$. In particular, for any such prefix, the probability that
$y_{j+1}\neq y_{j}$ is at least $\min\\{\beta,1-\beta\\}$. The claim thus
follows by a Chernoff bound, together with a union bound over choices of
$i\in[n]$.

Our main result is a black-box construction of worst-case LPHS for the set of
inputs ${\sf Good}^{\alpha}_{n}$, from any LPHS for random inputs, with small
overhead (poly-logarithmic in the query complexity).

At a high level, the construction reduces to the case of random inputs, by (1)
considering an intermediate input value
$x^{\prime}\in(\left\\{0,1\right\\}^{b})^{n}$ over a larger alphabet
$\left\\{0,1\right\\}^{b}$, whose symbols are formed from a random tiling of
$b\in\omega(\log n)$ bits of $x$, and then (2) converting $x^{\prime}$ to a
new input $y\in\left\\{0,1\right\\}^{n}$ using an $n$-wise independent hash
$\gamma:\left\\{0,1\right\\}^{b}\to\left\\{0,1\right\\}$. This approach is
reminiscent of the generic alphabet-enlarging procedure used in Property 2.7
(and other prior works) via shingling, except with randomly chosen tile
windows to accommodate worst-case inputs. As we will show, the
$\alpha$-goodness of the original input $x$ will ensure with high probability
over the choice of tiling that all tile-symbols of $x^{\prime}$ are distinct
elements of $\left\\{0,1\right\\}^{b}$. Then by $n$-wise independence of
$\gamma$, the resulting input $y\in\left\\{0,1\right\\}^{n}$ will be uniform.
Note that if we begin with an LPHS which makes only $d$ queries to the
(random) input, then we require only $d$-wise independence of $\gamma$.

######  Proposition 5.4 (Worst-case cyclic LPHS for $\alpha$-good inputs).

Assume there exists an $(n,d,\delta)$-cyclic LPHS for random inputs. Then, for
every $0<\alpha(n)\leq 1$ and $b\geq\omega(\log n)$, there exists a
$(n,d^{\prime},\delta^{\prime})$-cyclic LPHS for worst-case inputs in ${\sf
Good}^{\alpha}_{n}$, with $d^{\prime}=O(d\cdot b)$ and
$\delta^{\prime}=\delta+n^{2}(1-\alpha)^{b}$.

Plugging in the LPHS construction from Theorem 3.5 (quoted from [23]),
together with $b\in\omega(\log n)\cap\log^{O(1)}(n)$ yields the following
corollary.

######  Corollary 5.5.

For every constant $0<\alpha\leq 1$, there exists a worst-case _cyclic_
$(n,d,\delta)$-LPHS for ${\sf Good}^{\alpha}_{n}$ with $d=\tilde{O}(\sqrt{n})$
and $\delta=O(1/n)$.

We now proceed to prove Proposition 5.4.

Proof. Let $b=b(n)$. Consider the following hash function family
$\mathcal{H}=\\{h_{S,\gamma}\\}$, indexed by a subset $S\subset[n]$ of size
$b$, and a hash function
$\gamma:\left\\{0,1\right\\}^{b}\to\left\\{0,1\right\\}$ from an $n$-wise
independent hash family. Sampling a hash function $h_{S,\gamma}$ from
$\mathcal{H}$ will consist of randomly selecting $S\subset[n]$ and sampling
$\gamma$ from the $n$-wise independent hash family.

The worst-case LPHS will use as a black box an underlying $(n,d,\delta)$-LPHS
$h^{*}:\left\\{0,1\right\\}^{n}\to\mathbb{Z}$ on random inputs.

Evaluation of $h_{S,\gamma}(x)$, for $x\in\left\\{0,1\right\\}$:

  1. 1.

For $i\in[n]$, denote $i+S=\\{i+s\mod n~{}|~{}s\in S\\}$ and
$x_{i+S}=(x_{j})_{j\in i+S}\in\left\\{0,1\right\\}^{b}$.

  2. 2.

Execute the algorithm for average-case LPHS $h^{*}$. For each index $i\in[n]$
that $h^{*}$ wishes to query, perform the following:

    1. (a)

Query $b$ indices of $x$, corresponding to the set $(i+S)\subset[n]$. Denote
the corresponding bit string by $x_{i+S}\in\left\\{0,1\right\\}^{b}$.

    2. (b)

Let $y_{i}:=\gamma(x_{i+S})\in\left\\{0,1\right\\}$. Submit $y_{i}$ to
$h^{*}$, as the answer to query $i\in[n]$.

  3. 3.

Let $z\in\mathbb{Z}$ denote the output of $h^{*}$. Output $z$.

Note that the query complexity of $h_{S,\gamma}$ is precisely $b$ times the
query complexity of $h^{*}$. We now analyze the correctness of the resulting
worst-case LPHS.

######  Claim 5.6.

Let $x\in{\sf Good}^{\alpha}_{n}$. With overwhelming probability over a random
choice of subset $S\subset[n]$ of size $b(n)\leq n$, all $S$-tiles $x_{i+S}$
of $x$ are distinct. Namely,

$\Pr_{h_{S,\gamma}\in_{R}\mathcal{H}}[\exists i\neq
i^{\prime}\in[n],x_{i+S}=x_{i^{\prime}+S}]\leq n^{2}\cdot(1-\alpha)^{b}.$

Proof (of Claim 5.6). Fix $i<i^{\prime}\in[n]$. By $\alpha$-goodness of the
input $x$, it holds that $\Delta(x\ll i,x\ll
i^{\prime})=\Delta(x,x\ll(i^{\prime}-i))\geq\alpha n$; that is, there exists a
subset $T\subseteq[n]$ of size $|T|\geq\alpha n$ for which $x_{i+j}\neq
x_{i^{\prime}+j}$ for every $j\in T$. Over the choice of $S$,
$\Pr_{S}[x_{i+S}=x_{i^{\prime}+S}]\leq\Pr_{S}[S\cap
T=\emptyset]\leq(1-\alpha)^{b}$. The claim thus holds by a union bound over
pairs $i,i^{\prime}\in[n]$. $\blacksquare$

Conditioned on distinctness of all $S$-tiles $x_{i+S}$ queried by the
algorithm $h^{*}$, then by $n$-wise independence of the hash family $\gamma$,
it holds that the computed output bits $y_{i}:=\gamma(x_{i+S})$ will be
independently random. That is, conditioned on the above event, the hash
function $h_{S,\gamma}$ will err with probability identical to that of $h^{*}$
on a random input. The proposition follows.

$\blacksquare$

###  5.2 Non-Cyclic LPHS for Worst-Case Inputs

We next present and achieve a notion of _non-cyclic_ LPHS for worst-case
inputs, up to a maximum shift $R$. In this case, the alphabet-tiling procedure
must be adjusted, as symbols outside the shift window will be lost. Instead,
we consider a modified approach, in which the tiles for each index $i$ are
chosen as a random subset from within a $W$-size window beginning at index
$i$, for $W<n$. This makes for a slightly more complex “goodness” condition
for worst-case input strings.

######  Definition 5.7 (Worst-Case LPHS).

Let $X\subseteq\left\\{0,1\right\\}^{n}$ be a set of inputs. A family
$\mathcal{H}$ of hash functions $h:\left\\{0,1\right\\}^{n}\to\mathbb{Z}_{n}$
is a (non-cyclic) $(n,d,\delta)$-LPHS for worst-case inputs in $X$, up to
shift bound $R$, if each $h$ makes $d$ (adaptive) queries (of the form
$x[i]$), and for every $x\in X$, and every $1\leq r\leq R$ it holds that

$\Pr_{h\in_{R}\mathcal{H}}[h(x)\neq h(x\lll r)+r]\leq\delta.$

We formalize the desired input non-regularity requirement via
$(\alpha,W)$-goodness, parameterized by a “window size” $W\in[n]$ and
difference parameter $0<\alpha\leq 1$, such that each of the length-$W$
substrings $x$ differ pairwise in at least $\alpha$ fraction of their symbols.
In what follows, we denote by $x_{i+[W]}$ the $W$-substring of $x$ beginning
at index $i$ (which may have length less than $W$ if $(i+W)<n$), and by
$\Delta(x^{\prime},y^{\prime})$ the Hamming distance of strings
$x^{\prime},y^{\prime}\in\left\\{0,1\right\\}^{\ell}$ (where $1\leq\ell\leq
W$).

######  Definition 5.8 ($(\alpha,W)$-good inputs).

An input $x\in\left\\{0,1\right\\}^{n}$ is said to be $(\alpha,W)$-good if for
every $i<i^{\prime}\in\\{1,\dots,n-W/2\\}$ it holds that
$\Delta(x_{i+[W]},x_{i^{\prime}+[W]})\geq\alpha|x_{i^{\prime}+[W]}|$.999Note
for $i\leq n-W$, the length $|x_{i+[W]}|=W$, but for
$(n-W)<i^{\prime}\leq(n-W/2)$, then
$W/2\leq|x_{i^{\prime}+[W]}|=(n-i^{\prime})<W$. That is, we consider also
substring windows that “hang over” the edge of the string $x$ up to $W/2$. We
denote the set of all $(\alpha,W)$-good inputs in $\left\\{0,1\right\\}^{n}$
by ${\sf Good}^{\alpha,W}_{n}$.

######  Remark (Biased random inputs).

As with the cyclic case, we similarly have that biased per-bit random inputs
satisfy $(\alpha,W)$-goodness with high probability for sufficiently large $W$
and $\alpha$ that is a function of the bias.

Namely, consider the same distribution $\mathcal{D}_{\beta}$ over
$\left\\{0,1\right\\}^{n}$ where each bit $x_{i}$ is selected as biased i.i.d.
bits, equalling 1 with (constant) probability $0<\beta<1$. Then for every
constant $\alpha<\min\\{\beta,1-\beta\\}$, it holds that

$\Pr_{x\in_{R}\mathcal{D}_{\beta}}[x\in{\sf Good}^{\alpha,W}_{n}]\geq
1-n^{2}e^{-\Omega(W)}.$

(Note here that $n$ need not be prime.) The argument here follows similarly to
the cyclic case, except without the complication of cyclic wraparound.

Consider a fixed pair $i<j\in[n-W/2]$. We analyze
$\Delta(x_{i+[W]},x_{j+[W]})=|\\{\ell\in[W]:x_{i+\ell}\neq x_{j+\ell}\\}|$. We
may again reorder the elements of $x$, this time into a collection of
$i^{\prime}:=j-i$ sequences, the corresponding shifted cosets of
$(x_{i},x_{i+i^{\prime}}x_{i+2i^{\prime}},\cdots)$ starting with the
corresponding $(j-i)$th value $x_{\ell}$, $\ell\in\\{i,\dots,j-1\\}$, and
containing all $i^{\prime}$-multiple instances, up to $j+W$. For any such
sequence, and any fixed choice of values in the prefix of the sequence, the
probability that the following term is equal to the previous is at least
$\min\\{\beta,1-\beta\\}$. Altogether, all indices in the range
$\\{i,\dots,i+W\\}\cup\\{j,\dots,j+W\\}$ thus contribute a fresh term, aside
from the initial $(j-i)$ that served as start points of the sequences. The
claim thus follows by a Chernoff bound, together with union bound over pairs
$i,j$. Note that for $W\in\omega(\log n)$, the resulting error probability is
negligible.

As with the cyclic case, we demonstrate an analogous black-box construction of
worst-case _non-cyclic_ LPHS for the set of inputs ${\sf
Good}^{\alpha,W}_{n}$, from any _non-cyclic_ LPHS for random inputs, with
small overhead. We state the following proposition in terms of an arbitrary
window-size parameter $W$, and then discuss relevant settings afterward.

######  Proposition 5.9 (Worst-Case LPHS For $(\alpha,W)$-Good Inputs).

Assume there exists an $(n,d,\delta)$-non-cyclic LPHS with shift bound $R$ for
_random_ inputs. Then, for every $0<\alpha(n)\leq 1$, $1<W(n)\leq n$, and
$b\geq\omega(\log n)$, there exists an
$(n^{\prime},d^{\prime},\delta^{\prime})$-non-cyclic LPHS with shift bound $R$
for _worst-case_ inputs in ${\sf Good}^{\alpha,W}_{n^{\prime}}$, with
$n^{\prime}=n+W$, $d^{\prime}=O(d\cdot b)$ and
$\delta^{\prime}=\delta+e^{-\Omega(b)}$.

Proof. Let $b=b(n)$, $W=W(n)$. Consider the hash function family
$\mathcal{H}=\\{h_{S,\gamma}\\}$ as defined within the proof of Proposition
5.4, indexed by a subset $S\subset[W]$ of size $b$, and a hash function
$\gamma:\left\\{0,1\right\\}^{b}\to\left\\{0,1\right\\}$ from an $n$-wise
independent hash family. Here, we have the following two differences from the
cyclic case:

  * •

Sampling a hash function $h_{S,\gamma}$ from $\mathcal{H}$ will consist of
randomly sampling $\gamma$ from the $n$-wise independent hash family (as
before), but now sampling the subset $S\subset[W]$ instead of $[n]$.

  * •

The worst-case LPHS will use as a black box an underlying $(n,d,\delta)$-_non-
cyclic_ LPHS $h^{*}:\left\\{0,1\right\\}^{n}\to\mathbb{Z}$ on random inputs
(as opposed to cyclic LPHS).

Note that (as before) the query complexity of $h_{S,\gamma}$ is precisely $b$
times the query complexity of $h^{*}$. We now analyze the correctness of the
resulting worst-case LPHS.

First, note that for any $x\in{\sf Good}^{\alpha,W}_{n^{\prime}}$ and $1\leq
r\leq R$, then with high probability over $y\in_{R}\left\\{0,1\right\\}^{r}$,
it holds that the concatenated string $z:=x||y\in{\sf
Good}^{\alpha/2,W}_{n^{\prime}+r}$. Indeed, consider
$\Delta(z_{i+[W]},z_{j+[W]})$ for various choices of
$i,j\in[n^{\prime}+r-W/2]$. From the definition of ${\sf
Good}^{\alpha,W}_{n^{\prime}}$, the required relative distance $\alpha/2$
holds for pairs with $i,j\in[n^{\prime}-W/2]$. For any
$i\in[n^{\prime}+r-W/2]$ and
$j\in\\{(n^{\prime}-W/2+1),\dots,(n^{\prime}+r-W/2)\\}$, then the string
$z_{j}$ is composed of at least $W/2$ _uniform_ bits (coming from $y$); the
required relative distance $\alpha/2$ thus holds except with probability upper
bounded by $e^{-\Omega(W)}$, by the (biased) random inputs Remark above.

The proposition then follows from the following claim, which collectively
implies that our transformation reduces (with small error) directly to the
underlying average-case LPHS: (1) First, that aside from probability
$n^{2}(1-\alpha)^{b}$ over $h_{S,\gamma}$, queries into a “good” input in
$\left\\{0,1\right\\}^{n+W}$ get mapped to queries into a _uniform_ input in
$\left\\{0,1\right\\}^{n}$; (2) Second, that the transformation preserves the
(non-cyclic) shift metric.

######  Claim 5.10.

For given $S,\gamma$, define
$f_{S,\gamma}:\left\\{0,1\right\\}^{n+W}\to\left\\{0,1\right\\}^{n}$ via
$f_{S,\gamma}(x)=(\gamma(x_{i+S}))_{i\in[n]}$. For every $x\in{\sf
Good}^{\alpha,W}_{n^{\prime}}$, the following hold:

  1. 1.

With high probability over a random choice of subset $S\subset[W]$ of size
$b(n)\leq n$, all “$S$-tiles” $x_{i+S}$ of $x$ are distinct. Namely,

$\Pr_{S\in_{R}{W\choose b}}[\exists i\neq
i^{\prime}\in[n],x_{i+S}=x_{i^{\prime}+S}]\leq n^{2}\cdot(1-\alpha)^{b}.$

As a consequence, then with probability $1-n^{2}(1-\alpha)^{b}$ over the
choice of $S$, it holds that $\left\\{f_{S,\gamma}(x)\right\\}_{\gamma}\equiv
U_{\left\\{0,1\right\\}^{n}}$, where the distribution
$\left\\{f_{S,\gamma}(x)\right\\}_{\gamma}$ is over the choice of $\gamma$,
and $U_{\left\\{0,1\right\\}^{n}}$ denotes the uniform distribution over
$\left\\{0,1\right\\}^{n}$.

  2. 2.

The map $f_{S,\gamma}$ preserves the (non-cyclic) shift metric. That is, for
every $1\leq r\leq R$,

     * •

Agreement window: For every $S,\gamma$, and every index $(1+r)\leq
i\leq(n-r)$, it holds that $f_{S,\gamma}(x)_{i}=f_{S,\gamma}(x\lll r)_{i+r}$
with probability 1 (over randomness of $\lll$).

     * •

Outside agreement window:

$\left\\{f_{S,\gamma}(x\lll
r)\right\\}_{\gamma}\equiv\left\\{\Big{(}f_{S,\gamma}(x)_{[1+r,\dots,n]},U_{\left\\{0,1\right\\}^{r}}\Big{)}\right\\}_{\gamma}.$

Proof. We address each part of the claim.

  1. 1.

Fix $i<i^{\prime}\in[n]$. By $(\alpha,W)$-goodness of the input $x$, it holds
that $\Delta(x_{i+[W]},x_{i^{\prime}+[W]})\geq\alpha n$; that is, there exists
a subset $T\subseteq[W]$ of size $|T|\geq\alpha n$ for which $x_{i+j}\neq
x_{i^{\prime}+j}$ for every $j\in T$. Over the choice of $S$,
$\Pr_{S}[x_{i+S}=x_{i^{\prime}+S}]\leq\Pr_{S}[S\cap
T=\emptyset]\leq(1-\alpha)^{b}$. The claim thus holds by a union bound over
pairs $i,i^{\prime}\in[n]$.

  2. 2.

Note that $x\in\left\\{0,1\right\\}^{n+W}$ and $x\lll r$ satisfy the property
$x_{i}=(x\lll r)_{i+r}$ for all $i\in[n+W-r]$. Since $S\subset[W]$, then in
particular $x_{i+S}=(x\lll r)_{i+r+S}$ for every $i\in[n-r]$. This implies the
desired equality within the agreement window.

Outside the agreement window, the required property holds directly by applying
the Claim part (1) to the appended string $z:=x||y$ for
$y\in_{R}\left\\{0,1\right\\}^{r}$, which can be done since (as argued above),
this string satisfies $z\in{\sf Good}^{\alpha/2,W}_{n^{\prime}+r}$.

$\blacksquare$

$\blacksquare$

Plugging in the non-cyclic LPHS construction from Theorem 3.5, together with
$b\in\omega(\log n)\cap\log^{O(1)}(n)$ yields the following corollary.

######  Corollary 5.11.

For every constant $0<\alpha\leq 1$ and $W\in\omega(\log n)$, there exists a
worst-case _non-cyclic_ $(n,d,\delta)$-LPHS for ${\sf Good}^{\alpha,W}_{n}$
with $d=\tilde{O}(\sqrt{n})$ and $\delta=O(1/n)$.

Let $d_{S}(x,y)$ denote non-cyclic shift distance, defined as the distance
between $x$ and $y$ on the De Bruijn Graph. Then the above results imply the
following (probabilistic, bounded-distance) isometric embedding of $d_{S}$ to
the line.

######  Corollary 5.12.

Let $0<\alpha\leq 1$, $R\in[n]$ be a shift distance bound, $W\in\omega(\log
n)$, and $d<n^{1/2}$. Then, there exists a family of hash functions
$\mathcal{H}$ such that

  1. 1.

Each $h\in\mathcal{H}$ makes $d$ queries to the input;

  2. 2.

For all $x,y\in{\sf Good}^{\alpha,W}_{n}$ with $d_{S}(x,y)=r\leq R$, we have
$\Pr[|h(x)-h(y)|\neq r]\leq\tilde{O}(r/d^{2})$.

##  6 Applications

In this section we present several cryptographic and algorithmic applications
that motivate the different LPHS flavors studied in this work. In all
applications, there are two or more parties that have partially overlapping
views of a large object, and the goal is to measure in sublinear time the
relative misalignment between the views, with low failure probability and
without direct interaction between the parties. Before discussing the
applications in detail, we give a taxonomy of the kinds of LPHS instances on
which they depend.

  * •

1-dimensional vs. $k$-dimensional. The first application, to packed
homomorphic secret sharing, requires $k$-dimensional LPHS for $k\geq 2$. The
other applications can apply in any dimension, but the 2-dimensional variant
seems most useful in the context of natural use cases that involve
2-dimensional objects (such as digital images).

  * •

Cyclic vs. non-cyclic. While some of the applications can also meaningful in
the cyclic case, the non-cyclic one is needed to capture the “partially
overlapping views” scenario.

  * •

Random vs. worst-case. In the application to packed homomorphic secret sharing
from a generic group, the object is a huge and locally random mathematical
object. Hence the default random-input variant of LPHS suffices. In other
applications, which may involve physical objects or digital documents, the
worst-case variant is needed. While the latter must inevitably exclude objects
that are close to being highly periodic, this is not an issue for most natural
use cases.

  * •

Small shift vs. big shift. When the misalignment is small, one could apply a
MinHash-based $(d,\tilde{O}(1/d))$-LPHS and reduce its failure probability via
repetition. This solution is not suitable for applications that depend on the
simple metric structure of the LPHS output, and in any case leads to inferior
communication rate (for the same failure probability and running time)
compared to applying a single instance of a $(d,\tilde{O}(1/d^{2}))$-LPHS. In
applications that require detecting an arbitrary misalignment in sublinear
time, a $(d,\tilde{O}(1/d))$-LPHS does not suffice at all since the failure
probability is multiplied by the shift amount.

We proceed with the details of the applications, starting with cryptographic
applications.

###  6.1 Packed Homomorphic Secret Sharing

In this section, we present a cryptographic application of _$k$ -dimensional_
LPHS for constructing a “packed” version of homomorphic secret sharing (HSS)
from cryptographically hard groups. Roughly speaking, $k$-packed HSS can share
a vector of $k$ values at the same communication cost as sharing a single
value. This improved communication comes at the expense of a computational
overhead that we optimize using two distinct LPHS-based approaches. Our main
approach relies on $k$-dimensional LPHS. Since even for $k=2$ we do not have a
provable optimal construction of $k$-dimensional LPHS, we also present an
alternative approach that relies on 1-dimensional LPHS and performs better in
some parameter regimes.

The remainder of this section is composed as follows. In Section 6.1.1 we
introduce a $k$-dimensional variant of the DDL problem and in Section 6.1.2 we
show how to realize it from $k$-dimensional non-cyclic LPHS. Then, in Section
6.1.3, we present the application of $k$-dimensional DDL to reducing the
communication complexity of group-based HSS, as well as an alternative
construction based on 1-dimensional embedding.

####  6.1.1 Multidimensional DDL

In this section we describe a $k$-dimensional generalization of DDL ($k$D-DDL
for short) that we will use as an intermediate step towards constructing
packed HSS. Since DDL has already found applications beyond the context of HSS
[26, 29, 25], one may expect the same for the $k$-dimensional variant.

While perhaps the most direct extrapolation of DDL to $k$ dimensions would
correspond to a DDL challenge within $k$ _independent_ copies of the group
(i.e., $\mathbb{Z}_{n}^{k}\hookrightarrow\bigoplus_{i=1}^{k}G$), for our
purposes, we will consider a notion where the $k$ dimensions are embedded
within a single group $G$ of size $N\gg n$. More explicitly, we will embed
$\mathbb{Z}_{n}^{k}\hookrightarrow G$ via
$(j_{1},\dots,j_{k})\mapsto\prod_{i=1}^{k}g_{i}^{j_{i}}$ for $k$ randomly
selected generators $g_{i}$ of $G$. As this embedding is not injective, its
use within a construction of $k$D-DDL from $k$D-LPHS will introduce an extra
collision error probability; however, when $N$ is much bigger than the number
of queries $d$ made by the $k$D-LPHS algorithm (as will be the case for the
HSS application), this collision error probability will be negligible.

As in the case of (1-dimemsional) DDL algorithms defined in Section 3.1, we
consider generic algorithms, i.e. operating within the generic group model. We
present a version of this model that captures the $k$-dimensional case below.

Recall that in the 1-dimensional case, the LPHS parameter $n$ was the same as
the group size and the LPHS string $x^{(b)}$ represented the sequence of all
group elements. Since this will no longer be the case in the $k$-dimensional
variant, from here on we denote the group size by $N$, and the sequence of
labels of group elements by $X^{(b)}$. In the 1-dimensional case, we
considered an experiment where a string $X^{(b)}\in\Sigma_{b}^{N}$
(representing the group) and a value $v\in\mathbb{Z}_{N}$ are sampled
uniformly; the generic DDL algorithm makes adaptive queries of the form
$(\alpha,\beta)\in\mathbb{Z}_{N}\times\mathbb{Z}_{N}$, which are answered by
$X^{(b)}[\ell_{v}(\alpha,\beta)]\in\Sigma_{b}$, where
$\ell_{v}(\alpha,\beta):=\alpha\cdot v+\beta\in\mathbb{Z}_{N}$, and outputs a
value $\gamma\in\mathbb{Z}_{N}$. The goal of the 1D-DDL algorithm was that the
outputs $\gamma,\gamma^{\prime}$ on implicit inputs $v$ and $v^{\prime}=v+1$
satisfied $\gamma-\gamma^{\prime}=1$.

In the $k$-dimensional experiment that we define, again, a string
$X^{(b)}\in\Sigma_{b}^{\mathbb{Z}_{N}}$, representing a single group of order
$N$ with generator $g$, and a value $v\in\mathbb{Z}_{N}$. are sampled
uniformly. In addition, $k$ public “basis elements”
$w_{1},\dots,w_{k}\leftarrow\mathbb{Z}_{N}$ are randomly selected,
representing the (discrete logarithm of) $k$ group generators
$g_{i}=g^{w_{i}}$. We assume $N$ to be prime, in which case the $g_{i}$ are
distinct group generators with high probability. Given this setup, the generic
algorithm $A^{\mathrm{G}}$ makes adaptive queries of the form
$(\alpha,(\beta_{1},\ldots,\beta_{k}))\in\mathbb{Z}_{N}\times\mathbb{Z}_{N}^{k}$,
which are answered by $X^{(b)}[\alpha v+\sum_{i=1}^{k}\beta_{i}w_{i}]$, namely
the string handle of the group element
$(g^{v})^{\alpha}\cdot\prod_{i=1}^{k}g_{i}^{\beta_{i}}$.

The output of the algorithm is an integer vector $\gamma\in\mathbb{Z}^{k}$.
Here we use the notation $A^{\mathrm{G,w}}(X^{(b)},v)$ to indicate that $A$ is
a generic algorithm that does not have direct access to $X^{(b)}$ and $v$, but
can have full knowledge of the public basis $w=(w_{1},\ldots,w_{k})$.

The goal of the $k$D-DDL algorithm is to similarly detect a shift of 1 on the
input in any one of the $k$ dimensions. In this case, such a shift in
dimension $i\in[k]$ corresponds to an additive offset of $w_{i}$ in the
discrete logarithm. Concretely, we would like that the outputs
$\gamma,\gamma^{\prime}$ on implicit inputs $v$ and $v^{\prime}=v+w_{i}$ to
satisfy $\gamma-\gamma^{\prime}=e_{i}$, the $i$th unit vector in
$\mathbb{Z}^{k}$.

Note that the error probability of a $k$D-DDL algorithm can come from multiple
sources: its internal coins, the choice of the implicit input $v$, and the
“setup” process of choosing group labels $X^{(b)}$ and the basis $w$. While
for the purpose of driving down the error via repetition it is useful to
separate the first source of error from the others (see more below), we will
consider the probability space that combines all these random choices for
simplicity.

######  Definition 6.1 ($k$D-DDL).

A generic $k$D-DDL algorithm $A$ is an $(N,b,d,\delta)$ $k$D-DDLA if $A$ makes
$d$ (adaptive) queries and for every $i\in[k]$,

$\Pr[A^{{\mathrm{G,w}}}(X^{(b)},v)-A^{{{\mathrm{G,w}}}}(X^{(b)},v+w_{i})\neq
e_{i}]\leq\delta,$

where $A^{\mathrm{G}}$ denotes generic access as described above and the
probability is over the choice of $X^{(b)}$ from $\Sigma_{b}^{\mathbb{Z}_{N}}$
and $v,w_{1},\ldots,w_{k}$ from $\mathbb{Z}_{N}$.

######  Remark (Bigger $k$-dimensional shifts).

Analogously to Lemma 2.4, we can use a union bound to deduce a bound on the
error probability for bigger $k$-dimensional shifts. Concretely, for any
$(N,b,d,\delta)$ $k$D-DDLA and $k$-dimensional shift
$u=(u_{1},\ldots,u_{k})\in\mathbb{Z}^{k}$ we have

$\Pr\left[A^{{\mathrm{G,w}}}(X^{(b)},v)-A^{{\mathrm{G,w}}}\Big{(}X^{(b)},v+\sum_{i=1}^{k}u_{i}w_{i}\Big{)}\neq
u\right]\leq\delta\cdot|u|_{1},$

where $|u|_{1}$ denotes the $\ell_{1}$-norm of $u$ and the probability space
is as in Definition 6.1. In the context of the packed HSS application, this
will imply an error that scales with the $\ell_{1}$-norm of the output vector.

As DDL algorithms have a small but non-negligible error, it may be useful to
drive the error probability down using independent repetitions, where the
internal coins of the algorithm are picked independently but all other sources
of randomness are fixed. (This repetition comes at a price of additional
communication, since each instance produces different outputs.) For this
purpose, one can use a more refined version of Definition 6.1 in which the
probability space is only over the internal randomness of $A^{{\mathrm{G,w}}}$
and the probability bound $\delta$ should hold except with negligible
probability over all other random choices. The construction we present next
indeed satisfies this property.

####  6.1.2 $k$D-DDL from $k$D-LPHS

Our main solution to the $k$D-DDL problem is based on the non-cyclic variant
of $k$-dimensional LPHS from Definition 2.1 ($k$D-LPHS for short) that we
recall below.

Let $e_{i}$ denote the $i$th unit vector of length $k$. For a $k$-dimensional
string $x=x^{(k,b)}$, we denote by $x\lll e_{i}$ a non-cyclic shift of $x$ by
1 in the $i$th dimension (e.g., for $k=2$ and $i=1$, this corresponds to
chopping the top row and adding a random row on the bottom). In the following
we will use $\mathbb{Z}_{n}$ to denote the set of integers
$\\{0,1,\ldots,n-1\\}$ and will not use its group structure.

######  Definition 6.2 (Non-cyclic $k$D-LPHS).

Let $h:\Sigma_{b}^{\mathbb{Z}_{n}^{k}}\to\mathbb{Z}^{k}$ be a function. We say
that $h$ is a non-cyclic $(n,b,d,\delta)$ $k$D-LPHS if $h$ can be computed by
making $d$ adaptive queries (of the form $x[\beta_{1},\dots,\beta_{k}]$ for
$\beta_{i}\in\mathbb{Z}_{n}$) to a $k$-dimensional input
$x=x^{(k,b)}\in\Sigma_{b}^{\mathbb{Z}_{n}^{k}}$ and for every $i\in[k]$:

$\Pr_{x\in_{R}\Sigma_{b}^{\mathbb{Z}_{n}^{k}}}\left[h(x)\neq h(x\lll
e_{i})+e_{i}\right]\leq\delta.$

This naturally extends to a probabilistic $h\in_{R}\cal H$.

Given any non-cyclic $k$D-LPHS, we can construct a $k$D-DDL algorithm with
similar parameters. The transformation will not be perfect, but will induce
collision probability error that for sufficiently large group sizes $N$ will
be negligible.

######  Theorem 6.3 (From non-cyclic $k$D-LPHS to $k$D-DDL).

Let $k,n$ be positive integers and $N$ be a prime such that $N\geq n$. There
exists a black-box reduction that converts any $(n,b,d,\delta)$ non-cyclic
$k$D-LPHS to an $(N,b,d,\delta+d^{2}/N)$ $k$D-DDL algorithm. The DDLA is
query-restricted in the sense that the values
$\alpha,\beta_{1},\ldots,\beta_{k}$ for each generic query satisfy $\alpha=1$