  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)$ {\em locality-preserving hash function for shifts} (LPHS) if: (1)
$h$ can be computed by (adaptively) querying $d$ bits of its input, and (2)
$\Pr [ h(x) \neq h(x \ll 1) + 1 ] \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.
