License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.27
URN: urn:nbn:de:0030-drops-156231
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15623/
Boyle, Elette ;
Dinur, Itai ;
Gilboa, Niv ;
Ishai, Yuval ;
Keller, Nathan ;
Klein, Ohad
Locality-Preserving Hashing for Shifts with Connections to Cryptography
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 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.
BibTeX - Entry
@InProceedings{boyle_et_al:LIPIcs.ITCS.2022.27,
author = {Boyle, Elette and Dinur, Itai and Gilboa, Niv and Ishai, Yuval and Keller, Nathan and Klein, Ohad},
title = {{Locality-Preserving Hashing for Shifts with Connections to Cryptography}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {27:1--27:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15623},
URN = {urn:nbn:de:0030-drops-156231},
doi = {10.4230/LIPIcs.ITCS.2022.27},
annote = {Keywords: Sublinear algorithms, metric embeddings, shift finding, discrete logarithm, homomorphic secret sharing}
}
|
Keywords: |
|
Sublinear algorithms, metric embeddings, shift finding, discrete logarithm, homomorphic secret sharing |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
