Paper 2026/2788

Differentially Private Distance-Sensitive Representations for General Metrics

Paul Cesaretti, CUNY Graduate Center
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.