logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 10: 100306(2018) https://doi.org/10.1007/s11432-018-9538-4

On sub-packetization and access number of capacity-achieving PIR schemes for MDS coded non-colluding servers

More info
  • ReceivedMar 10, 2018
  • AcceptedJul 23, 2018
  • PublishedSep 4, 2018

Abstract

Consider the problem of private information retrieval (PIR) over a distributed storage system where $M$ records are stored across $N$ servers by using an $[N,K]$ MDS code. For simplicity, this problem is usually referred as the coded PIR problem. In 2016, Banawan and Ulukus designed the first capacity-achieving coded PIR scheme with sub-packetization $KN^{M}$ and access number $MKN^{M}$, where capacity characterizes the minimal download size for retrieving per unit of data, and sub-packetization and access number are two metrics closely related to implementation complexity.In this paper, we focus on minimizing the sub-packetization and the access number for linear capacity-achieving coded PIR schemes. We first determine the lower bounds on sub-packetization and access number, which are $Kn^{M-1}$ and $MKn^{M-1}$, respectively, in the nontrivial cases (i.e., $N\!>\!K\!\geq\!1$ and $M\!>\!1$), where $n\!=\!N/{\rm~gcd}(N,K)$. We then design a general linear capacity-achieving coded PIR scheme to simultaneously attain these two bounds, implying tightness of both bounds.


References

[1] Chor B, Kushilevitz E, Goldreich O, et al. Private information retrieval. In: Proceedings of IEEE Symposium on Foundations of Computer Science, Milwaukee, 1995. 41--50. Google Scholar

[2] Chor B, Kushilevitz E, Goldreich O. Private information retrieval. J ACM, 1998, 45: 965-981 CrossRef Google Scholar

[3] Gasarch W. A survey on private information retrieval. Bull EATCS, 2004, 82: 72--107. Google Scholar

[4] Dvir Z, Gopi S. 2-server PIR with sub-polynomial communication. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC'15), Portland, 2015. 577--584. Google Scholar

[5] Efremenko K. 3-query locally decodable codes of subexponential length. In: Proceedings of the 41th Annual ACM Symposium on Theory of Computing (STOC'09), Bethesda, 2009. 39--44. Google Scholar

[6] Sun H, Jafar S A. The capacity of private information retrieval. IEEE Trans Inf Theory, 2017, 63: 4075-4088 CrossRef Google Scholar

[7] Sun H, Jafar S A. The capacity of private information retrieval with colluding databases. In: Proceedings of IEEE Global Conference on Signal and Information Processing, Washington, 2016. 941--946. Google Scholar

[8] Sun H, Jafar S A. The capacity of symmetric private information retrieval. In: Proceedings of IEEE Globecom Workshops (GC Wkshps), Washington, 2016. Google Scholar

[9] Banawan K, Ulukus S. Multi-message private information retrieval. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 1898--1902. Google Scholar

[10] Banawan K, Ulukus S. Private information retrieval from Byzantine and colluding databases. In: Proceedings of the 55th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2017. 1091--1098. Google Scholar

[11] Chen Z, Wang Z Y, Jafar S A. The capacity of private information retrieval with private side information. 2017,. arXiv Google Scholar

[12] Kadhe S, Garcia B, Heidarzadeh A, et al. Private information retrieval with side information. 2017,. arXiv Google Scholar

[13] Tandon R. The capacity of cache aided private information retrieval. 2017,. arXiv Google Scholar

[14] Wei Y P, Banawan K, Ulukus S. Fundamental limits of cache-aided private information retrieval with unknown and uncoded prefetching. 2017,. arXiv Google Scholar

[15] Banawan K, Ulukus S. The capacity of private information retrieval from coded databases. IEEE Trans Inf Theory, 2018, 64: 1945-1956 CrossRef Google Scholar

[16] Tajeddine R, Rouayheb S E. Private information retrieval from MDS coded data in distributed storage systems. In: Proceedings of IEEE International Symposium on Information Theory, Barcelona, 2016. 1411--1415. Google Scholar

[17] Wang Q W, Skoglund M. Symmetric private information retrieval for MDS coded distributed storage. In: Proceedings of IEEE International Conference on Communications (ICC), Paris, 2017. Google Scholar

[18] Freij-Hollanti R, Gnilke O W, Hollanti C. Private information retrieval from coded databases with colluding servers. SIAM J Appl Algebra Geometry, 2017, 1: 647-664 CrossRef Google Scholar

[19] Zhang Y W, Ge G N. A general private information retrieval scheme for MDS coded databases with colluding servers. 2017,. arXiv Google Scholar

[20] Ye M, Barg A. Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization. IEEE Trans Inf Theory, 2017, 63: 6307-6317 CrossRef Google Scholar

[21] Balaji S B, Kumar P V. A tight lower bound on the sub-packetization level of optimal-access MSR and MDS codes. 2018,. arXiv Google Scholar

[22] Sun H, Jafar S A. Optimal download cost of private information retrieval for arbitrary message length. IEEE Trans Inf Forensic Secur, 2017, 12: 2920-2932 CrossRef Google Scholar

[23] Zhang Z F, Xu J K. Capacity-achieving PIR schemes with optimal sub-packetization. 2017,. arXiv Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1