We study the problem of pliable private information retrieval with side information (PPIR-SI) for the single server case. In PPIR, the messages are partitioned into nonoverlapping classes and stored in a number of noncolluding databases. The user wishes to retrieve any one message from a desired class while revealing no information about the desired class identity to the databases. In PPIR-SI, the user has prior access to some side information in the form of messages from different classes and wishes to retrieve any one new message from a desired class, i.e., the message is not included in the side information set, while revealing no information about the desired class to the databases. We characterize the capacity of (linear) single-server PPIR-SI for the case where the user’s side information is unidentified, i.e., the user is oblivious of the identities of its side information messages and the database structure. We term this case PPIR-USI. Surprisingly, we show that having side information, in PPIR-USI, is disadvantageous, in terms of the download rate, compared to PPIR.

We formulate a new variant of the private information retrieval (PIR) problem where the user is pliable, i.e., interested in any message from a desired subset of the available dataset, denoted as pliable private information retrieval (PPIR). We consider the setup where a dataset consisting of f messages is replicated in n noncolluding databases and classified into Γ classes. For this setup, the user wishes to retrieve any λ ≥ 1 messages from multiple desired classes, while revealing no information about the identity of the desired classes to the databases. We term this problem multi-message PPIR (M-PPIR) and introduce the single-message PPIR (PPIR) problem as an elementary special case of M-PPIR. We first derive converse bounds on the M-PPIR download rate, followed by achievable schemes. As a result, we show that the PPIR capacity for f messages and Γ classes matches the PIR capacity with n noncolluding databases and Γ messages. Thus, enabling flexibility, i.e., pliability, where privacy is only guaranteed for classes, but not for messages as in classical PIR, allows to trade-off privacy versus download rate. A similar insight is shown to hold for the general case of M-PPIR.

Private computation in a distributed storage system (DSS) is a generalization of the private information retrieval (PIR) problem. In such a setting, a user wishes to compute a function of$f$messages stored in$n$noncolluding coded databases, i.e., databases storing data encoded with an$[n,k]$linear storage code, while revealing no information about the desired function to the databases. We consider the problem of private linear computation (PLC) for coded databases. In PLC, a user wishes to compute a linear combination over the$f$messages while keeping the coefficients of the desired linear combination hidden from the databases. For a DSS setup where data is stored using a code from a particular family of linear storage codes, we derive an outer bound on the PLC rate, which is defined as the ratio of the desired amount of information and the total amount of downloaded information. In particular, the proposed converse is valid for any number of messages and linear combinations, and depends on the rank of the coefficient matrix obtained from all linear combinations. Further, we present a PLC scheme with rate equal to the outer bound and hence settle the PLC capacity for the considered class of linear storage codes. Interestingly, the PLC capacity matches the maximum distance separable coded capacity of PIR for the considered class of linear storage codes.

We consider the problem of private polynomial computation (PPC) from a distributed storage system (DSS). In such setting a user wishes to compute a multivariate polynomial of degree at most$g$over$f$variables (or messages) stored in$n$noncolluding coded databases, i.e., databases storing data encoded with an$[n,k]$linear storage code, while revealing no information about the desired polynomial evaluation to the databases. For a DSS setup where data is stored using linear storage codes, we derive an outer bound on the PPC rate, which is defined as the ratio of the (minimum) desired amount of information and the total amount of downloaded information, and construct two novel PPC schemes. In the first scheme, we consider Reed-Solomon coded databases with Lagrange encoding, which leverages ideas from recently proposed star-product private information retrieval and Lagrange coded computation. The second scheme considers the special case of coded databases with systematic Lagrange encoding. Both schemes yield improved rates, while asymptotically, as$f\rightarrow \infty $, the systematic scheme gives a significantly better computation retrieval rate compared to all known schemes up to some storage code rate that depends on the maximum degree of the candidate polynomials.

We study the problem of strong coordination of the actions of two nodes X and Y that communicate over a discrete memoryless channel (DMC) such that the actions follow a prescribed joint probability distribution. We propose two novel random coding schemes and a polar coding scheme for this noisy strong coordination problem, and derive inner and outer bounds for the respective strong coordination capacity region. The first scheme is a joint coordination-channel encoding scheme that utilizes the randomness provided by the communication channel to reduce the amount of local randomness required to generate the sequence of actions at Node Y. Based on this random coding scheme, we provide a characterization of the capacity region for a special case of the noisy strong coordination setup, namely, when the DMC is a deterministic channel. The second scheme exploits separate coordination and channel encoding where local randomness is extracted from the channel after decoding. Moreover, by leveraging the random coding results for this problem, we present an example in which the proposed joint encoding scheme is able to strictly outperform the separate encoding scheme in terms of achievable communication rate for the same amount of injected randomness into both systems. Thus, we establish the sub-optimality of the separation of strong coordination and channel encoding with respect to the communication rate over the DMC in this problem. Finally, the third scheme is a joint coordination-channel polar coding scheme for strong coordination. We show that polar codes are able to achieve the established inner bound to the strong noisy coordination capacity region and thus provide a constructive alternative to a random coding proof. Our polar coding scheme also offers a constructive solution to a channel simulation problem where a DMC and shared randomness are employed together to simulate another DMC.

We consider private polynomial computation (PPC) over noncolluding coded databases. In such a setting a user wishes to compute a multivariate polynomial of degree at most g over f variables (or messages) stored in multiple databases while revealing no information about the desired polynomial to the databases. We construct two novel PPC schemes, where the first is a generalization of our previous work in private linear computation for coded databases. In this scheme we consider Reed-Solomon coded databases with Lagrange encoding, which leverages ideas from recently proposed star-product private information retrieval and Lagrange coded computation. The second scheme considers the special case of coded databases with systematic Lagrange encoding. Both schemes yield improved rates compared to the best known schemes from the literature for a small number of messages, while in the asymptotic case the rates match.

We consider the problem of private computation (PC) in a distributed storage system. In such a setting a user wishes to compute a function of f messages replicated across n noncolluding databases, while revealing no information about the desired function to the databases. We provide an information-theoretically accurate achievable PC rate, which is the ratio of the smallest desired amount of information and the total amount of downloaded information, for the scenario of nonlinear computation. For a large message size the rate equals the PC capacity, i.e., the maximum achievable PC rate, when the candidate functions are the f independent messages and one arbitrary nonlinear function of these. When the number of messages grows, the PC rate approaches an outer bound on the PC capacity. As a special case, we consider private monomial computation (PMC) and numerically compare the achievable PMC rate to the outer bound for a finite number of messages.

We study the problem of private function retrieval (PFR) in a distributed storage system. In PFR the user wishes to retrieve a linear combination of M messages stored in non-colluding (N, K) MDS coded databases while revealing no information about the coefficients of the intended linear combination to any of the individual databases. We present an achievable scheme for MDS coded PFR with a rate that matches the capacity for coded private information retrieval derived recently, R = (1+Rc+Rc2+...+RcM-1)-1=[(1-Rc)/(1-RcM)], where Rc=[K/N] is the rate of the MDS code.

We study the problem of strong coordination of actions of two agents X and Y that communicate over a noisy communication channel such that the actions follow a given joint probability distribution. We propose two novel schemes for this noisy strong coordination problem, and derive inner bounds for the underlying strong coordination capacity region. The first scheme is a joint coordination-channel coding scheme that utilizes the randomness provided by the communication channel to reduce the local randomness required in generating the action sequence at agent Y. The second scheme exploits separate coordination and channel coding where local randomness is extracted from the channel after decoding. Finally, we present an example in which the joint scheme is able to outperform the separate scheme in terms of coordination rate.