This work considers the problem of privately outsourcing the computation of a matrix product over a finite field${\mathbb {F}}_{q}$to$N$helper servers. These servers are considered to be honest but curious,i.e., they behave according to the protocol but will try to deduce information about the user’s data. Furthermore, any set of up to$X$servers is allowed to share their data. Previous works considered this collusion a hindrance and the download cost of the schemes increases with growing$X$. We propose to utilize such linkage between servers to the user’s advantage by allowing servers to cooperate in the computational task. This leads to a significant gain in the download cost for the proposed schemes. The gain naturally comes at the cost of increased communication load between the servers. Hence, the proposed cooperative schemes can be understood as outsourcing both computational cost and communication cost. Both information–theoretically secure and computationally secure schemes are considered, showing that allowing information leakage that is computationally hard to utilize will lead to further gains. The proposed server cooperation is then exemplified for specific secure distributed matrix multiplication (SDMM) schemes and linear private information retrieval (PIR). Similar ideas naturally apply to many other use cases as well, but not necessarily always with lowered costs.

The design of lattice coset codes for wiretap channels is considered. Bounds on the eavesdropper's correct decoding probability and information leakage are first revisited. From these bounds, it is explicit that both the information leakage and error probability are controlled by the average flatness factor of the eavesdropper's lattice, which we further interpret geometrically. It is concluded that the minimization of the (average) flatness factor of the eavesdropper's lattice leads to the study of well-rounded lattices, which are shown to be among the optimal in order to achieve these minima. Constructions of some well-rounded lattices are also provided.

A private proximity retrieval (PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance r from the user's record x. The user's privacy at each server is given by the fraction of the record x that is kept private. The distortion of a PPR scheme measures how accurately the user can calculate the identities of the desired files. We assume that each server stores a copy of the database. This paper studies protocols that offer trade-offs between perfect privacy and low computational complexity and storage.In this paper, this study is initiated. The work focuses on the case when the records are binary vectors together with the Hamming distance. In particular, for a given privacy level, we investigate the minimum number of servers that guarantee a prescribed distortion value. The collusions of pairs of servers as well as other distance measures are investigated.

In a user-private information retrieval (UPIR) scheme, a set of users collaborate to retrieve files from a database without revealing to observers which participant in the scheme requested the file. To achieve privacy, users retrieve files from the database in response to anonymous requests posted to message spaces; assuming that each message space can be accessed by a subset of the participants in the scheme. Privacy with respect to the database is easily achieved, but privacy with respect to coalitions of other users within the scheme is sensitive to the choice of incidence structure determining which users can access each message space. Earlier schemes were based on pairwise balanced designs and symmetric designs, and involved at most one step of message passing to retrieve a file. We propose a new class of UPIR schemes based on generalised quadrangles (GQs), which need up to two steps of message passing in each file retrieval. We introduce a new message passing protocol in which messages are encrypted. Even using this protocol, previously proposed schemes are compromised by finite coalitions of users. We construct a family of GQ-UPIR schemes which maintain privacy with high probability even when $$O(n^{1/2-\epsilon })$$ users collude, where n is the total number of users in the scheme. We also show that a UPIR scheme based on any family of generalised quadrangles is secure against coalitions of $$O(n^{1/4-\epsilon })$$ users.

Private information retrieval (PIR) schemes for coded storage with colluding servers are presented, which are not restricted to maximum distance separable (MDS) codes. PIR schemes for general linear codes are constructed, and the resulting PIR rate is calculated explicitly. It is shown that codes with transitive automorphism groups yield the highest possible rates obtainable with the proposed scheme. In the special case of no server collusion, this rate coincides with the known asymptotic PIR capacity for MDS-coded storage systems. While many PIR schemes in the literature require field sizes that grow with the number of servers and files in the system, we focus especially on the case of a binary base field, for which Reed-Muller codes serve as an important and explicit class of examples.

The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an [n, k] Reed-Solomon storage code is designed, protecting against t-collusion, and handling up to b Byzantine and r unresponsive servers, when n > k + t + 2b + r - 1. This scheme achieves a PIR rate of ((n - r - (k + 2b + t - 1))/n - r). In the case where the capacity is known, namely, when k = 1, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.

A private information retrieval (PIR) scheme on coded storage systems with colluding, byzantine, and non-responsive servers is presented. Furthermore, the scheme can also be used for symmetric PIR in the same setting. An explicit scheme using an [n, k] generalized Reed-Solomon storage code is designed, protecting against t-collusion and handling up to b byzantine and r non-responsive servers, when n ≥ n1'=(ν+1)k+t+2b+r-1, for some integer ν ≥ 1. This scheme achieves a PIR rate of 1-[(k+2b+t+r-1)/(n'-r)]. In the case where the capacity is known, namely when k=1, it is asymptotically capacity achieving as the number of files grows.

The problem of providing privacy, in the private information retrieval (PIR) sense, to users requesting data from a distributed storage system (DSS), is considered. The DSS is coded by an (n, k, d) maximum distance separable code to store the data reliably on unreliable storage nodes. Some of these nodes can be spies which report to a third party, such as an oppressive regime, which data is being requested by the user. An information theoretic PIR scheme ensures that a user can satisfy its request while revealing no information on which data is being requested to the nodes. A user can trivially achieve PIR by downloading all the data in the DSS. However, this is not a feasible solution due to its high communication cost. We construct PIR schemes with low download communication cost. When there is b = 1 spy node in the DSS, in other words, no collusion between the nodes, we construct PIR schemes with download cost 1/1-R per unit of requested data (R = k/n is the code rate), achieving the information theoretic limit for linear schemes. The proposed schemes are universal since they depend on the code rate, but not on the generator matrix of the code. Also, if b ≤ n-δk nodes collude, with δ = n-b/k, we construct linear PIR schemes with download cost b+δk/δ.

In Private Information Retrieval (PIR), one wants to download a file from a database without revealing to the database which file is being downloaded. Much attention has been paid to the case of the database being encoded across several servers, subsets of which can collude to attempt to deduce the requested file. With the goal of studying the achievable PIR rates in realistic scenarios, we generalize results for coded data from the case of all subsets of servers of size t colluding, to arbitrary subsets of the servers. We investigate the effectiveness of previous strategies in this new scenario, and present new results in the case where the servers are partitioned into disjoint colluding groups.

For many wiretap channel models asymptotically optimal coding schemes are known, but less effort has been put into actual realizations of wiretap codes for practical parameters. Bounds on the mutual information and error probability when using coset coding on a Rayleigh fading channel were recently established by Oggier and Belfiore, and the results in this paper build on their work. However, instead of using their ultimate inverse norm sum approximation, a more precise expression for the eavesdropper's probability of correct decision is used in order to determine a general class of good coset codes. The code constructions are based on well-rounded lattices arising from simple geometric criteria. In addition to new coset codes and simulation results, novel number-theoretic results on well-rounded ideal lattices are presented.