Private Information Retrieval With Arbitrary Privacy Requirements for Graph-Based Storage

• URL: http://arxiv.org/abs/2605.10879v1
• Date: Mon, 11 May 2026 17:27:33 GMT
• Title: Private Information Retrieval With Arbitrary Privacy Requirements for Graph-Based Storage
• Abstract summary: We reformulate the definition of privacy in the private information retrieval problem to accommodate flexible privacy requirements.<n>We focus on graph-replicated PIR, with a generalized privacy requirement, instead of requiring all messages to be private from all servers.
• Score: 39.20087907351314
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We reformulate the definition of privacy in the private information retrieval (PIR) problem to accommodate flexible privacy requirements. We focus on graph-replicated PIR, with a generalized privacy requirement, instead of requiring all messages to be private from all servers, during retrieval. Towards this, we define a privacy requirement set for each server, which can be an arbitrary subset of all message indices, as long as the stored message indices are in their privacy requirement set. Since both the storage and privacy requirement sets have many possibilities, we focus on two specific storage settings, namely the path and cyclic graphs. We consider several privacy settings for each of them, which are not necessarily the same, to give different examples for privacy sets. Of particular interest are the privacy sets that comprise the indices of messages stored at servers within a neighborhood range. The neighborhood range parameter allows a transition from the recently introduced local PIR [1] to the standard graph-replicated PIR. In these cases, we derive bounds on the capacity or find the exact capacity.

Related papers

• Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results [39.20087907351314]
  We introduce the problem of private information retrieval (PIR) under arbitrary privacy requirements, in a graph-based storage system.<n>This formulation is motivated by the server storage limitations, abundance of data (messages) and heterogeneous data privacy requirements.<n>We derive general lower and upper bounds on the PIR capacity for general graphs, under certain privacy requirements.
  arXiv  Detail & Related papers  (2026-09-14T17:03:36Z)
• Local Private Information Retrieval for Graph-Based Replicated Systems [39.20087907351314]
  We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems.<n>In our proposed privacy setting, the user is concerned with hiding the message index from a particular server.<n>We coin this relaxed privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph.
  arXiv  Detail & Related papers  (2026-08-31T17:50:47Z)
• Differential Confounding Privacy and Inverse Composition [32.85314813605347]
  We introduce textitdifferential confounding privacy (DCP), a specialized form of the Pufferfish privacy framework.<n>We show that while DCP mechanisms retain privacy guarantees under composition, they lack the graceful compositional properties of DP.<n>We propose an textitInverse Composition (IC) framework, where a leader-follower model optimally designs a privacy strategy to achieve target guarantees.
  arXiv  Detail & Related papers  (2024-08-21T21:45:13Z)
• Mean Estimation Under Heterogeneous Privacy Demands [5.755004576310333]
  This work considers the problem of mean estimation, where each user can impose their own privacy level. The algorithm we propose is shown to be minimax optimal and has a near-linear run-time. Users with less but differing privacy requirements are all given more privacy than they require, in equal amounts.
  arXiv  Detail & Related papers  (2023-10-19T20:29:19Z)
• Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free [13.198689566654103]
  This work considers the problem of mean estimation under heterogeneous Differential Privacy constraints. The algorithm we propose is shown to be minimax optimal when there are two groups of users with distinct privacy levels.
  arXiv  Detail & Related papers  (2023-04-27T05:23:06Z)
• How Do Input Attributes Impact the Privacy Loss in Differential Privacy? [55.492422758737575]
  We study the connection between the per-subject norm in DP neural networks and individual privacy loss. We introduce a novel metric termed the Privacy Loss-Input Susceptibility (PLIS) which allows one to apportion the subject's privacy loss to their input attributes.
  arXiv  Detail & Related papers  (2022-11-18T11:39:03Z)
• Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
  We consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis. In this work, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person.
  arXiv  Detail & Related papers  (2022-09-08T22:43:50Z)
• Fully Adaptive Composition in Differential Privacy [53.01656650117495]
  Well-known advanced composition theorems allow one to query a private database quadratically more times than basic privacy composition would permit. We introduce fully adaptive composition, wherein both algorithms and their privacy parameters can be selected adaptively. We construct filters that match the rates of advanced composition, including constants, despite allowing for adaptively chosen privacy parameters.
  arXiv  Detail & Related papers  (2022-03-10T17:03:12Z)
• Single-Server Private Linear Transformation: The Individual Privacy Case [10.072633952908456]
  This paper considers the single-server Private Linear Transformation (PLT) problem with individual privacy guarantees. The goal is to minimize the download cost while keeping the identity of each message required for the computation individually private.
  arXiv  Detail & Related papers  (2021-06-09T17:12:04Z)
• PGLP: Customizable and Rigorous Location Privacy through Policy Graph [68.3736286350014]
  We propose a new location privacy notion called PGLP, which provides a rich interface to release private locations with customizable and rigorous privacy guarantee. Specifically, we formalize a user's location privacy requirements using a textitlocation policy graph, which is expressive and customizable. Third, we design a private location trace release framework that pipelines the detection of location exposure, policy graph repair, and private trajectory release with customizable and rigorous location privacy.
  arXiv  Detail & Related papers  (2020-05-04T04:25:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.