American Institute of Mathematical Sciences

doi: 10.3934/amc.2020070

Capacity-achieving private information retrieval scheme with a smaller sub-packetization

 1 School of Mathematics, Southwest Jiaotong University, Chengdu, 610031, China 2 State Key Laboratory of Cryptology, P. O. Box 5159, Beijing, 100878, China 3 Department of Computer Science and Software Engineering, University of Melbourne, Melbourne, Australia 4 Institute for Communications Engineering, Technical University of Munich, Germany

Received  April 2019 Revised  February 2020 Published  April 2020

Fund Project: The work of W. Zhang and Z. Zhou was supported by the National Natural Science Foundation of China under Grant 61672028, and partially supported by National Cryptography Development Fund under Grant MMJJ20180103. Vladimir Sidorenko is on leave from Institute for Information Transmission Problems, Russian Academy of Sciences. His work is supported by the Russian Government, Contract No 14.W03.31.0019

Private information retrieval (PIR) allows a user to retrieve one out of $M$ messages from $N$ servers without revealing the identity of the desired message. Every message consists of $L$ symbols (packets) from an additive group and the length $L$ is called the sub-packetization. A PIR scheme with download cost (DC) $D/L$ is implemented by querying $D$ sums of the symbols to servers. We assume that each uncoded server can store up to $tLM/N$ symbols, $t\in\{1,2,\cdots,N\}$. The minimum DC of storage constrained PIR was determined by Attia et al. in 2018 to be $DC_{min} = 1+1/t+1/t^{2}+\cdots+1/t^{M-1}$. The capacity of storage constrained PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired symbols that can be privately retrieved per bit of downloaded symbols. Tandon et al. designed a capacity-achieving PIR scheme with sub-packetization $L' = {N\choose t}t^{M}$ of each message. In this paper, we design a PIR scheme with $t$ times smaller sub-packetization $L'/t$ and with the minimum DC for any parameters $N, M, t$. We also prove that $t^{M-1}$ is a factor of sub-packetization $L$ for any capacity-achieving PIR scheme from storage constrained servers.

Citation: Wenqin Zhang, Zhengchun Zhou, Udaya Parampalli, Vladimir Sidorenko. Capacity-achieving private information retrieval scheme with a smaller sub-packetization. Advances in Mathematics of Communications, doi: 10.3934/amc.2020070
References:

show all references

References:
Sub-messages stored in the servers
 $Serv^1$ $Serv^2$ $Serv^3$ $A_{12}, A_{13}$ $A_{12}, A_{23}$ $A_{13}, A_{23}$ $B_{12}, B_{13}$ $B_{12}, B_{23}$ $B_{13}, B_{23}$ $C_{12}, C_{13}$ $C_{12}, C_{23}$ $C_{13}, C_{23}$
 $Serv^1$ $Serv^2$ $Serv^3$ $A_{12}, A_{13}$ $A_{12}, A_{23}$ $A_{13}, A_{23}$ $B_{12}, B_{13}$ $B_{12}, B_{23}$ $B_{13}, B_{23}$ $C_{12}, C_{13}$ $C_{12}, C_{23}$ $C_{13}, C_{23}$
