Converse for Multi-Server Single-Message PIR with Side Information

Michael Christoph Gastpar, Su Li
2020
Article de conférence

Multi-server single-message private information retrieval is studied in the presence of side information. In this problem, K independent messages are replicatively stored at N non-colluding servers. The user wants to privately download one message from the servers without revealing the index of the message to any of the servers, leveraging its M side information messages. We assume that the servers only know the number of the side information messages available at the user but not their indices. We prove a converse bound on the maximum download rates, which coincides with the known achievability scheme proposed by Kadhe et. al.. Hence, we characterize the capacity for this problem, which is (1 +1/N+ 1/N 2 + · · · + N⌈1K/M+1⌉ -1 ) -1 . The proof leverages a novel concept that we call virtual side information, which, for a fixed query and any message, identifies the side information that would be needed in order to recover that message.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Michael Christoph Gastpar, Su Li
2020
Article de conférence

Résumé

Official source

https://infoscience.epfl.ch/record/285901?ln=fr

À propos de ce résultat

Concepts associés (9)

Concepts associés

Chargement

Publications associées (3)

Chargement

Publications associées

Chargement

Asymétrie d'information

Une asymétrie d'information est une situation où, sur un marché, les agents économiques qui contractent ou échangent ne sont pas sur un pied d'égalité en termes d'informations, l'un des deux agents

Message

Un message est un ensemble de signes. Il implique donc un codage par l'émetteur, et un décodage par le récepteur (d'où la nécessité d'un code commun). La théorie de l'information fut mise au point po

Download

In computer networks, download means to receive data from a remote system, typically a server such as a web server, an server, an email server, or other similar systems. This contrasts with uploadi

Single-server Multi-user Private Information Retrieval with Side Information

Michael Christoph Gastpar, Su Li

In the problem of private information retrieval with side information, a single user wants to recover one of the K independent messages which are stored at one or multiple servers. The user initially has a subset of messages as side information. The goal of the user is to retrieve the demand message by using minimum number of transmissions (R∗) from the server(s) to the user under the condition that the index of the demand message should not be inferred by the server. We introduce the multi-user variant into this problem, where each user wants to retrieve one message and has a subset of messages as side information. In this paper, we study the special cases where all users want to retrieve one common message from a single server, but each user has different side information messages. We show that the optimal coding scheme can be constructed by first optimally partitioning the messages and then generating MDS codes separately in each subset of messages in the partition. We determine the R∗ , propose algorithms to compute R∗ , and construct optimal linear coding schemes with complexity polynomial in K (but exponential in the number of side information messages).

2018

Chargement

Single-server Multi-message Private Information Retrieval with Side Information

Michael Christoph Gastpar, Su Li

We study the problem of single-server multi-message private information retrieval with side information. One user wants to recover N out of K independent messages which are stored at a single server. The user initially possesses a subset of M messages as side information. The goal of the user is to download the N demand messages while not leaking any information about the indices of these messages to the server. In this paper, we characterize the minimum number of required transmissions for linear codes. Moreover, we present an optimal coding scheme which enables the user to download the demand messages and preserves the privacy of their indices by using linear codes. Additionally, we show that the trivial MDS coding scheme with K - M transmissions is optimal if N > M or N-2 + N >= K - M. This means if one wishes to privately download more than the square-root of the number of files in the database, then one must effectively download the full database (minus the side information), irrespective of the amount of side information one has available.

IEEE2018

Chargement

Single-server Multi-message Private Information Retrieval with Side Information: the General Cases

Michael Christoph Gastpar, Su Li

The single-server multi-message private information retrieval with side information problem is studied for general cases. In this problem, K independent messages are stored at a single server. One user initially has M messages as side information and wants to download N demand messages while not leaking any information about the indices of demand messages to the server. In our previous work, we characterized the minimum number of required download bits and presented an achievability scheme for this problem with the constraint of linear codes. In this paper, we extend the results to general (non-linear) codes and present the closed-form expression for the minimum number of required download bits. Moreover, we show that linear coding schemes are sufficient to achieve the optimal (minimum) download bits. Additionally, we show that the trivial MDS coding scheme with K - M transmissions is optimal if N > M or N 2 +N ≥ K-M. This means if one wishes to privately download more than the square-root of the number of messages in the database, then one must effectively download the full database (minus the side information), irrespective of the amount of side information one has available.

IEEE2020

Chargement