American Institute of Mathematical Sciences

Advanced
May  2021, 15(2): 347-363. doi: 10.3934/amc.2020070

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

Wenqin Zhang 1,2, , Zhengchun Zhou 1, , Udaya Parampalli 3, and  Vladimir Sidorenko 4,

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.

Keywords: Private information retrieval, minimum download cost, sub-packetization, storage constrained servers.
Mathematics Subject Classification: Primary: 06E75, 94A60, 11T23.
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, 2021, 15 (2) : 347-363. doi: 10.3934/amc.2020070
References:
[1]

M. A. Attia, D. Kumar and R. Tandon, The capacity of uncoded storage constrained PIR, 2018 IEEE International Symposium on Information Theory, (2018), 1959-1963.  doi: 10.1109/ISIT.2018.8437729.  Google Scholar

[2]

K. Banawan and S. Ulukus, Multi-message private information retrieval: Capacity results and near-optimal schemes, IEEE Trans. Inform. Theory, 64 (2018), 6842-6862.  doi: 10.1109/TIT.2018.2828310.  Google Scholar

[3]

K. Banawan and S. Ulukus, The capacity of private information retrieval from byzantine and colluding databases, IEEE Transactions on Information Theory, 65 (2018), 1206–1219, arXiv: 1706.01442. doi: 10.1109/TIT.2018.2869154.  Google Scholar

[4]

K. Banawan and S. Ulukus, The capacity of private information retrieval from coded databases, IEEE Transactions Information Theory, 64 (2018), 1945-1956.  doi: 10.1109/TIT.2018.2791994.  Google Scholar

[5]

Z. Chen, Z. Y. Wang and S. Jafar, The capacity of private information retrieval with private side information, (2017), arXiv: 1709.03022. Google Scholar

[6]

B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, Private information retrieval, 36th Annual Symposium on Foundations of Computer Science, (1995), 41-50.  doi: 10.1109/SFCS.1995.492461.  Google Scholar

[7]

R. Freij-Hollanti, O. W. Gnilke, C. Hollanti and D. A. Karpuk, Private information retrieval from coded databases with colluding servers, SIAM Journal on Applied Algebra and Geometry, 1 (2017), 647-664.  doi: 10.1137/16M1102562.  Google Scholar

[8]

S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb and A. Sprintson, Private information retrieval with side information, (2017), arXiv: 1709.00112. Google Scholar

[9]

H. Sun and S. A. Jafar, The capacity of private information retrieval, IEEE Transactions Information Theory, 63 (2017), 4075-4088.  doi: 10.1109/TIT.2017.2689028.  Google Scholar

[10]

H. Sun and S. A. Jafar, The capacity of symmetric private information retrieval, 2016 IEEE Globecom Workshops, Washington, DC, USA, (2016), 1-5.   Google Scholar

[11]

H. Sun and S. A. Jafar, The capacity of private information retrieval with colluding databases, IEEE Trans. Inform. Theory, 64 (2018), 2361-2370.  doi: 10.1109/TIT.2017.2777490.  Google Scholar

[12]

H. Sun and S. A. Jafar, Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al., IEEE Transactions Information Theory, 64 (2018), 1000-1022.  doi: 10.1109/TIT.2017.2779454.  Google Scholar

[13]

H. Sun and S. A. Jafar, Optimal download cost of private information retrieval for arbitrary message length, IEEE Transactions Information Forensics and Security, 12 (2017), 2920-2932.   Google Scholar

[14]

R. Tajeddine, O. W. Gnilke and S. El Rouayheb, Private information retrieval from MDS coded data in distributed storage systems, IEEE Trans. Inform. Theory, 64 (2018), 7081-7093.  doi: 10.1109/TIT.2018.2815607.  Google Scholar

[15]

R. Tandon, M. Abdul-Wahid, F. Almoualem and D. Kumar, PIR from storage constrained databases - coded caching meets PIR, 2018 IEEE International Conference on Communications, (2018), 1-7.   Google Scholar

[16]

Q. W. Wang and M. Skoglund, Symmetric private information retrieval for MDS coded distributed storage, IEEE International Conference on Communications, (2017), 1-6.  doi: 10.1109/ICC.2017.7997029.  Google Scholar