Symbols stored in the servers
 $Serv^1$ $Serv^2$ $Serv^3$ $\underline{a^1_{12}},\; \underline{a^2_{12}}$ $\underline{a^1_{12}},\; \underline{a^2_{12}}$ $\underline{a^1_{13}},\; \underline{a^2_{13}}$ $\underline{a^1_{13}},\; \underline{a^2_{13}}$ $\underline{a^1_{23}},\; \underline{a^2_{23}}$ $\underline{a^1_{23}},\; \underline{a^2_{23}}$ $\underline{b^1_{12}},\; \underline{b^2_{12}}$ $\underline{b^1_{12}},\; \underline{b^2_{12}}$ $\underline{b^1_{13}},\; \underline{b^2_{13}}$ $\underline{b^1_{13}},\; \underline{b^2_{13}}$ $\underline{b^1_{23}},\; \underline{b^2_{23}}$ $\underline{b^1_{23}},\; \underline{b^2_{23}}$
 $Serv^1$ $Serv^2$ $Serv^3$ $\underline{a^1_{12}},\; \underline{a^2_{12}}$ $\underline{a^1_{12}},\; \underline{a^2_{12}}$ $\underline{a^1_{13}},\; \underline{a^2_{13}}$ $\underline{a^1_{13}},\; \underline{a^2_{13}}$ $\underline{a^1_{23}},\; \underline{a^2_{23}}$ $\underline{a^1_{23}},\; \underline{a^2_{23}}$ $\underline{b^1_{12}},\; \underline{b^2_{12}}$ $\underline{b^1_{12}},\; \underline{b^2_{12}}$ $\underline{b^1_{13}},\; \underline{b^2_{13}}$ $\underline{b^1_{13}},\; \underline{b^2_{13}}$ $\underline{b^1_{23}},\; \underline{b^2_{23}}$ $\underline{b^1_{23}},\; \underline{b^2_{23}}$
Queries to download message $A$
 $Serv^1$ $Serv^2$ $Serv^3$ $a^1_{12}$ $a^1_{23}$ $a^1_{13}$ $b^1_{12}$ $b^1_{23}$ $b^1_{13}$ $a^2_{13}+ b^1_{13}$ $a^2_{12}+ b^1_{12}$ $a^2_{23}+ b^1_{23}$
 $Serv^1$ $Serv^2$ $Serv^3$ $a^1_{12}$ $a^1_{23}$ $a^1_{13}$ $b^1_{12}$ $b^1_{23}$ $b^1_{13}$ $a^2_{13}+ b^1_{13}$ $a^2_{12}+ b^1_{12}$ $a^2_{23}+ b^1_{23}$
Queries to download message $B$
 $Serv^1$ $Serv^2$ $Serv^3$ $b^1_{12}$ $b^1_{23}$ $b^1_{13}$ $a^1_{12}$ $a^1_{23}$ $a^1_{13}$ $b^2_{13}+a^1_{13}$ $b^2_{12}+a^1_{12}$ $b^2_{23}+a^1_{23}$
 $Serv^1$ $Serv^2$ $Serv^3$ $b^1_{12}$ $b^1_{23}$ $b^1_{13}$ $a^1_{12}$ $a^1_{23}$ $a^1_{13}$ $b^2_{13}+a^1_{13}$ $b^2_{12}+a^1_{12}$ $b^2_{23}+a^1_{23}$
Sub-messages stored in the servers
 $Serv^1$ $Serv^2$ $Serv^3$ $Serv^4$ $Serv^5$ $A_{12}, A_{13}$ $A_{12}, A_{23}$ $A_{13}, A_{23}$ $A_{14}, A_{24}$ $A_{15}, A_{25}$ $A_{14}, A_{15}$ $A_{24}, A_{25}$ $A_{34}, A_{35}$ $A_{34}, A_{45}$ $A_{35}, A_{45}$ $B_{12}, B_{13}$ $B_{12}, B_{23}$ $B_{13}, B_{23}$ $B_{14}, B_{24}$ $B_{15}, B_{25}$ $B_{14}, B_{15}$ $B_{24}, B_{25}$ $B_{34}, B_{35}$ $B_{34}, B_{45}$ $B_{35}, B_{45}$ $C_{12}, C_{13}$ $C_{12}, C_{23}$ $C_{13}, C_{23}$ $C_{14}, C_{24}$ $C_{15}, C_{25}$ $C_{14}, C_{15}$ $C_{24}, C_{25}$ $C_{34}, C_{35}$ $C_{34}, C_{45}$ $C_{35}, C_{45}$
 $Serv^1$ $Serv^2$ $Serv^3$ $Serv^4$ $Serv^5$ $A_{12}, A_{13}$ $A_{12}, A_{23}$ $A_{13}, A_{23}$ $A_{14}, A_{24}$ $A_{15}, A_{25}$ $A_{14}, A_{15}$ $A_{24}, A_{25}$ $A_{34}, A_{35}$ $A_{34}, A_{45}$ $A_{35}, A_{45}$ $B_{12}, B_{13}$ $B_{12}, B_{23}$ $B_{13}, B_{23}$ $B_{14}, B_{24}$ $B_{15}, B_{25}$ $B_{14}, B_{15}$ $B_{24}, B_{25}$ $B_{34}, B_{35}$ $B_{34}, B_{45}$ $B_{35}, B_{45}$ $C_{12}, C_{13}$ $C_{12}, C_{23}$ $C_{13}, C_{23}$ $C_{14}, C_{24}$ $C_{15}, C_{25}$ $C_{14}, C_{15}$ $C_{24}, C_{25}$ $C_{34}, C_{35}$ $C_{34}, C_{45}$ $C_{35}, C_{45}$
