Paper 2026/2788
Differentially Private Distance-Sensitive Representations for General Metrics
Abstract
A distance-sensitive set representation stores a set $S$ from a metric space $(U,d)$ and answers queries of the form "is some element of $S$ within distance $r$ of $q$?''. Existing differentially private constructions are confined to Hamming space, because they route the query through a signature map built for that metric. We give a framework that removes this restriction. The released object records only the occupancy of a fixed public partition of $U$, so privacy transfers unchanged from an off-the-shelf private membership structure, and the entire metric dependence collapses into one packing quantity, the straddle number $\kappa$: the largest number of cells a ball of radius $r$ can meet. Any metric admitting a partition of width at most $(c-1)r$ and straddlenumber $\kappa$ then has an $\varepsilon$-differentially private $(c,r)$-representation with $\varepsilon =\ln(2\kappa/\alpha)$ in $O(k\log(\kappa/\alpha))$ bits. Instantiating $\kappa$ gives matching upper and lower bounds in $\ell_\infty$ for partition-based constructions ($\varepsilon=O(\log d)$ at $c=\Theta(d)$, against $\varepsilon=\Omega(d)$ at constant $c$), and a randomized, dimension-free construction for every $\ell_p$ (one probe and $\varepsilon=\ln(2/\alpha)$ regardless of $d$) at the cost of a weaker, non-oblivious guarantee whose price is exactly this $\log d$ gap. For metrics available only through a distance oracle, we build the partition from a public net and a public navigable graph, and show that greedy search on that graph both locates and enumerates the cells a query must probe; on a $\lambda$-doubling metric this gives $\varepsilon\le 5\ln\lambda+\ln(2/\alpha)$. We further show that the per-query form of the guarantee is forced rather than chosen: any representation correct on all queries simultaneously requires $\varepsilon\ge\ln M+\ln(1/\alpha)-O(1)$ for $M$ the packing number of the whole space, and on doubling metrics this is achievable up to an additive $O(dim_D\log\frac{c}{c-1})$. Finally, the space bound is optimal in $k$ and $\alpha$.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- differential privacydistance-sensitive filtersnavigable graphsnear-neighbor search
- Contact author(s)
- pcesaretti @ gradcenter cuny edu
- History
- 2026-11-10: revised
- 2026-11-05: received
- See all versions
- Short URL
- https://ia.cr/2026/2788
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2788,
author = {Paul Cesaretti},
title = {Differentially Private Distance-Sensitive Representations for General Metrics},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2788},
year = {2026},
url = {https://eprint.iacr.org/2026/2788}
}