Privacy and Security in Coded Computation and Cache-aided Information Retrieval
김민철 · Seoul National University Open Repository (Seoul National University) · 2020
As a major format of data changes from the text to the videos, the amount of memory for storing data increases exponentially, as well as the amount of computation for handling the data.As a result, to alleviate these burdens of storage and computations, the distributed systems are actively studied.Meanwhile, since low latency is one of the main objectives in 5G communications, recent techniques such as edge computing or federated learning in machine learning become important.Since the decentralized systems are fundamental characteristics of these techniques, the distributed systems which include the decentralized systems also become important.In this dissertation, I consider the distributed systems for storage and computation.For the data storage, large-scale data centers collectively store a library of files where the size of each file is tremendous.When a user needs a specific file, it can be downloaded from distributed data centers.In this system, minimizing the amount of download is a significant concern.The user's privacy in this system implies that the user should conceal the index of its desired file against the databases.This kind of problem is referred to as private information retrieval (PIR) problem.The goal of PIR problem is to minimize the amount of download from the databases while ensuring the user's privacy.Meanwhile, for a large amount of computation, the user can divide the whole computation into sub-computations and distribute them to external workers who constitute i a distributed system.There can be three cases for the computation.Firstly, the user may own all of the data to be computed and sends both of its data and instructions for the computation to the workers.Secondly, the workers collectively own all of the data and the user just sends instructions for the data selection and computation to the workers.Thirdly, the user and the workers have their own data respectively and the user sends the data and instructions for the data selection and computation to the workers.Since some of the workers can be slow for various reasons, the user may use a coding technique, e.g., an erasure code, to avoid the delaying effect caused by the slow workers.This kind of technique is referred to as coded computation.In these systems, speeding up the computation process is a significant concern.In this dissertation, I focus on the third system.In the considered system, the privacy is similar to that of distributed systems for storage.On the other hand, the security implies that the user should conceal the content of its own data against the workers so that the workers do not have any information about the user's own data.In this dissertation, I consider the user's privacy in distributed systems for storage, and both of the privacy and security in distributed systems for the computation.In case of the distributed systems for storage, since the user does not have its own data, the data security on the user's data cannot be considered.Particularly, I propose some achievable schemes that ensure the privacy and security in these systems.To begin with, as a new variation of PIR problem, I consider a user's cache that has some pre-stored data of databases' library.I refer to this problem as cache-aided PIR