Locality-Preserving Hashing for Shifts with Connections to Cryptography

• Published in: arXiv.org 2022-01
• Main Authors: Boyle, Elette, Dinur, Itai, Gilboa, Niv, Ishai, Yuval, Keller, Nathan, Klein, Ohad
• Format: Article
• Language: English
• Subjects: Cryptography; Encryption; Hash based algorithms
• ISSN: 2331-8422

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.