-
Previous Article
Secure and efficient multiparty private set intersection cardinality
- AMC Home
- This Issue
-
Next Article
A note on generalization of bent boolean functions
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 |
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.
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. |
[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. |
[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. |
[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. |
[5] |
Z. Chen, Z. Y. Wang and S. Jafar, The capacity of private information retrieval with private side information, (2017), arXiv: 1709.03022. |
[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. |
[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. |
[8] |
S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb and A. Sprintson, Private information retrieval with side information, (2017), arXiv: 1709.00112. |
[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. |
[10] |
H. Sun and S. A. Jafar,
The capacity of symmetric private information retrieval, 2016 IEEE Globecom Workshops, Washington, DC, USA, (2016), 1-5.
|
[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. |
[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. |
[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.
|
[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. |
[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.
|
[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. |
[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. |
[18] |
J. K. Xu and Z. F. Zhang, On sub-packetization of capacity-achieving PIR schemes for MDS coded databases, (2017), arXiv: 1712.02466. |
[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. |
[20] |
Y. W. Zhang and G. N. Ge, Multi-file private information retrieval from MDS coded databases with colluding servers, (2017), arXiv: 1705.03186. |
[21] |
Z. F. Zhang and J. K. Xu, Capacity-achieving PIR schemes with optimal sub-packetization, (2017), arXiv: 1710.11370. |
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. |
[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. |
[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. |
[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. |
[5] |
Z. Chen, Z. Y. Wang and S. Jafar, The capacity of private information retrieval with private side information, (2017), arXiv: 1709.03022. |
[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. |
[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. |
[8] |
S. Kadhe, B. Garcia, A. Heidarzadeh, S. El Rouayheb and A. Sprintson, Private information retrieval with side information, (2017), arXiv: 1709.00112. |
[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. |
[10] |
H. Sun and S. A. Jafar,
The capacity of symmetric private information retrieval, 2016 IEEE Globecom Workshops, Washington, DC, USA, (2016), 1-5.
|
[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. |
[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. |
[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.
|
[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. |
[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.
|
[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. |
[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. |
[18] |
J. K. Xu and Z. F. Zhang, On sub-packetization of capacity-achieving PIR schemes for MDS coded databases, (2017), arXiv: 1712.02466. |
[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. |
[20] |
Y. W. Zhang and G. N. Ge, Multi-file private information retrieval from MDS coded databases with colluding servers, (2017), arXiv: 1705.03186. |
[21] |
Z. F. Zhang and J. K. Xu, Capacity-achieving PIR schemes with optimal sub-packetization, (2017), arXiv: 1710.11370. |
Step |
|||||
Step |
|||||
Step |
|||||
Step |
|||||
Step |
|||||
Step |
|||||
Steps | Tuple | Number of Total symbols | Number of Useful symbols |
Step 1 | Single | ||
Step 2 | Pair | ||
Step 3 | Triple | ||
Step k | k-tuple | ||
Step M | M-tuple |
Steps | Tuple | Number of Total symbols | Number of Useful symbols |
Step 1 | Single | ||
Step 2 | Pair | ||
Step 3 | Triple | ||
Step k | k-tuple | ||
Step M | M-tuple |
Steps | Tuple | Number of Total symbols (all servers) | Number of Useful symbols (all servers) |
Step 1 | Single | ||
Step 2 | Pair | ||
Step 3 | Triple | ||
Step k | k-tuple | ||
Step M | M-tuple |
Steps | Tuple | Number of Total symbols (all servers) | Number of Useful symbols (all servers) |
Step 1 | Single | ||
Step 2 | Pair | ||
Step 3 | Triple | ||
Step k | k-tuple | ||
Step M | M-tuple |
[1] |
Colleen M. Swanson, Douglas R. Stinson. Extended combinatorial constructions for peer-to-peer user-private information retrieval. Advances in Mathematics of Communications, 2012, 6 (4) : 479-497. doi: 10.3934/amc.2012.6.479 |
[2] |
Feimin Zhong, Wei Zeng, Zhongbao Zhou. Mechanism design in a supply chain with ambiguity in private information. Journal of Industrial and Management Optimization, 2020, 16 (1) : 261-287. doi: 10.3934/jimo.2018151 |
[3] |
Tero Laihonen. Information retrieval and the average number of input clues. Advances in Mathematics of Communications, 2017, 11 (1) : 203-223. doi: 10.3934/amc.2017013 |
[4] |
Zhongbao Zhou, Xingfen Liu, Feimin Zhong, Yuan Cao, Long Zheng. Retailer's willingness to adopt blockchain technology based on private demand information. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022087 |
[5] |
I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929 |
[6] |
Xiaomei Li, Renjing Liu, Zhongquan Hu, Jiamin Dong. Information sharing in two-tier supply chains considering cost reduction effort and information leakage. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021200 |
[7] |
Qun Lin, Antoinette Tordesillas. Towards an optimization theory for deforming dense granular materials: Minimum cost maximum flow solutions. Journal of Industrial and Management Optimization, 2014, 10 (1) : 337-362. doi: 10.3934/jimo.2014.10.337 |
[8] |
Ke-Wei Ding, Nan-Jing Huang, Yi-Bin Xiao. Distributionally robust chance constrained problems under general moments information. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2923-2942. doi: 10.3934/jimo.2019087 |
[9] |
Guodong Ma, Jinbao Jian. A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization. Journal of Industrial and Management Optimization, 2015, 11 (1) : 307-328. doi: 10.3934/jimo.2015.11.307 |
[10] |
Pablo Sánchez, Jaume Sempere. Conflict, private and communal property. Journal of Dynamics and Games, 2016, 3 (4) : 355-369. doi: 10.3934/jdg.2016019 |
[11] |
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 and Management Optimization, 2022, 18 (1) : 375-396. doi: 10.3934/jimo.2020158 |
[12] |
Shiqiu Liu, Frédérique Oggier. On applications of orbit codes to storage. Advances in Mathematics of Communications, 2016, 10 (1) : 113-130. doi: 10.3934/amc.2016.10.113 |
[13] |
Jau-Chuan Ke, Hsin-I Huang, Chuen-Horng Lin. Analysis on a queue system with heterogeneous servers and uncertain patterns. Journal of Industrial and Management Optimization, 2010, 6 (1) : 57-71. doi: 10.3934/jimo.2010.6.57 |
[14] |
Dequan Yue, Jun Yu, Wuyi Yue. A Markovian queue with two heterogeneous servers and multiple vacations. Journal of Industrial and Management Optimization, 2009, 5 (3) : 453-465. doi: 10.3934/jimo.2009.5.453 |
[15] |
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 |
[16] |
Tzu-Hsin Liu, Jau-Chuan Ke, Ching-Chang Kuo. Machine interference problem involving unsuccessful switchover for a group of repairable servers with vacations. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1411-1422. doi: 10.3934/jimo.2020027 |
[17] |
Jeongsim Kim, Bara Kim. Stability of a queue with discriminatory random order service discipline and heterogeneous servers. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1237-1254. doi: 10.3934/jimo.2016070 |
[18] |
Bruno Sixou, Valentina Davidoiu, Max Langer, Francoise Peyrin. Absorption and phase retrieval with Tikhonov and joint sparsity regularizations. Inverse Problems and Imaging, 2013, 7 (1) : 267-282. doi: 10.3934/ipi.2013.7.267 |
[19] |
Huiping Li, Song Li. Phase retrieval from Fourier measurements with masks. Inverse Problems and Imaging, 2021, 15 (5) : 1051-1075. doi: 10.3934/ipi.2021028 |
[20] |
Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024 |
2021 Impact Factor: 1.015
Tools
Metrics
Other articles
by authors
[Back to Top]