Storage-Rate Trade-off in A-XPIR

• URL: http://arxiv.org/abs/2601.14202v1
• Date: Tue, 20 Jan 2026 18:04:49 GMT
• Title: Storage-Rate Trade-off in A-XPIR
• Authors: Mohamed Nomeir, Sennur Ulukus,
• Abstract summary: We consider the storage problem in an asymmetric $X$-secure private information retrieval setting.<n>We focus on the trade-off region between the average storage at the servers and the average download cost.
• Score: 43.77138822870302
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the storage problem in an asymmetric $X$-secure private information retrieval (A-XPIR) setting. The A-XPIR setting considers the $X$-secure PIR problem (XPIR) when a given arbitrary set of servers is communicating. We focus on the trade-off region between the average storage at the servers and the average download cost. In the case of $N=4$ servers and two non-overlapping sets of communicating servers with $K=2$ messages, we characterize the achievable region and show that the three main inequalities compared to the no-security case collapse to two inequalities in the asymmetric security case. In the general case, we derive bounds that need to be satisfied for the general achievable region for an arbitrary number of servers and messages. In addition, we provide the storage and retrieval scheme for the case of $N=4$ servers with $K=2$ messages and two non-overlapping sets of communicating servers, such that the messages are not replicated (in the sense of a coded version of each symbol) and at the same time achieve the optimal achievable rate for the case of replication. Finally, we derive the exact capacity for the case of asymmetric security and asymmetric collusion for $N=4$ servers, with the communication links $\{1,2\}$ and $\{3,4\}$, which splits the servers into two groups, i.e., $g=2$, and with the collusion links $\{1,3\}$, $\{2,4\}$, as $C=\frac{1}{3}$. More generally, we derive a capacity result for a certain family of asymmetric collusion and asymmetric security cases.

Related papers

• Multi-Agent Stage-wise Conservative Linear Bandits [2.2557806157585834]
  We study the linear bandit problem in a multi-agent networked setting.<n>Agents must satisfy stage-wise conservative constraints.<n>We propose MA-SCLUCB, an episodic algorithm alternating between action selection and consensus-building phases.
  arXiv  Detail & Related papers  (2025-10-01T07:29:18Z)
• The Capacity of Semantic Private Information Retrieval with Colluding Servers [31.285983939625098]
  We study the problem of semantic private information retrieval (Sem-PIR) with $T$ colluding servers (Sem-TPIR)<n>In Sem-TPIR, the message sizes are different, and message retrieval probabilities by any user are not uniform.<n>This is a generalization of the classical PIR problem where the message sizes are equal and message retrieval probabilities are identical.
  arXiv  Detail & Related papers  (2025-07-21T17:24:40Z)
• Extending Asynchronous Byzantine Agreement with Crusader Agreement [23.27199615640474]
  We present a new reduction from multivalued BA to binary BA.<n>As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $ell$-bit inputs.
  arXiv  Detail & Related papers  (2025-02-04T13:44:41Z)
• Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum $X$-Secure $B$-Byzantine $E$-Eavesdropped $U$-Unresponsive $T$-Colluding PIR? [40.207696410490136]
  We consider the quantum emphsymmetric private information retrieval problem in a system with $N$ databases and $K$ messages.<n>In the first model, there are $mathcalE$ eavesdropped links in the uplink direction (the direction from the user to the $N$ servers)<n>In the second model, we consider the case with Byzantine servers that can coordinate to devise a plan to harm the privacy and security of the system together with static eavesdroppers.
  arXiv  Detail & Related papers  (2024-12-09T18:17:24Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
  arXiv  Detail & Related papers  (2024-05-09T17:40:09Z)
• Sharing nonlocality in a network using the quantum violation of chain network inequality [0.9948874862227255]
  Based on the quantum violation of suitable $n$-local inequality in a star network for arbitrary $m$ inputs, we demonstrate the sharing of nonlocality in the network. We consider two different types of sharing of nonlocality in the network.
  arXiv  Detail & Related papers  (2023-11-08T06:50:41Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  We consider the randomized communication complexity of the distributed $ell_p$-regression problem in the coordinator model. For $p = 2$, i.e., least squares regression, we give the first optimal bound of $tildeTheta(sd2 + sd/epsilon)$ bits. For $p in (1,2)$,we obtain an $tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound.
  arXiv  Detail & Related papers  (2023-07-11T08:51:53Z)
• A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
  We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
  arXiv  Detail & Related papers  (2022-07-07T06:16:19Z)
• SwiftAgg+: Achieving Asymptotically Optimal Communication Load in Secure Aggregation for Federated Learning [83.94234859890402]
  SwiftAgg+ is a novel secure aggregation protocol for federated learning systems. A central server aggregates local models of $NinmathbbN$ distributed users, each of size $L in mathbbN$, trained on their local data, in a privacy-preserving manner.
  arXiv  Detail & Related papers  (2022-03-24T13:12:23Z)
• Information Theoretic Secure Aggregation with User Dropouts [56.39267027829569]
  A server wishes to learn and only learn the sum of the inputs of a number of users while some users may drop out (i.e., may not respond) We consider the following minimal two-round model of secure aggregation.
  arXiv  Detail & Related papers  (2021-01-19T17:43:48Z)
• Capacity of Quantum Private Information Retrieval with Colluding Servers [71.78056556634196]
  Quantum private information retrieval (QPIR) is a protocol in which a user retrieves one of multiple files from non-communicating servers. As variants of QPIR with stronger security requirements, symmetric QPIR is a protocol in which no other files than the target file are leaked to the user. We construct a capacity-achieving QPIR protocol by the stabilizer formalism and prove the optimality of our protocol.
  arXiv  Detail & Related papers  (2020-01-13T18:12:20Z)

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.