The Asymptotic Capacity of Byzantine Symmetric Private Information Retrieval and Its Consequences

• URL: http://arxiv.org/abs/2501.17124v1
• Date: Tue, 28 Jan 2025 18:14:55 GMT
• Title: The Asymptotic Capacity of Byzantine Symmetric Private Information Retrieval and Its Consequences
• Authors: Mohamed Nomeir, Alptug Aytekin, Sennur Ulukus,
• Abstract summary: We consider the problem of finding the capacity of symmetric private information retrieval (SPIR) with $B$ Byzantine servers.<n>We define Byzantine servers, inspired by citebyzantine_tpir, as the servers that can share everything, before and after the scheme initiation.
• Score: 31.285983939625098
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of finding the asymptotic capacity of symmetric private information retrieval (SPIR) with $B$ Byzantine servers. Prior to finding the capacity, a definition for the Byzantine servers is needed since in the literature there are two different definitions. In \cite{byzantine_tpir}, where it was first defined, the Byzantine servers can send any symbol from the storage, their received queries and some independent random symbols. In \cite{unresponsive_byzantine_1}, Byzantine servers send any random symbol independently of their storage and queries. It is clear that these definitions are not identical, especially when \emph{symmetric} privacy is required. To that end, we define Byzantine servers, inspired by \cite{byzantine_tpir}, as the servers that can share everything, before and after the scheme initiation. In this setting, we find an upper bound, for an infinite number of messages case, that should be satisfied for all schemes that protect against this setting and develop a scheme that achieves this upper bound. Hence, we identify the capacity of the problem.

Related papers

• Rethinking Byzantine Robustness in Federated Recommendation from Sparse Aggregation Perspective [65.65471972217814]
  federated recommendation (FR) based on federated learning (FL) emerges, keeping the personal data on the local client and updating a model collaboratively.<n>FR has a unique sparse aggregation mechanism, where the embedding of each item is updated by only partial clients, instead of full clients in a dense aggregation of general FL.<n>In this paper, we reformulate the Byzantine robustness under sparse aggregation by defining the aggregation for a single item as the smallest execution unit.<n>We propose a family of effective attack strategies, named Spattack, which exploit the vulnerability in sparse aggregation and are categorized along the adversary's knowledge and capability.
  arXiv  Detail & Related papers  (2025-01-06T15:19:26Z)
• Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum $X$-Secure $B$-Byzantine $E$-Eavesdropped $U$-Unresponsive $T$-Colluding PIR? [31.285983939625098]
  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)
• Understanding Byzantine Robustness in Federated Learning with A Black-box Server [47.98788470469994]
  Federated learning (FL) becomes vulnerable to Byzantine attacks where some of participators tend to damage the utility or discourage the convergence of the learned model. Previous works propose to apply robust rules to aggregate updates from participators against different types of Byzantine attacks. In practice, FL systems can involve a black-box server that makes the adopted aggregation rule inaccessible to participants, which can naturally defend or weaken some Byzantine attacks.
  arXiv  Detail & Related papers  (2024-08-12T10:18:24Z)
• Quantum $X$-Secure $B$-Byzantine $T$-Colluding Private Information Retrieval [31.285983939625098]
  We consider the problems arising from the presence of Byzantine servers in a quantum private information retrieval (QPIR) setting. We show that quantum Byzantine servers have more capabilities than their classical counterparts due to the possibilities created by quantum encoding procedures.
  arXiv  Detail & Related papers  (2024-01-30T18:44:41Z)
• Practical Differentially Private and Byzantine-resilient Federated Learning [17.237219486602097]
  We use our version of differentially private gradient descent (DP-SGD) algorithm to preserve privacy. We leverage the random noise to construct an aggregation that effectively rejects many existing Byzantine attacks.
  arXiv  Detail & Related papers  (2023-04-15T23:30:26Z)
• A Robust Classification Framework for Byzantine-Resilient Stochastic Gradient Descent [3.5450828190071655]
  This paper proposes a Robust Gradient Classification Framework (RGCF) for Byzantine fault tolerance in distributed gradient descent. RGCF is not dependent on the number of workers; it can scale up to training instances with a large number of workers without a loss in performance.
  arXiv  Detail & Related papers  (2023-01-16T10:40:09Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  We consider a distributed reinforcement learning setting where multiple agents explore the environment and communicate their experiences through a central server. $alpha$-fraction of agents are adversarial and can report arbitrary fake information. We seek to identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents.
  arXiv  Detail & Related papers  (2022-06-01T00:44:53Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
  arXiv  Detail & Related papers  (2021-03-30T13:55:11Z)
• Byzantine-Robust Decentralized Stochastic Optimization over Static and Time-Varying Networks [25.15075119957447]
  We consider the Byzantine-robust optimization problem defined over decentralized static and time-varying networks. Some of the agents are unreliable due to data corruptions, equipment failures or cyber-attacks. Our key idea to handle the Byzantine attacks is to formulate a total variation (TV) norm-penalized approximation of the Byzantine-free problem. We prove that the proposed method reaches a neighborhood of the Byzantine-free optimal solution, and the size of neighborhood is determined by the number of Byzantine agents and the network topology.
  arXiv  Detail & Related papers  (2020-05-12T04:18:39Z)
• Federated Variance-Reduced Stochastic Gradient Descent with Robustness to Byzantine Attacks [74.36161581953658]
  This paper deals with distributed finite-sum optimization for learning over networks in the presence of malicious Byzantine attacks. To cope with such attacks, most resilient approaches so far combine gradient descent (SGD) with different robust aggregation rules. The present work puts forth a Byzantine attack resilient distributed (Byrd-) SAGA approach for learning tasks involving finite-sum optimization over networks.
  arXiv  Detail & Related papers  (2019-12-29T19:46:03Z)

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.