**Locality-Preserving Hashing for Shifts with Connections to Cryptography**

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

**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)$ {\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.

**Category / Keywords: **foundations / discrete logarithm, sublinear algorithms, homomorphic secret sharing

**Original Publication**** (with major differences): **ITCS 2022

**Date: **received 9 Jan 2022, last revised 9 Jan 2022

**Contact author: **elette boyle at idc ac il, dinuri at cs bgu ac il, gilboan at bgu ac il, yuvali at cs technion ac il, nathan keller27 at gmail com, ohadkel at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20220110:075132 (All versions of this report)

**Short URL: **ia.cr/2022/028

[ Cryptology ePrint archive ]