论文标题
单人私有私人信息检索的线性容量以及附带信息
The Linear Capacity of Single-Server Individually-Private Information Retrieval with Side Information
论文作者
论文摘要
本文考虑了单个服务器单独私人信息检索以及附带信息（IPIR）的问题。在此问题中，有一个远程服务器存储$ K $消息的数据集，并且有一个用户最初知道这些消息的$ M $，并且想检索属于数据集的$ d $其他消息。用户的目标是通过从服务器中下载最少信息来检索$ d $所需的消息，同时又显示有关单个消息是否是$ d $所需消息之一的信息。在这项工作中，我们专注于线性iPir计划，即用户仅下载服务器原始消息的线性组合的IPIR计划。我们证明了所有$ k，d，m $的线性ipir方案的下载率的相反限制，并显示了所有$ k，d，m $符合某种可划分条件的实现性。我们的结果表征了IPIR的线性容量，该线性容量定义为所有线性IPIR计划的最大下载率，其范围为$ k，d，m $。
This paper considers the problem of single-server Individually-Private Information Retrieval with side information (IPIR). In this problem, there is a remote server that stores a dataset of $K$ messages, and there is a user that initially knows $M$ of these messages, and wants to retrieve $D$ other messages belonging to the dataset. The goal of the user is to retrieve the $D$ desired messages by downloading the minimum amount of information from the server while revealing no information about whether an individual message is one of the $D$ desired messages. In this work, we focus on linear IPIR schemes, i.e., the IPIR schemes in which the user downloads only linear combinations of the original messages from the server. We prove a converse bound on the download rate of any linear IPIR scheme for all $K,D,M$, and show the achievability of this bound for all $K,D,M$ satisfying a certain divisibility condition. Our results characterize the linear capacity of IPIR, which is defined as the maximum achievable download rate over all linear IPIR schemes, for a wide range of values of $K,D,M$.
