UC Irvine

The modern information age is heralded by exciting paradigms that generate a tremendous amount of data, such as health records, financial transactions, and social media user information. As information becomes increasingly available, distributed computing becomes more and more important, especially in information retrieval, search, and computation. The high demand for distributed computing brings many new challenges and concerns. This dissertation focuses on privacy, security, and flexibility issues in distributed computing from an information-theoretic perspective. Specifically, we study the privacy problem via private information retrieval (PIR) with a focus on the scenarios with available side information and private search. The security and flexibility problems are investigated via coded distributed computing. Two settings for matrix multiplication are studied: the secure multi-party computation and the distributed computation with a flexible number of available servers.

PIR allows a user to retrieve one message from databases while preserving the privacy of the desired message index. We investigate the role of side information in PIR, meaning a subset of the messages known by the user. Assume T is the number of possible colluding databases, despite which the privacy of the desired message and the side information should still be maintained. We focus on T-Private Information Retrieval with Private Side Information (TPIR-PSI) and characterize its capacity. A novel achievable scheme is proposed. As a special case obtained by setting T = 1, our result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We extend our results to the problem of symmetric-TPIR with private side information (STPIR-PSI). Then, we consider private search, where a user searches for all records matching a symbol from the servers, without revealing any information about the queried symbol. Private search is shown to be highly related to PIR with arbitrarily dependent messages. A new converse bound is presented for PIR with arbitrary dependence. Based on the asymptotic behavior of the new converse bound, the asymptotic capacity of private search is characterized. Our result is further generalized to OR search, AND search, NOT search and sequence search.

As the next step, we consider secure multi-party batch matrix multiplication (SMBMM). Two batches of matrices are individually coded and transmitted to the computation servers, who communicate with each other and a master such that the product of the matrices is decoded at the master. The matrices are kept secure from the servers and the master, except that the master obtains the final product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA-NA) is proposed based on cross-subspace alignment codes. Compared to the state-of-art solution, polynomial sharing, GCSA-NA outperforms it in several key aspects — more efficient and secure inter-server communication, lower latency, flexible inter-server network topology, efficient batch processing, and tolerance to stragglers. Moreover, the idea of noise alignment can be applied to symmetric secure private information retrieval to achieve the asymptotic capacity.

Finally, we focus on the flexibility of the coded distributed matrix multiplication. The goal is also to compute the matrix product from distributed servers. However, servers do not communicate among themselves and the number of stragglers (slow servers) is not known a priori. A novel flexible construction is proposed to fully utilize the computation capability of available servers. The main idea is to require non-straggler servers to finish more sub-tasks to compensate for the effect of the stragglers. The fundamental trade-off between server storage capacity and computation load is investigated.