Queries to download message $A$
 $Serv^1$ $Serv^2$ $Serv^3$ $Serv^4$ $Serv^5$ Step $1$ $a^1_{12},\; a^1_{13}$ $a^1_{23},\; a^1_{24}$ $a^1_{34},\; a^1_{35}$ $a^1_{14},\; a^1_{45}$ $a^1_{15},\; a^1_{25}$ $b^1_{12},\; b^1_{13}$ $b^1_{23},\; b^1_{24}$ $b^1_{34},\; b^1_{35}$ $b^1_{14},\; b^1_{45}$ $b^1_{15},\; b^1_{25}$ $c^1_{12},\; c^1_{13}$ $c^1_{23},\; c^1_{24}$ $c^1_{34},\; c^1_{35}$ $c^1_{14},\; c^1_{45}$ $c^1_{15},\; c^1_{25}$ Step $2$ $a^2_{14}+b^1_{14}$ $a^2_{12}+b^1_{12}$ $a^2_{13}+b^1_{13}$ $a^2_{24}+b^1_{24}$ $a^2_{35}+b^1_{35}$ $a^3_{14}+c^1_{14}$ $a^3_{12}+c^1_{12}$ $a^3_{13}+c^1_{13}$ $a^3_{24}+c^1_{24}$ $a^3_{35}+c^1_{35}$ $a^2_{15}+b^1_{15}$ $a^2_{25}+b^1_{25}$ $a^2_{23}+b^1_{23}$ $a^2_{34}+b^1_{34}$ $a^2_{45}+b^1_{45}$ $a^3_{15}+c^1_{15}$ $a^3_{25}+c^1_{25}$ $a^3_{23}+c^1_{23}$ $a^3_{34}+c^1_{34}$ $a^3_{45}+c^1_{45}$ $b^2_{14}+c^2_{14}$ $b^2_{12}+c^2_{12}$ $b^2_{13}+c^2_{13}$ $b^2_{24}+c^2_{24}$ $b^2_{35}+c^2_{35}$ $b^2_{15}+c^2_{15}$ $b^2_{25}+c^2_{25}$ $b^2_{23}+c^2_{23}$ $b^2_{34}+c^2_{34}$ $b^2_{45}+c^2_{45}$ Step $3$ $a^4_{12}+b^2_{12}+c^2_{12}$ $a^4_{23}+b^2_{23}+c^2_{23}$ $a^4_{34}+b^2_{34}+c^2_{34}$ $a^4_{14}+b^2_{14}+c^2_{14}$ $a^4_{15}+b^2_{15}+c^2_{15}$ $a^4_{13}+b^2_{13}+c^2_{13}$ $a^4_{24}+b^2_{24}+c^2_{24}$ $a^4_{35}+b^2_{35}+c^2_{35}$ $a^4_{45}+b^2_{45}+c^2_{45}$ $a^4_{25}+b^2_{25}+c^2_{25}$
 $Serv^1$ $Serv^2$ $Serv^3$ $Serv^4$ $Serv^5$ Step $1$ $a^1_{12},\; a^1_{13}$ $a^1_{23},\; a^1_{24}$ $a^1_{34},\; a^1_{35}$ $a^1_{14},\; a^1_{45}$ $a^1_{15},\; a^1_{25}$ $b^1_{12},\; b^1_{13}$ $b^1_{23},\; b^1_{24}$ $b^1_{34},\; b^1_{35}$ $b^1_{14},\; b^1_{45}$ $b^1_{15},\; b^1_{25}$ $c^1_{12},\; c^1_{13}$ $c^1_{23},\; c^1_{24}$ $c^1_{34},\; c^1_{35}$ $c^1_{14},\; c^1_{45}$ $c^1_{15},\; c^1_{25}$ Step $2$ $a^2_{14}+b^1_{14}$ $a^2_{12}+b^1_{12}$ $a^2_{13}+b^1_{13}$ $a^2_{24}+b^1_{24}$ $a^2_{35}+b^1_{35}$ $a^3_{14}+c^1_{14}$ $a^3_{12}+c^1_{12}$ $a^3_{13}+c^1_{13}$ $a^3_{24}+c^1_{24}$ $a^3_{35}+c^1_{35}$ $a^2_{15}+b^1_{15}$ $a^2_{25}+b^1_{25}$ $a^2_{23}+b^1_{23}$ $a^2_{34}+b^1_{34}$ $a^2_{45}+b^1_{45}$ $a^3_{15}+c^1_{15}$ $a^3_{25}+c^1_{25}$ $a^3_{23}+c^1_{23}$ $a^3_{34}+c^1_{34}$ $a^3_{45}+c^1_{45}$ $b^2_{14}+c^2_{14}$ $b^2_{12}+c^2_{12}$ $b^2_{13}+c^2_{13}$ $b^2_{24}+c^2_{24}$ $b^2_{35}+c^2_{35}$ $b^2_{15}+c^2_{15}$ $b^2_{25}+c^2_{25}$ $b^2_{23}+c^2_{23}$ $b^2_{34}+c^2_{34}$ $b^2_{45}+c^2_{45}$ Step $3$ $a^4_{12}+b^2_{12}+c^2_{12}$ $a^4_{23}+b^2_{23}+c^2_{23}$ $a^4_{34}+b^2_{34}+c^2_{34}$ $a^4_{14}+b^2_{14}+c^2_{14}$ $a^4_{15}+b^2_{15}+c^2_{15}$ $a^4_{13}+b^2_{13}+c^2_{13}$ $a^4_{24}+b^2_{24}+c^2_{24}$ $a^4_{35}+b^2_{35}+c^2_{35}$ $a^4_{45}+b^2_{45}+c^2_{45}$ $a^4_{25}+b^2_{25}+c^2_{25}$
 Steps Tuple Number of Total symbols Number of Useful symbols Step 1 Single $N{{M}\choose{1}}\lambda$ $N\lambda$ Step 2 Pair $N{{M}\choose{2}}\lambda(t-1)$ $N{{M-1}\choose{2-1}}\lambda(t-1)$ Step 3 Triple $N{{M}\choose{3}}\lambda(t-1)^2$ $N{{M-1}\choose{3-1}}\lambda(t-1)^2$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step k k-tuple $N{{M}\choose{k}}\lambda(t-1)^{k-1}$ $N{{M-1}\choose{k-1}}\lambda(t-1)^{k-1}$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step M M-tuple $N{{M}\choose{M}}\lambda(t-1)^{M-1}$ $N{{M-1}\choose{M-1}}\lambda(t-1)^{M-1}$
 Steps Tuple Number of Total symbols Number of Useful symbols Step 1 Single $N{{M}\choose{1}}\lambda$ $N\lambda$ Step 2 Pair $N{{M}\choose{2}}\lambda(t-1)$ $N{{M-1}\choose{2-1}}\lambda(t-1)$ Step 3 Triple $N{{M}\choose{3}}\lambda(t-1)^2$ $N{{M-1}\choose{3-1}}\lambda(t-1)^2$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step k k-tuple $N{{M}\choose{k}}\lambda(t-1)^{k-1}$ $N{{M-1}\choose{k-1}}\lambda(t-1)^{k-1}$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step M M-tuple $N{{M}\choose{M}}\lambda(t-1)^{M-1}$ $N{{M-1}\choose{M-1}}\lambda(t-1)^{M-1}$
