Alex Sprintson

Sakshi Dang, Julia Lieb, Pedro Soto et al.

The matrix completion problem provides a unifying lens through which many fundamental problems in coding theory can be viewed. In this paper, we investigate Locally Recoverable Codes (LRCs) with Maximal Recoverability (MR) and Maximum Distance Profile (MDP) convolutional codes in the framework of matrix completion. In particular, we present techniques that are general enough to provide constructions for both types of codes. A common feature of our code constructions is the sparsity of their generator matrices and the property that a large number of the entries of the generator matrices are elements of a small subfield of a larger extension field.

Anoosheh Heidarzadeh, Alex Sprintson

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$.

Anoosheh Heidarzadeh, Alex Sprintson

This paper introduces the problem of Private Information Retrieval with Reusable and Single-use Side Information (PIR-RSSI). In this problem, one or more remote servers store identical copies of a set of $K$ messages, and there is a user that initially knows $M$ of these messages, and wants to privately retrieve one other message from the set of $K$ messages. The objective is to design a retrieval scheme in which the user downloads the minimum amount of information from the server(s) while the identity of the message wanted by the user and the identities of an $M_1$-subset of the $M$ messages known by the user (referred to as reusable side information) are protected, but the identities of the remaining $M_2=M-M_1$ messages known by the user (referred to as single-use side information) do not need to be protected. The PIR-RSSI problem reduces to the classical Private Information Retrieval (PIR) problem when ${M_1=M_2=0}$, and reduces to the problem of PIR with Private Side Information or PIR with Side Information when ${M_1\geq 1,M_2=0}$ or ${M_1=0,M_2\geq 1}$, respectively. In this work, we focus on the single-server setting of the PIR-RSSI problem. We characterize the capacity of this setting for the cases of ${M_1=1,M_2\geq 1}$ and ${M_1\geq 1,M_2=1}$, where the capacity is defined as the maximum achievable download rate over all PIR-RSSI schemes. Our results show that for sufficiently small values of $K$, the single-use side information messages can help in reducing the download cost only if they are kept private; and for larger values of $K$, the reusable side information messages cannot help in reducing the download cost.

Fatemeh Kazemi, Alex Sprintson

This paper focuses on the Private Linear Transformation (PLT) problem in the multi-server scenario. In this problem, there are $N$ servers, each of which stores an identical copy of a database consisting of $K$ independent messages, and there is a user who wishes to compute $L$ independent linear combinations of a subset of $D$ messages in the database while leaking no information to the servers about the identity of the entire set of these $D$ messages required for the computation. We focus on the setting in which the coefficient matrix of the desired $L$ linear combinations generates a Maximum Distance Separable (MDS) code. We characterize the capacity of the PLT problem, defined as the supremum of all achievable download rates, for all parameters $N, K, D \geq 1$ and $L=1$, i.e., when the user wishes to compute one linear combination of $D$ messages. Moreover, we establish an upper bound on the capacity of PLT problem for all parameters $N, K, D, L \geq 1$, and leveraging some known capacity results, we show the tightness of this bound in the following regimes: (i) the case when there is a single server (i.e., $N=1$), (ii) the case when $L=1$, and (iii) the case when $L=D$.

Anoosheh Heidarzadeh, Nahid Esmati, Alex Sprintson

This paper considers the single-server Private Linear Transformation (PLT) problem with individual privacy guarantees. In this problem, there is a user that wishes to obtain $L$ independent linear combinations of a $D$-subset of messages belonging to a dataset of $K$ messages stored on a single server. The goal is to minimize the download cost while keeping the identity of each message required for the computation individually private. The individual privacy requirement ensures that the identity of each individual message required for the computation is kept private. This is in contrast to the stricter notion of joint privacy that protects the entire set of identities of all messages used for the computation, including the correlations between these identities. The notion of individual privacy captures a broad set of practical applications. For example, such notion is relevant when the dataset contains information about individuals, each of them requires privacy guarantees for their data access patterns. We focus on the setting in which the required linear transformation is associated with a maximum distance separable (MDS) matrix. In particular, we require that the matrix of coefficients pertaining to the required linear combinations is the generator matrix of an MDS code. We establish lower and upper bounds on the capacity of PLT with individual privacy, where the capacity is defined as the supremum of all achievable download rates. We show that our bounds are tight under certain conditions.

Anoosheh Heidarzadeh, Nahid Esmati, Alex Sprintson

This paper introduces the problem of Private Linear Transformation (PLT) which generalizes the problems of private information retrieval and private linear computation. The PLT problem includes one or more remote server(s) storing (identical copies of) $K$ messages and a user who wants to compute $L$ independent linear combinations of a $D$-subset of messages. The objective of the user is to perform the computation by downloading minimum possible amount of information from the server(s), while protecting the identities of the $D$ messages required for the computation. In this work, we focus on the single-server setting of the PLT problem when the identities of the $D$ messages required for the computation must be protected jointly. We consider two different models, depending on whether the coefficient matrix of the required $L$ linear combinations generates a Maximum Distance Separable (MDS) code. We prove that the capacity for both models is given by $L/(K-D+L)$, where the capacity is defined as the supremum of all achievable download rates. Our converse proofs are based on linear-algebraic and information-theoretic arguments that establish connections between PLT schemes and linear codes. We also present an achievability scheme for each of the models being considered.

Nahid Esmati, Anoosheh Heidarzadeh, Alex Sprintson

