Paper 2022/028

Locality-Preserving Hashing for Shifts with Connections to Cryptography

Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, and Ohad Klein


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.

Available format(s)
Publication info
Published elsewhere. Major revision. ITCS 2022
discrete logarithmsublinear algorithmshomomorphic secret sharing
Contact author(s)
elette boyle @ idc ac il
dinuri @ cs bgu ac il
gilboan @ bgu ac il
yuvali @ cs technion ac il
nathan keller27 @ gmail com
ohadkel @ gmail com
2022-01-10: received
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Itai Dinur and Niv Gilboa and Yuval Ishai and Nathan Keller and Ohad Klein},
      title = {Locality-Preserving Hashing for Shifts with Connections to Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2022/028},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.