אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Private information retrieval (PIR) is a technique of retrieving data from servers in a distributed storage system (DSS), without revealing the identity of the data to the servers. A scheme that achieves the PIR property is referred to as a PIR protocol and is characterized by its PIR rate, which the ratio of downloaded data and the size of the requested data. The supremum of PIR rates achieved by any PIR protocol in a DSS that stores data using arbitrary coded data is referred to as the PIR capacity.

Chor et al. were the first to introduce the PIR problem, where they presented a PIR protocol when the servers stored replicated data. In recent years, there have been some significant gains made in the Information theory society concerning the PIR capacity. In this talk, we summarize these results and present a PIR protocol where the DSS stores arbitrary linear coded data thereby presenting a connection between coding theory and the PIR problem. The proposed protocol achieves the asymptotic MDS-PIR capacity, i.e., the PIR capacity when the underlying storage code is MDS and for the asymptotic number of files in DSS. We prove that under such storage codes the rates achieved by our protocol is indeed the PIR capacity. We refer to such codes as MDS-PIR capacity achieving codes and give a necessary and a sufficient condition for such codes. For codes not part of this family, we propose a new PIR protocol that further improves the PIR rate of the previous protocol.