Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum $X$-Secure $B$-Byzantine $E$-Eavesdropped $U$-Unresponsive $T$-Colluding PIR?

• URL: http://arxiv.org/abs/2412.06728v1
• Date: Mon, 09 Dec 2024 18:17:24 GMT
• Title: Byzantine-Eavesdropper Alliance: How to Achieve Symmetric Privacy in Quantum $X$-Secure $B$-Byzantine $E$-Eavesdropped $U$-Unresponsive $T$-Colluding PIR?
• Authors: Mohamed Nomeir, Alptug Aytekin, Sennur Ulukus,
• Abstract summary: 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.
• Score: 31.285983939625098
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the quantum \emph{symmetric} private information retrieval (QSPIR) problem in a system with $N$ databases and $K$ messages, with $U$ unresponsive servers, $T$-colluding servers, and $X$-security parameter, under several fundamental threat models. In the first model, there are $\mathcal{E}_1$ eavesdropped links in the uplink direction (the direction from the user to the $N$ servers), $\mathcal{E}_2$ eavesdropped links in the downlink direction (the direction from the servers to the user), where $|\mathcal{E}_1|, |\mathcal{E}_2| \leq E$; we coin this eavesdropper setting as \emph{dynamic} eavesdroppers. We show that super-dense coding gain can be achieved for some regimes. In the second model, we consider the case with Byzantine servers, i.e., servers that can coordinate to devise a plan to harm the privacy and security of the system together with static eavesdroppers, by listening to the same links in both uplink and downlink directions. It is important to note the considerable difference between the two threat models, since the eavesdroppers can take huge advantage of the presence of the Byzantine servers. Unlike the previous works in SPIR with Byzantine servers, that assume that the Byzantine servers can send only random symbols independent of the stored messages, we follow the definition of Byzantine servers in \cite{byzantine_tpir}, where the Byzantine servers can send symbols that can be functions of the storage, queries, as well as the random symbols in a way that can produce worse harm to the system. In the third and the most novel threat model, we consider the presence of Byzantine servers and dynamic eavesdroppers together. We show that having dynamic eavesdroppers along with Byzantine servers in the same system model creates more threats to the system than having static eavesdroppers with Byzantine servers.

Related papers

• Storage-Rate Trade-off in A-XPIR [43.77138822870302]
  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.
  arXiv  Detail & Related papers  (2026-01-20T18:04:49Z)
• Trade-off in Estimating the Number of Byzantine Clients in Federated Learning [51.015234193544636]
  Federated learning is vulnerable to Byzantine clients that can send any erroneous signals.<n>We show that underestimation ($hatfge f$) can lead to arbitrarily poor performance for both aggregators and federated learning.<n>All these optimal bounds are proportional to $hatf/(n-f-hatf)$ with $n$ clients, which monotonically increases with larger $hatf$.
  arXiv  Detail & Related papers  (2025-10-06T02:01:56Z)
• The Asymptotic Capacity of Byzantine Symmetric Private Information Retrieval and Its Consequences [31.285983939625098]
  We consider the problem of finding the capacity of symmetric private information retrieval (SPIR) with $B$ Byzantine servers. We define Byzantine servers, inspired by citebyzantine_tpir, as the servers that can share everything, before and after the scheme initiation.
  arXiv  Detail & Related papers  (2025-01-28T18:14:55Z)
• Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement [1.77513002450736]
  It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $tn/2$ corruptions. We propose a compiler that transforms any pair of resilience-optimal Byzantine agreement protocols into one that is crypto-agnostic. Our results improve the state-of-the-art in bit complexity by at least two factors of $n$ and provide either early stopping (deterministic) or expected constant round complexity (randomized)
  arXiv  Detail & Related papers  (2024-10-15T23:44:29Z)
• 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)
• 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)
• 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)
• H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models [110.06476624089679]
  We introduce a novel approach for implementing the KV cache which significantly reduces its memory footprint. Our approach is based on the observation that a small portion of tokens contributes most of the value when computing attention scores. We propose Heavy Hitter (H$$O), a KV cache eviction policy that dynamically retains a balance of recent and H$$ tokens.
  arXiv  Detail & Related papers  (2023-06-24T20:11:14Z)
• 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)
• Tiered Reinforcement Learning: Pessimism in the Face of Uncertainty and Constant Regret [144.06550139857296]
  We propose a new learning framework that captures the tiered structure of many real-world user-interaction applications. We simultaneously maintain two policies $pitextO$ and $pitextE$. We show that if choosing Pessimistic Value It as the exploitation algorithm to produce $pitextE$, we can achieve a constant regret for risk-averse users.
  arXiv  Detail & Related papers  (2022-05-25T00:03:25Z)
• 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)

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.