We introduce the problem of Private Linear Transformation (PLT). This problem includes a single (or multiple) remote server(s) storing (identical copies of) $K$ messages and a user who wants to compute $L$ linear combinations of a $D$-subset of these messages by downloading the minimum amount of information from the server(s) while protecting the privacy of the entire set of $D$ messages. This problem generalizes the Private Information Retrieval and Private Linear Computation problems. In this work, we focus on the single-server case. For the setting in which the coefficient matrix of the required $L$ linear combinations generates a Maximum Distance Separable (MDS) code, we characterize the capacity -- defined as the supremum of all achievable download rates, for all parameters $K, D, L$. In addition, we present lower and/or upper bounds on the capacity for the settings with non-MDS coefficient matrices and the settings with a prior side information.

Nahid Esmati, Anoosheh Heidarzadeh, Alex Sprintson

This paper considers the single-server Private Linear Transformation (PLT) problem when individual privacy is required. In this problem, there is a user that wishes to obtain $L$ linear combinations of a $D$-subset of messages belonging to a dataset of $K$ messages stored on a single server. The goal is to minimize the download cost while keeping the identity of every message required for the computation individually private. The individual privacy requirement implies that, from the perspective of the server, every message is equally likely to belong to the $D$-subset of messages that constitute the support set of the required linear combinations. We focus on the setting in which the matrix of coefficients pertaining to the required linear combinations is the generator matrix of a Maximum Distance Separable code. We establish lower and upper bounds on the capacity of PLT with individual privacy, where the capacity is defined as the supremum of all achievable download rates. We show that our bounds are tight under certain divisibility conditions. In addition, we present lower bounds on the capacity of the settings in which the user has a prior side information about a subset of messages.

Anoosheh Heidarzadeh, Fatemeh Kazemi, Alex Sprintson

We study the role of coded side information in single-server Private Information Retrieval (PIR). An instance of the single-server PIR problem includes a server that stores a database of $K$ independently and uniformly distributed messages, and a user who wants to retrieve one of these messages from the server. We consider settings in which the user initially has access to a coded side information which includes a linear combination of a subset of $M$ messages in the database. We assume that the identities of the $M$ messages that form the support set of the coded side information as well as the coding coefficients are initially unknown to the server. We consider two different models, depending on whether the support set of the coded side information includes the requested message or not. We also consider the following two privacy requirements: (i) the identities of both the demand and the support set of the coded side information need to be protected, or (ii) only the identity of the demand needs to be protected. For each model and for each of the privacy requirements, we consider the problem of designing a protocol for generating the user's query and the server's answer that enables the user to decode the message they need while satisfying the privacy requirement. We characterize the (scalar-linear) capacity of each setting, defined as the ratio of the number of information bits in a message to the minimum number of information bits downloaded from the server over all (scalar-linear) protocols that satisfy the privacy condition. Our converse proofs rely on new information-theoretic arguments---tailored to the setting of single-server PIR and different from the commonly-used techniques in multi-server PIR settings. We also present novel capacity-achieving scalar-linear protocols for each of the settings being considered.

Swanand Kadhe, Anoosheh Heidarzadeh, Alex Sprintson et al.

Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way. In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRC), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in 'cooperative' locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols. In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.

Swanand Kadhe, Alex Sprintson

We consider the problem of designing codes for distributed storage that protect user data against eavesdroppers that can gain access to network links as well as individual nodes. Our goal is to achieve weak security (also known as block security) that requires that the eavesdroppers would not be able to decode individual files or combinations of a small number of files. The standard approach for achieving block security is to use a joint design scheme that consists of (inner) storage code and the (outer) coset code. However, jointly designing the codes requires that the user, who pre-processes and stores the files, should know the underlying storage code in order to design the (outer) linear transformation for achieving weak security. In many practical scenarios, such as storing the files on the third party cloud storage system, it may not be possible for the user to know the underlying storage code. In this work, we present universal schemes that separate the outer code design from the storage code design for minimum storage regenerating codes (MSR). Our schemes allow the independent design of the storage code and the outer code. Our schemes use small field size and can be used in a broad range of practical settings.

Swanand Kadhe, Brenden Garcia, Anoosheh Heidarzadeh et al.

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of $K$ independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of $M$ messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message without revealing its identity while minimizing the amount of data downloaded from the servers. We focus on achieving information-theoretic privacy in two scenarios: (i) the user wants to protect jointly its demand and side information; (ii) the user wants to protect only the information about its demand, but not the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is $K-M$ messages, and in the second scenario it is $\lceil \frac{K}{M+1}\rceil$ messages, which should be compared to $K$ messages, the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.

C. Jasson Casey, Andrew Sutton, Alex Sprintson

If simplicity is a key strategy for success as a network protocol OpenFlow is not winning. At its core OpenFlow presents a simple idea, which is a network switch data plane abstraction along with a control protocol for manipulating that abstraction. The result of this idea has been far from simple: a new version released each year, five active versions, com- plex feature dependencies, unstable version negotiation, lack of state machine definition, etc. This complexity represents roadblocks for network, software, and hardware engineers. We have distilled the core abstractions present in 5 existing versions of OpenFlow and refactored them into a simple API called tinyNBI. Our work does not provide high-level network abstractions (address pools, VPN maps, etc.), instead it focuses on providing a clean low level interface that supports the development of these higher layer abstractions. The goal of tinyNBI is to allow configuration of all existing OpenFlow abstractions without having to deal with the unique personalities of each version of OpenFlow or their level of support in target switches.