Codes for distributed PIR with low storage overhead

Arman Fazeli, Alexander Vardy, Eitan Yaakobi

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים


Private information retrieval (PIR) protocols allow a user to retrieve a data item from a database without revealing any information about the identity of the item being retrieved. Specifically, in information-theoretic k-server PIR, the database is replicated among k non-communicating servers, and each server learns nothing about the item retrieved by the user. The cost of PIR protocols is usually measured in terms of their communication complexity, which is the total number of bits exchanged between the user and the servers. However, another important cost parameter is the storage overhead, which is the ratio between the total number of bits stored on all the servers and the number of bits in the database. Since single-server information-theoretic PIR is impossible, the storage overhead of all existing PIR protocols is at least 2 (or k, in the case of k-server PIR). In this work, we show that information-theoretic PIR can be achieved with storage overhead arbitrarily close to the optimal value of 1, without sacrificing the communication complexity. Specifically, we prove that all known k-server PIR protocols can be efficiently emulated, while preserving both privacy and communication complexity but significantly reducing the storage overhead. To this end, we distribute the n bits of the database among s + r servers, each storing n/s coded bits (rather than replicas). Notably, our coding scheme remains the same, regardless of the specific k-server PIR protocol being emulated. For every fixed k, the resulting storage overhead (s +r)/s approaches 1 as s grows; explicitly we have equation. Moreover, in the special case k = 2, the storage overhead is only 1 + 1/s. In order to achieve these results, we introduce and study a new kind of binary linear codes, called here k-server PIR codes. Finally, we show how such codes can be constructed from multidimensional cubic, from Steiner systems, and from one-step majority-logic decodable codes.

שפה מקוריתאנגלית
כותר פרסום המארחProceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
מספר עמודים5
מסת"ב (אלקטרוני)9781467377041
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 28 ספט׳ 2015
אירועIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, הונג קונג
משך הזמן: 14 יוני 201519 יוני 2015

סדרות פרסומים

שםIEEE International Symposium on Information Theory - Proceedings


כנסIEEE International Symposium on Information Theory, ISIT 2015
מדינה/אזורהונג קונג
עירHong Kong

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1710???
  • ???subjectarea.asjc.2600.2611???
  • ???subjectarea.asjc.2600.2604???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Codes for distributed PIR with low storage overhead'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי