Coded Secure Delivery for Anonymous Information Retrieval

In recent years, communication networks have expanded significantly in size and usage. Alongside traditional performance metrics, increasing attention is being paid to user security (restricting access to authorized users) and privacy (protecting requesting user identities). Motivated by these challenges, we introduce the model of coded secure delivery (CSD), where a server uses pre-distributed shared keys to securely serve access-controlled data objects. A CSD instance is defined by two matrices: access-control set (ACS) specifying which users are allowed access to which objects, and key-holder set (KHS) specifying which users have which keys.
Given instance’s ACS and KHS, we fully characterize the requirements for a CSD solution. The characterization is for coded solutions, in which every transmission is a linear combination of data objects over some finite field, encrypted using one of the keys shared by the server and a subset of users. Our main contribution is a two-step solution approach, allowing us to solve the instance with low communication cost, i.e., a small number of transmissions.
We further demonstrate the high power of coding in the CSD problem by showing families of instances with provable gaps between communication costs with and without coding. We also study the complementary problem of key distribution: how should KHS matrices be chosen toward low communication costs, given the ACS matrix and under a key-budget constraint. Finally, we provide an empirical study of the performance of our proposed algorithms, in comparisons between coded and uncoded, and between different key-distribution algorithms.

M.Sc. student under the supervision of Prof. Yuval Cassuto.