Loading...
Send to Friend
 Bookmark
 Review List
  1. Simple search
  2. Search result
  3. Optimal binary differential privacy via graphs

Optimal binary differential privacy via graphs

Torkamani, S ; Sharif University of Technology | 2024

82 Viewed
  1. Type of Document: Article
  2. DOI: 10.1109/JSAIT.2024.3384183
  3. Publisher: 2024
  4. Abstract:
  5. We present the notion of reasonable utility for binary mechanisms, which applies to all utility functions in the literature. This notion induces a partial ordering on the performance of all binary differentially private (DP) mechanisms. DP mechanisms that are maximal elements of this ordering are optimal DP mechanisms for every reasonable utility. By looking at differential privacy as a randomized graph coloring, we characterize these optimal DP in terms of their behavior on a certain subset of the boundary datasets we call a boundary hitting set. In the process of establishing our results, we also introduce a useful notion that generalizes DP conditions for binary-valued queries, which we coin as suitable pairs. Suitable pairs abstract away the algebraic roles of ɛ δ in the DP framework, making the derivations and understanding of our proofs simpler. Additionally, the notion of a suitable pair can potentially capture privacy conditions in frameworks other than DP and may be of independent interest. © 2020 IEEE
  6. Keywords:
  7. Graph theory ; Perturbation techniques ; Toys ; Condition ; Differential privacies ; Image color analysis ; Manufacturing industries ; Partial order ; Perturbation method ; Privacy ; Toy manufacturing industry ; Upper Bound ; Utility functions ; Information theory
  8. Source: IEEE Journal on Selected Areas in Information Theory ; Volume 5 , 2024 , Pages 162-174 ; 26418770 (ISSN)
  9. URL: https://ieeexplore.ieee.org/document/10497099