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 ...<inline-formula> <tex-math notation="LaTeX">(n,k,d) </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">b=1 </tex-math></inline-formula> spy node in the DSS, in other words, no collusion between the nodes, we construct PIR schemes with download cost <inline-formula> <tex-math notation="LaTeX">\frac {1}{1-R} </tex-math></inline-formula> per unit of requested data (<inline-formula> <tex-math notation="LaTeX">R=k/n </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">b\leq n-\delta k </tex-math></inline-formula> nodes collude, with <inline-formula> <tex-math notation="LaTeX">\delta =\lfloor {\frac {n-b}{k}}\rfloor </tex-math></inline-formula>, we construct linear PIR schemes with download cost <inline-formula> <tex-math notation="LaTeX">\frac {b+\delta k}{\delta } </tex-math></inline-formula>.
The problem of private information retrieval (PIR) from coded storage systems with colluding, Byzantine, and unresponsive servers is considered. An explicit scheme using an <inline-formula> <tex-math ...notation="LaTeX">n,k </tex-math></inline-formula> Reed-Solomon storage code is designed, protecting against <inline-formula> <tex-math notation="LaTeX">t </tex-math></inline-formula>-collusion, and handling up to <inline-formula> <tex-math notation="LaTeX">b </tex-math></inline-formula> Byzantine and <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula> unresponsive servers, when <inline-formula> <tex-math notation="LaTeX">n>k+t+2b+r-1 </tex-math></inline-formula>. This scheme achieves a PIR rate of <inline-formula> <tex-math notation="LaTeX">(({n-r-(k+2b+t-1)})/{n-r}) </tex-math></inline-formula>. In the case where the capacity is known, namely, when <inline-formula> <tex-math notation="LaTeX">k=1 </tex-math></inline-formula>, it is asymptotically capacity achieving as the number of files grows. Finally, the scheme is adapted to symmetric PIR.
Large matrix multiplications commonly take place in large-scale machine-learning applications. Often, the sheer size of these matrices prevent carrying out the multiplication at a single server. ...Therefore, these operations are typically offloaded to a distributed computing platform with a master server and a large amount of workers in the cloud, operating in parallel. For such distributed platforms, it has been recently shown that coding over the input data matrices can reduce the computational delay by introducing a tolerance against straggling workers, i.e., workers for which execution time significantly lags with respect to the average. In addition to exact recovery, we impose a security constraint on both matrices to be multiplied. Specifically, we assume that workers can collude and eavesdrop on the content of these matrices. For this problem, we introduce a new class of polynomial codes with fewer non-zero coefficients than the degree +1. We provide closed-form expressions for the recovery threshold and show that our construction improves the recovery threshold of existing schemes in the literature, in particular for larger matrix dimensions and a moderate to large number of colluding workers. In the absence of any security constraints, we show that our construction is optimal in terms of recovery threshold.
This work considers the problem of privately outsourcing the computation of a matrix product over a finite field <inline-formula> <tex-math notation="LaTeX">{\mathbb {F}}_{q} ...</tex-math></inline-formula> to <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">X </tex-math></inline-formula> servers is allowed to share their data. Previous works considered this collusion a hindrance and the download cost of the schemes increases with growing <inline-formula> <tex-math notation="LaTeX">X </tex-math></inline-formula>. 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.
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.
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
-
ϵ
)
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
-
ϵ
)
users.
PDF
