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

  • Figure 1

    Suppose $M=2$, $N=3$, $K=2$. (a) is for privately retrieving $W_1$, while (b) is for retrieving $W_2$.

  • Figure 2

    Query sequence for $\theta=1$ in the $(M=3$, $N=3$, $K=2)$ PIR scheme.

  • Figure 3

    Query sequence for the $\theta=1$ in the $(M=2$, $N=5$, $K=2)$ PIR scheme.

  • Figure 4

    Explanations of the functions ${\rm~Dist}_1(\Lambda,\underline{\Lambda})$ and ${\rm~Dist}_2(\Lambda,\Gamma)$ in Example 5.2. (a) Dist$_1~(\{2\},\{1,2\})$; (b) Dist$_2~(\{2\},$ $\{1,2\})$; (c) Dist$_2~(\{2,3\},\{2,3\})$.

  • Table 1   Notations in the general scheme
    Notation Meaning
    $\theta$ rm The index of the desired record
    $\underline{\Lambda}$ $\Lambda\cup\{\theta\}$rm for some $\Lambda\subseteq[M]-\{\theta\}$
    $\Lambda_{j,h}$ rm Suppose $\{\Lambda\subseteq[M]-\{\theta\}\mid|\Lambda|=j\}=\{\Lambda_{j,1},\Lambda_{j,2},\ldots,\Lambda_{j,t}\}$rm where $1\leq~h\leq~t=\binom{M-1}{j}$
    $q_{\Lambda,\lambda}$ rm A $\Lambda$-type $|\Lambda|$-sum
    $q^{(i)}_{\Lambda,h}$ rm The $h$-th $\Lambda$-type $|\Lambda|$-sum provided by Serv$^{(i)}$
    $\gamma^{(i)}_j$ rm The number of each type of $j$-sums provided by Serv$^{(i)}$
    $\alpha_j$ $\gamma^{(i)}_j$ for $~1\leq~i\leq~N-K$
    $\beta_j$ $\gamma^{(i)}_j$ for $N-K+1\leq~i\leq~N$
  • Table 2   Notations in the general scheme
    $\Lambda$-type ${\rm~Serv}^{(i)},~1\leq~i\leq~N-K$ ${\rm~Serv}^{(i)},~N-K<~i\leq~N$
    ${~q}^{(i)}_{\Lambda,1}$ ${~q}^{(i)}_{\Lambda,1}$
    $\forall\Lambda\subseteq[M]$ $\vdots$ $\vdots$
    ${q}^{(i)}_{\Lambda,\alpha_{|\Lambda|}}$ ${q}^{(i)}_{\Lambda,\beta_{|\Lambda|}}$

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

京ICP备18024590号-1