### Lower Bounds for Oblivious Near-Neighbor Search

Kasper Green Larsen, Tal Malkin, Omri Weinstein, and Kevin Yeo

##### Abstract

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search ($\mathsf{ANN}$) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for $\mathsf{ANN}$. This is the first super-logarithmic $\mathit{unconditional}$ lower bound for $\mathsf{ANN}$ against general (non black-box) data structures. We also show that any oblivious $\mathit{static}$ data structure for decomposable search problems (like $\mathsf{ANN}$) can be obliviously dynamized with $O(\log n)$ overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
oblivious RAMlower boundnear-neighbors
Contact author(s)
History
Short URL
https://ia.cr/2019/377

CC BY

BibTeX

@misc{cryptoeprint:2019/377,
author = {Kasper Green Larsen and Tal Malkin and Omri Weinstein and Kevin Yeo},
title = {Lower Bounds for Oblivious Near-Neighbor Search},
howpublished = {Cryptology ePrint Archive, Paper 2019/377},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/377}},
url = {https://eprint.iacr.org/2019/377}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.