Coded Secure Delivery for Anonymous Information Retrieval

This paper proposes and studies a scheme of coded secure delivery (CSD), where data objects are delivered upon request in a way that only users that are allowed access can recover them. The security of the scheme is driven by encryption with keys that are pre-distributed to different subsets of the users. As a result, the system can securely serve anonymous requests, enhancing its users’ privacy. A CSD instance is defined formally by two binary matrices, and our main result is an algorithm to minimize the number of transmissions needed to accomplish it. Coding allows transmission of linear combinations of objects, and the power of coding is demonstrated by showing instance families with large gaps to uncoded delivery. In addition to minimizing communication costs, the paper studies the key-distribution problem toward minimizing the users’ storage costs.