We consider the problem of secure distributed matrix multiplication (SDMM) in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We construct polynomial codes for SDMM by studying a combinatorial problem on a special type of addition table, which we call the degree table. The codes are based on arithmetic progressions, and are thus named GASP (Gap Additive Secure Polynomial) Codes. GASP Codes are shown to outperform all previously known polynomial codes for secure distributed matrix multiplication in terms of download rate.
1 January 2019 in IEEE Transactions on Information Theory
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. Lastly, the scheme is adapted to symmetric PIR.
20 September 2018 in IEEE Transactions on Information Theory
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 ?eld sizes that grow with the number of servers and ?les in the system, we focus especially on the case of a binary base ?eld, for which Reed-Muller codes serve as an important and explicit class of examples.
We present Modular Polynomial (MP) Codes for Secure Distributed Matrix Multiplication (SDMM). The construction is based on the observation that one can decode certain proper subsets of the coefficients of a polynomial with fewer evaluations than is necessary to interpolate the entire polynomial. We also present Generalized Gap Additive Secure Polynomial (GGASP) codes. Both MP and GGASP codes are shown experimentally to perform favorably in terms of recovery threshold when compared to other polynomials codes for SDMM which use the grid partition. Both MP and GGASP codes achieve the recovery threshold of Entangled Polynomial Codes for robustness against stragglers, but MP codes can decode below this recovery threshold depending on the set of worker nodes which fails. The decoding complexity of MP codes is shown to be lower than other approaches in the literature, due to the user not being tasked with interpolating an entire polynomial.
4 May 2016 in IEEE Transactions on Information Forensics and Security
Physical-layer network coding (PNC) has been proposed for next generation networks. In this paper, we investigate PNC schemes with embedded perfect secrecy by exploiting structured interference in relay networks with two users and a single relay. In a practical scenario where both users employ finite and uniform signal input distributions, we establish upper bounds (UBs) on the achievable perfect secrecy rates and make these explicit when pulse amplitude modulation modems are used. We then describe two simple, explicit encoders that can achieve perfect secrecy rates close to these UBs with respect to an untrustworthy relay in the single antenna and single relay setting. Last, we generalize our system to a multiple-input multiple-output relay channel, where the relay has more antennas than the users and study optimal precoding matrices, which maintain a required secrecy constraint. Our results establish that the design of PNC transmission schemes with enhanced throughput and guaranteed data confidentiality is feasible in next generation systems.