2026-07-22T22:31:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15623 2024-03-06T10:55:47Z ddc:004 open_access

Locality-Preserving Hashing for Shifts with Connections to Cryptography Boyle, Elette Dinur, Itai Gilboa, Niv Ishai, Yuval Keller, Nathan Klein, Ohad Sublinear algorithms metric embeddings shift finding discrete logarithm homomorphic secret sharing 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 is a (d,δ) 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) ≠ h(x ≪ 1) + 1] ≤ δ, where x is random and ≪ 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 δ = Õ(1/d²). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elette Boyle and Itai Dinur and Niv Gilboa and Yuval Ishai and Nathan Keller and Ohad Klein 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.27 urn:nbn:de:0030-drops-156231 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.27 eng https://creativecommons.org/licenses/by/4.0/legalcode