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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 28 سبتمبر 2015
الحدثIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, هونغ كونغ
المدة: ١٤ يونيو ٢٠١٥١٩ يونيو ٢٠١٥

سلسلة المنشورات

الاسمIEEE International Symposium on Information Theory - Proceedings
مستوى الصوت2015-June


!!ConferenceIEEE International Symposium on Information Theory, ISIT 2015
الدولة/الإقليمهونغ كونغ
المدينةHong Kong

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!Information Systems
  • !!Modeling and Simulation
  • !!Applied Mathematics


أدرس بدقة موضوعات البحث “Codes for distributed PIR with low storage overhead'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا