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

Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, 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.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. MAJOR revision.ITCS 2022
Keywords
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
History
Short URL
https://ia.cr/2022/028

CC BY

BibTeX

@misc{cryptoeprint:2022/028,
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{https://eprint.iacr.org/2022/028}},
url = {https://eprint.iacr.org/2022/028}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.