[17]

N. Woolsey, R.-R. Chen and M. Y. Ji, A new design of private information retrieval for storage constrained databases, (2019), arXiv: 1901.07490. doi: 10.1109/ISIT.2019.8849767.  Google Scholar

[18]

J. K. Xu and Z. F. Zhang, On sub-packetization of capacity-achieving PIR schemes for MDS coded databases, (2017), arXiv: 1712.02466. Google Scholar

[19]

Y. W. Zhang and G. N. Ge, A general private information retrieval scheme for MDS coded databases with colluding servers, (2017), arXiv: 1704.06785. doi: 10.1007/s10623-019-00640-x.  Google Scholar

[20]

Y. W. Zhang and G. N. Ge, Multi-file private information retrieval from MDS coded databases with colluding servers, (2017), arXiv: 1705.03186. Google Scholar

[21]

Z. F. Zhang and J. K. Xu, Capacity-achieving PIR schemes with optimal sub-packetization, (2017), arXiv: 1710.11370. Google Scholar

show all references

References:
[1]

M. A. Attia, D. Kumar and R. Tandon, The capacity of uncoded storage constrained PIR, 2018 IEEE International Symposium on Information Theory, (2018), 1959-1963.  doi: 10.1109/ISIT.2018.8437729.  Google Scholar

[2]

K. Banawan and S. Ulukus, Multi-message private information retrieval: Capacity results and near-optimal schemes, IEEE Trans. Inform. Theory, 64 (2018), 6842-6862.  doi: 10.1109/TIT.2018.2828310.  Google Scholar

[3]

K. Banawan and S. Ulukus, The capacity of private information retrieval from byzantine and colluding databases, IEEE Transactions on Information Theory, 65 (2018), 1206–1219, arXiv: 1706.01442. doi: 10.1109/TIT.2018.2869154.  Google Scholar

[4]

K. Banawan and S. Ulukus, The capacity of private information retrieval from coded databases, IEEE Transactions Information Theory, 64 (2018), 1945-1956.  doi: 10.1109/TIT.2018.2791994.  Google Scholar

[5]

Z. Chen, Z. Y. Wang and S. Jafar, The capacity of private information retrieval with private side information, (2017), arXiv: 1709.03022. Google Scholar

[6]

B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan, Private information retrieval, 36th Annual Symposium on Foundations of Computer Science, (1995), 41-50.  doi: 10.1109/SFCS.1995.492461.  Google Scholar

[7]

R. Freij-Hollanti, O. W. Gnilke, C. Hollanti and D. A. Karpuk, Private information retrieval from coded databases with colluding servers, SIAM Journal on Applied Algebra and Geometry, 1 (2017), 647-664.  doi: 10.1137/16M1102562.  Google Scholar

[8]

S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb and A. Sprintson, Private information retrieval with side information, (2017), arXiv: 1709.00112. Google Scholar

[9]

H. Sun and S. A. Jafar, The capacity of private information retrieval, IEEE Transactions Information Theory, 63 (2017), 4075-4088.  doi: 10.1109/TIT.2017.2689028.  Google Scholar

[10]

H. Sun and S. A. Jafar, The capacity of symmetric private information retrieval, 2016 IEEE Globecom Workshops, Washington, DC, USA, (2016), 1-5.   Google Scholar

[11]

H. Sun and S. A. Jafar, The capacity of private information retrieval with colluding databases, IEEE Trans. Inform. Theory, 64 (2018), 2361-2370.  doi: 10.1109/TIT.2017.2777490.  Google Scholar

[12]

H. Sun and S. A. Jafar, Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al., IEEE Transactions Information Theory, 64 (2018), 1000-1022.  doi: 10.1109/TIT.2017.2779454.  Google Scholar

[13]

H. Sun and S. A. Jafar, Optimal download cost of private information retrieval for arbitrary message length, IEEE Transactions Information Forensics and Security, 12 (2017), 2920-2932.   Google Scholar

[14]

R. Tajeddine, O. W. Gnilke and S. El Rouayheb, Private information retrieval from MDS coded data in distributed storage systems, IEEE Trans. Inform. Theory, 64 (2018), 7081-7093.  doi: 10.1109/TIT.2018.2815607.  Google Scholar