Queries to download message $A$
 $Serv^1$ $Serv^2$ $Serv^3$ $Serv^4$ $a^1_{12},a^1_{14}$ $a^1_{23},a^1_{24}$ $a^1_{13}$ $a^1_{34}$ $b^1_{12},b^1_{14}$ $b^1_{23},b^1_{24}$ $b^1_{13}$ $b^1_{34}$ $a^2_{13}+b^1_{13}$ $a^2_{12}+b^1_{12}$ $a^2_{23}+b^1_{23}$ $a^2_{14}+b^1_{14}$ $a^2_{34}+b^1_{34}$ $a^2_{24}+b^1_{24}$
 $Serv^1$ $Serv^2$ $Serv^3$ $Serv^4$ $a^1_{12},a^1_{14}$ $a^1_{23},a^1_{24}$ $a^1_{13}$ $a^1_{34}$ $b^1_{12},b^1_{14}$ $b^1_{23},b^1_{24}$ $b^1_{13}$ $b^1_{34}$ $a^2_{13}+b^1_{13}$ $a^2_{12}+b^1_{12}$ $a^2_{23}+b^1_{23}$ $a^2_{14}+b^1_{14}$ $a^2_{34}+b^1_{34}$ $a^2_{24}+b^1_{24}$
 Steps Tuple Number of Total symbols (all servers) Number of Useful symbols (all servers) Step 1 Single ${{{M}\choose{1}}[da+t(N-d)]}$ $da+t(N-d)$ Step 2 Pair ${{M}\choose{2}}\frac{d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)}{{{N}\choose{t}}^{0}}$ ${{M-1}\choose{2-1}}\frac{d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)}{{{N}\choose{t}}^0}$ Step 3 Triple ${{M}\choose{3}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^2}{{{N}\choose{t}}^{1}}$ ${{M-1}\choose{3-1}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^2}{{{N}\choose{t}}^1}$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step k k-tuple ${{M}\choose{k}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{k-1}}{{{N}\choose{t}}^{k-2}}$ ${{M-1}\choose{k-1}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{k-1}}{{{N}\choose{t}}^{k-2}}$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step M M-tuple ${{M}\choose{M}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{M-1}}{{{N}\choose{t}}^{M-2}}$ ${{M-1}\choose{M-1}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{M-1}}{{{N}\choose{t}}^{M-2}}$
 Steps Tuple Number of Total symbols (all servers) Number of Useful symbols (all servers) Step 1 Single ${{{M}\choose{1}}[da+t(N-d)]}$ $da+t(N-d)$ Step 2 Pair ${{M}\choose{2}}\frac{d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)}{{{N}\choose{t}}^{0}}$ ${{M-1}\choose{2-1}}\frac{d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)}{{{N}\choose{t}}^0}$ Step 3 Triple ${{M}\choose{3}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^2}{{{N}\choose{t}}^{1}}$ ${{M-1}\choose{3-1}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^2}{{{N}\choose{t}}^1}$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step k k-tuple ${{M}\choose{k}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{k-1}}{{{N}\choose{t}}^{k-2}}$ ${{M-1}\choose{k-1}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{k-1}}{{{N}\choose{t}}^{k-2}}$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ Step M M-tuple ${{M}\choose{M}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{M-1}}{{{N}\choose{t}}^{M-2}}$ ${{M-1}\choose{M-1}}\frac{{[d({{N-1}\choose{t-1}}-a)+(N-d)({{N-1}\choose{t-1}}-t)]}^{M-1}}{{{N}\choose{t}}^{M-2}}$