We consider the problem of secure distributed ma-trix multiplication in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We show how to construct polynomial schemes for the outer product partitioning which take advantage of the user's ability to precompute, and provide bounds for our technique. We show that precomputation allows for a reduction in the order of the time complexity for the cases where the number of colluding servers is a fixed percentage of the number of servers. Furthermore, with precomputation, any percentage (less than 100%) of collusions can be tolerated, compared to the upper limit of 50% for the case without precomputation.

A new framework for interference alignment in secure and private information retrieval (PIR) from colluding servers is proposed, generalizing the original cross-subspace alignment (CSA) codes proposed by Jia, Sun, and Jafar. The general scheme is built on algebraic geometry codes and explicit constructions with replicated storage are given over curves of genus zero and one. It is shown that the proposed scheme offers interesting tradeoffs between the field size, file size, number of colluding servers, and the total number of servers. When the field size is fixed, this translates in some cases to higher retrieval rates than those of the original scheme. In addition, the new schemes exist also in cases where the original ones do not.

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.

We propose reducible algebraic curves as a mechanism to construct partial maximum distance separable codes geometrically. We obtain new general existence results, new explicit constructions, and improved estimates on the smallest field sizes over which such codes can exist. Our results are obtained by combining ideas from projective algebraic geometry, combinatorics, and probability theory.

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) is the problem of privately retrieving one out of M original files from N severs, i.e., each individual server gains no information on the identity of the file that the user is requesting. Usually, the M files are replicated or encoded by a maximum distance separable (MDS) code and then stored across the N servers. Compared to mere replication, MDS-coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR protocols from MSR-coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from MDS array codes is proposed, subsuming PIR from MSR-coded servers as a special case. Particularly, only the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from MDS-/MSR-coded servers. By choosing different MDS array codes, the new PIR protocol can have varying advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-)optimal repair bandwidth, 3) implementable over the binary field F2.

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.

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.

Private computation is a generalization of private information retrieval, in which a user is able to compute a function on a distributed dataset without revealing the identity of that function to the servers. In this paper, it is shown that Lagrange encoding, a powerful technique for encoding Reed-Solomon codes, enables private computation in many cases of interest. In particular, we present a scheme that enables private computation of polynomials of any degree on Lagrange encoded data, while being robust to Byzantine and straggling servers, and to servers colluding to attempt to deduce the identities of the functions to be evaluated. Moreover, incorporating ideas from the well-known Shamir secret sharing scheme allows the data itself to be concealed from the servers as well. Our results extend private computation to high degree polynomials and to data-privacy, and reveal a tight connection between private computation and coded computation.

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 recently introduced combinatorial tool called the degree table. Maximizing the download rate of a polynomial code for SDMM is equivalent to minimizing N, the number of distinct elements in the corresponding degree table. We propose new constructions of degree tables with a low number of distinct elements. These new constructions lead to a general family of polynomial codes for SDMM, which we call GASP,. (Gap Additive Secure Polynomial codes) parametrized by an integer r. GASProutperforms all previously known polynomial codes for SDMM. We also present lower bounds on N and show that GASPrachieves the lower bounds in the case of no server collusion.

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.

Private Computation (PC), recently introduced by Sun and Jafar, is a generalization of Private Information Retrieval (PIR) in which a user wishes to privately compute an arbitrary function of data stored across several servers. We construct a PC scheme which accounts for server collusion, coded data, and non-linear functions. For data replicated over several possibly colluding servers, our scheme computes arbitrary functions of the data with rate equal to the asymptotic capacity of PIR for this setup. For systematically encoded data stored over colluding servers, we privately compute arbitrary functions of the columns of the data matrix and calculate the rate explicitly for polynomial functions. The scheme is a generalization of previously studied star-product PIR schemes.

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.

In this paper, we study lattice coding for Rician fading wireless channels. This is motivated in particular by preliminary studies suggesting the Rician fading model for millimeter-wavelength wireless communications. We restrict to lattice codes arising from rotations of Zn, and to a single-input single-output (SISO) channel. We observe that several lattice design criteria suggest the optimality of Hadamard rotations. For instance, we prove that Hadamard rotations maximize the diamond-packing density among all rotated Znlattices. Finally, we provide simulations to show that Hadamard rotations outperform optimal algebraic rotations and cross-packing lattices in the Rician channel.

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.

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.

To optimize rotated multidimensional constellations over a single-input single-output Rayleigh fading channel, a family of rotation matrices is constructed for all dimensions which are a power of 2. This family is a one-parameter subgroup of the group of rotation matrices, and is located using a gradient descent scheme on this Lie group. The parameter defining the family is chosen to optimize the cutoff rate of the constellation. The optimal rotation parameter is computed explicitly for low signal-to-noise ratios. These rotations outperform full-diversity algebraic rotations in terms of cutoff rate at low signal-to-noise ratio (SNR) and bit error rate at high SNR in dimension n = 4. However, a quadrature amplitude modulation (QAM) constellation rotated by such a matrix lacks full diversity, in contrast with the conventional wisdom that good signal sets exhibit full diversity. A new notion of diversity, referred to as local diversity, is introduced to attempt to account for this behavior. Roughly, a locally fully diverse constellation is fully diverse only in small neighborhoods. A local variant of the minimum product distance is also introduced and is shown experimentally to be a superior predictor of constellation performance than the minimum product distance in dimension n = 4.

We use a numerical algorithm on the Lie group of rotation matrices to obtain rotated constellations for Rayleigh fading channels. Our approach minimizes the union bound for the pairwise error probability to produce rotations optimized for a given signal-to-noise ratio. This approach circumvents explicit parametrization of rotation matrices, which has previously prevented robust numerical methods from being applied to constellation rotation. Our algorithm is applicable to arbitrary finite constellations in arbitrary dimensions, and one can thus apply our method to non-uniform constellations, which are of interest for practical concerns due to their ability to increase bit-interleaved coded modulation (BICM) capacity. We show how our rotations can improve the codeword error performance of non-uniform constellations, and we also apply our method to reproduce and improve rotations given by ideal lattices in cyclotomic fields.

With the goal of optimizing the CM (coded modulation) capacity of a finite constellation over a Rayleigh fading channel, we use one-parameter subgroups of the Lie group of rotation matrices to construct families of rotation matrices which optimize a certain objective function controlling the CM capacity. Our construction does not depend on any assumptions about the constellation or signal-to-noise ratio. We confirm the benefits of our construction for uniform and non-uniform constellations at a large range of SNR values through numerous simulations. We show that in two and four dimensions one can obtain a further potential increase in CM capacity by jointly considering non-uniform and rotated constellations.

In this paper, we establish probability bounds for the correct decision of the eavesdropper over a MIMO Wiretap Channel, when coding using cyclic division algebras is used. We focus in particular on codebooks constructed from natural orders in Q-central quaternion algebras, which allows the resulting expressions to take a more explicit form.