Welcome to the resource topic for 2022/028
Title:
Locality-Preserving Hashing for Shifts with Connections to Cryptography
Authors: Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, 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.
ePrint: https://eprint.iacr.org/2022/028
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .