Locality-Preserving Hashing for Shifts with Connections to Cryptography
summary
Constructs a locality-preserving hash that reads D bits and achieves error delta ≈ 1/D^2 and proves that delta ≥ 1/D^2 via a birthday-paradox lower bound, so the one-dimensional trade-off is optimal. Techniques combine argmin longest-zero and a randomized walk based on Pollard's kangaroo/Kruskal count to get the upper bound. Builds a nearest-neighbor data structure for the shift metric, a location-sensitive encryption primitive, and HSS schemes with K-fold communication savings; gives a 2D construction with delta ≈ 1/D^{7/8} and open problems about optimal 2D and higher-D bounds.
AI-written summary · about
chapters (16)
- 0:00How to communicate a location?
- 0:25Distinguished object solution
- 0:40A better solution?
- 1:05Locality-Preserving Hashing for Shifts
- 2:49LPHS Variants
- 5:33Applications of LPHS
- 6:58Nearest-Neighbor Search for Shifts Goal
- 9:22Location-Sensitive Encryption
- 10:55Homomorphic Secret Sharing (HSS) • Analog of Homomorphic Encryption, on secret shares - Allows secure computation with low communication - Private information retrieval
- 13:09argmin LPHS ID
- 14:42Kruskal count card trick
- 16:52Optimal ID-LPHS
- 17:40How to build 2D LPHS?
- 19:12Our Work
- 19:53The allegedly optimal algorithm • Algorithm
- 21:33Open Problems
related talks
41mReducibility and Statistical-Computational Gaps from Secret Leakage
01h 10mDifferential Privacy: Fundamentals to Forefront II
01h 06mAlgorithms for the k-List Problems
19mSymmetric Cryptography 1
51mMultilinear Maps and Attacks II
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
44mCorrelation Intractability and SNARGs from Sub-exponential DDH
49mCollision-Resistance from Multi-Collision-Resistance