Private Information Retrieval from Coded Storage
School of Science | Doctoral thesis (article-based) | Defence date: 2019-03-07
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
62 + app. 86
Aalto University publication series DOCTORAL DISSERTATIONS, 29/2019
AbstractAlong with the technological advancements and the remarkable growth of digital data storage, new challenges arise regarding the reliabilty of the digital data storage and the privacy of the users. A distributed storage system (DSS) can store big amounts of data for a long time over possibly unreliable servers. As for the privacy concern of the users, much effort has been spent in trying to find systems and schemes that allow users to communicate, search, upload and download files while maintaining their privacy. One of those schemes is private information retrieval (PIR). PIR allows the users to hide the identity of files they request from a DSS. In other words, a PIR scheme allows the user to retrieve any file from a DSS without revealing the file identity to any of the servers. It goes without saying that, to achieve privacy, the user should download a bigger amount of data than the size of the desired file. The extra amount of data downloaded is quantified by the communication complexity of a PIR scheme. Naturally, downloading all the data from the DSS hides the identity of the desired file, but has a very high communication complexity, especially as the number of files in a DSS is typically very large. Moreover, this also raises the question of the server privacy, meaning that the user should not be able to retrieve any extra information about the undesired files while retrieving a certain file. Schemes taking into account the server privacy are called symmetric PIR (SPIR) schemes. This thesis focuses on constructing PIR schemes for different DSSs with low communication cost. We study different DSSs which reduce the storage cost of the system while providing reliability. We construct PIR schemes on such systems, where we consider both cases, the case where the servers in the DSS do not communicate, and the case where some subsets of the servers communicate in an effort to figure out the desired file identity. Moreover, we consider the SPIR problem, and consider the case where some servers may be unresponsive, such that they do not respond to the sent query, and the case where the servers may be malicious or unsynchronized and thus give false information to the user. Last but not least, this thesis also considers schemes providing privacy for users requesting data from a DSS over a random linear network.
Supervising professorHollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
Thesis advisorHollanti, Camilla, Prof., Aalto University, Department of Mathematics and Systems Analysis, Finland
El Rouayheb, Salim, Prof., Rutgers University, USA
Gnilke, Oliver, Dr., Aalto University, Department of Mathematics and Systems Analysis, Finland
privacy, information retrieval, coding, storage systems, Reed-Solomon codes, regenrating codes, networks
[Publication 1]: Razane Tajeddine, Oliver W. Gnilke, Salim El Rouayheb. Private information retrieval from MDS coded data in distributed storage systems. IEEE Transactions on Information Theory, Volume 64, Issue 11, pp. 7081 - 7093, Nov 2018. Full Text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201811025578.
DOI: 10.1109/TIT.2018.2815607 View at publisher
- [Publication 2]: Razane Tajeddine, Salim El Rouayheb. Robust Private Information Retrieval on Coded Data. In IEEE International Symposium on Information Theory (ISIT), 2017.
[Publication 3]: Razane Tajeddine, Oliver W. Gnilke, David Karpuk, Ragnar Freij-Hollanti, Camilla Hollanti, Salim El Rouayheb. Private Information Retrieval Schemes for Coded Data with Arbitrary Collusion Patterns. In IEEE International Symposium on Information Theory (ISIT), 2017.
DOI: 10.1109/ISIT.2017.8006861 View at publisher
- [Publication 4]: Razane Tajeddine, Oliver W. Gnilke, David Karpuk, Ragnar Freij-Hollanti, Camilla Hollanti. Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and UnresponsiveServers. Accepted in IEEE Transactions on Information Theory, 2018.
- [Publication 5]: Julien Lavauzelle, Razane Tajeddine, Ragnar Freij-Hollanti, Camilla Hollanti. Private Information Retrieval Schemes with Regenerating Codes. Submitted to IEEE Transactions on Information Theory, 2018.
- [Publication 6]: Razane Tajeddine, Antonia Wachter-Zeh, Camilla Hollanti. Private Information Retrieval over Networks. Submitted to IEEE Transactions on Information Forensics and Security, 2018.