Related papers: The Capacity of Semantic Private Information Retrieval with Colluding Servers

The Capacity of Semantic Private Information Retrieval with Colluding Servers

URL: http://arxiv.org/abs/2507.15818v1
Date: Mon, 21 Jul 2025 17:24:40 GMT
Title: The Capacity of Semantic Private Information Retrieval with Colluding Servers
Authors: Mohamed Nomeir, Alptug Aytekin, Sennur Ulukus,
Abstract summary: 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.
Score: 31.285983939625098
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of semantic private information retrieval (Sem-PIR) with $T$ colluding servers (Sem-TPIR), i.e., servers that collectively share user queries. In Sem-TPIR, the message sizes are different, and message retrieval probabilities by any user are not uniform. This is a generalization of the classical PIR problem where the message sizes are equal and message retrieval probabilities are identical. The earlier work on Sem-PIR considered the case of no collusions, i.e., the collusion parameter of $T=1$. In this paper, we consider the general problem for arbitrary $T < N$. We find an upper bound on the retrieval rate and design a scheme that achieves this rate, i.e., we derive the exact capacity of Sem-TPIR.

Related papers

Private Multiple Linear Computation: A Flexible Communication-Computation Tradeoff [27.511481199887978]
We consider the problem of private multiple linear computation (PMLC) over a replicated storage system with colluding and unresponsive constraints. We propose a novel PMLC scheme to establish a flexible tradeoff between communication costs and computational complexities.
arXiv Detail & Related papers (2024-04-14T07:07:08Z)
Private Aggregate Queries to Untrusted Databases [3.6209090009720155]
Private information retrieval (PIR) is a privacy-preserving cryptographic tool. Most PIR protocols require the client to know the exact row index of the intended database item. We build a novel information-theoretic PIR framework that permits a user to fetch the aggregated result.
arXiv Detail & Related papers (2024-03-20T04:35:21Z)
Prior Entanglement Exponentially Improves One-Server Quantum Private Information Retrieval for Quantum Messages [60.889483085250355]
We find an exponential gap in the communication complexities between the presence and absence of prior entanglement. We propose an efficient one-server one-round QPIR protocol with prior entanglement.
arXiv Detail & Related papers (2023-04-11T10:34: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)
On the Capacity of Quantum Private Information Retrieval from MDS-Coded and Colluding Servers [59.98425646542448]
In quantum private information retrieval, a user retrieves a classical file from multiple servers by downloading quantum systems without revealing the identity of the file. The capacity of QPIR from MDS-coded and colluding servers is studied for the first time.
arXiv Detail & Related papers (2021-06-28T13:48:22Z)
High-Rate Quantum Private Information Retrieval with Weakly Self-Dual Star Product Codes [16.23970875497387]
In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. In this paper, the QPIR setting is extended to allow for retrieval with high rate for any number of colluding servers $t$ with $1 leq tleq n-k$.
arXiv Detail & Related papers (2021-02-04T09:44:10Z)
Quantum Private Information Retrieval for Quantum Messages [71.78056556634196]
Quantum private information retrieval (QPIR) for quantum messages is the protocol in which a user retrieves one of the multiple quantum states from one or multiple servers without revealing which state is retrieved. We consider QPIR in two different settings: the blind setting, in which the servers contain one copy of the message states, and the visible setting, in which the servers contain the description of the message states.
arXiv Detail & Related papers (2021-01-22T10:28:32Z)
Quantum Private Information Retrieval from Coded and Colluding Servers [16.23970875497387]
In the quantum PIR (QPIR) setting, a user privately retrieves a classical file by receiving quantum information from the servers. In this paper, the QPIR setting is extended to account for maximum distance separable (MDS) coded servers. The rates achieved are better than those known or conjectured in the classical counterparts.
arXiv Detail & Related papers (2020-01-16T15:19:08Z)
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.