[15]

R. Tandon, M. Abdul-Wahid, F. Almoualem and D. Kumar, PIR from storage constrained databases - coded caching meets PIR, 2018 IEEE International Conference on Communications, (2018), 1-7.   Google Scholar

[16]

Q. W. Wang and M. Skoglund, Symmetric private information retrieval for MDS coded distributed storage, IEEE International Conference on Communications, (2017), 1-6.  doi: 10.1109/ICC.2017.7997029.  Google Scholar

[17]

N. Woolsey, R.-R. Chen and M. Y. Ji, A new design of private information retrieval for storage constrained databases, (2019), arXiv: 1901.07490. doi: 10.1109/ISIT.2019.8849767.  Google Scholar

[18]

J. K. Xu and Z. F. Zhang, On sub-packetization of capacity-achieving PIR schemes for MDS coded databases, (2017), arXiv: 1712.02466. Google Scholar

[19]

Y. W. Zhang and G. N. Ge, A general private information retrieval scheme for MDS coded databases with colluding servers, (2017), arXiv: 1704.06785. doi: 10.1007/s10623-019-00640-x.  Google Scholar

[20]

Y. W. Zhang and G. N. Ge, Multi-file private information retrieval from MDS coded databases with colluding servers, (2017), arXiv: 1705.03186. Google Scholar

[21]

Z. F. Zhang and J. K. Xu, Capacity-achieving PIR schemes with optimal sub-packetization, (2017), arXiv: 1710.11370. Google Scholar

Table 1.  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} $
Table Options

Download as excel

$ 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} $
Table 2.  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}} $
Table Options

Download as excel

$ 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}} $
Table 3.  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} $
Table Options

Download as excel

$ 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} $
Table 4.  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} $
Table Options

Download as excel

$ 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} $
Table 5.  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} $
Table Options

Download as excel

$ 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} $
Table 6.  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} $
Table Options

Download as excel

$ 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} $
Table 7.  The number of symbols downloaded in each step of the scheme
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} $
Table Options

Download as excel

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} $
Table 8.  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} $
Table Options

Download as excel

$ 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} $
Table 9.  The number of symbols downloaded in each step of the scheme
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}} $
Table Options

Download as excel

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}} $
[1]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158
[2]

Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu, Tanmay Choudhury. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15 (2) : 365-386. doi: 10.3934/amc.2020071
[3]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[4]

Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001
[5]

Wai-Ki Ching, Jia-Wen Gu, Harry Zheng. On correlated defaults and incomplete information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 889-908. doi: 10.3934/jimo.2020003
[6]

Nicolas Rougerie. On two properties of the Fisher information. Kinetic & Related Models, 2021, 14 (1) : 77-88. doi: 10.3934/krm.2020049
[7]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[8]

Andrew D. Lewis. Erratum for "nonholonomic and constrained variational mechanics". Journal of Geometric Mechanics, 2020, 12 (4) : 671-675. doi: 10.3934/jgm.2020033
[9]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[10]

Honglin Yang, Jiawu Peng. Coordinating a supply chain with demand information updating. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020181
[11]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016
[12]

Chao Wang, Qihuai Liu, Zhiguo Wang. Periodic bouncing solutions for Hill's type sub-linear oscillators with obstacles. Communications on Pure & Applied Analysis, 2021, 20 (1) : 281-300. doi: 10.3934/cpaa.2020266
[13]

Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043
[14]

Zaizheng Li, Qidi Zhang. Sub-solutions and a point-wise Hopf's lemma for fractional $ p $-Laplacian. Communications on Pure & Applied Analysis, 2021, 20 (2) : 835-865. doi: 10.3934/cpaa.2020293
[15]

Yueyang Zheng, Jingtao Shi. A stackelberg game of backward stochastic differential equations with partial information. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020047
[16]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[17]

Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113
[18]

Chuan Ding, Da-Hai Li. Angel capitalists exit decisions under information asymmetry: IPO or acquisitions. Journal of Industrial & Management Optimization, 2021, 17 (1) : 369-392. doi: 10.3934/jimo.2019116
[19]

Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099
[20]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (80)
  • HTML views (428)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences