{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:45:57Z","timestamp":1780674357048,"version":"3.54.1"},"reference-count":29,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T00:00:00Z","timestamp":1673395200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["CCF-18-16518"],"award-info":[{"award-number":["CCF-18-16518"]}]},{"name":"National Science Foundation","award":["CCF-18-16546"],"award-info":[{"award-number":["CCF-18-16546"]}]},{"name":"National Science Foundation","award":["CCF-20-07067"],"award-info":[{"award-number":["CCF-20-07067"]}]},{"name":"National Science Foundation","award":["CCF-20-07108"],"award-info":[{"award-number":["CCF-20-07108"]}]},{"name":"National Science Foundation","award":["CCF-20-45656"],"award-info":[{"award-number":["CCF-20-45656"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>We consider the storage\u2013retrieval rate trade-off in private information retrieval (PIR) systems using a Shannon-theoretic approach. Our focus is mostly on the canonical two-message two-database case, for which a coding scheme based on random codebook generation and the binning technique is proposed. This coding scheme reveals a hidden connection between PIR and the classic multiple description source coding problem. We first show that when the retrieval rate is kept optimal, the proposed non-linear scheme can achieve better performance over any linear scheme. Moreover, a non-trivial storage-retrieval rate trade-off can be achieved beyond space-sharing between this extreme point and the other optimal extreme point, achieved by the retrieve-everything strategy. We further show that with a method akin to the expurgation technique, one can extract a zero-error PIR code from the random code. Outer bounds are also studied and compared to establish the superiority of the non-linear codes over linear codes.<\/jats:p>","DOI":"10.3390\/info14010044","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T03:40:35Z","timestamp":1673408435000},"page":"44","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Shannon-Theoretic Approach to the Storage\u2013Retrieval Trade-Off in PIR Systems"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8752-6141","authenticated-orcid":false,"given":"Chao","family":"Tian","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77845, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8777-7987","authenticated-orcid":false,"given":"Hua","family":"Sun","sequence":"additional","affiliation":[{"name":"Department Electrical Engineering, University of North Texas, Denton, TX 76203, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8084-9332","authenticated-orcid":false,"given":"Jun","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, McMaster University, Hamilton, ON L8S 4K1, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"key":"ref_1","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. (1995, January 23\u201325). Private information retrieval. Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Shah, N., Rashmi, K., and Ramchandran, K. (July, January 29). One extra bit of download ensures perfectly private information retrieval. Proceedings of the 2014 IEEE International Symposium on Information Theory (ISIT), Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6874954"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Fazeli, A., Vardy, A., and Yaakobi, E. (2015, January 14\u201319). Codes for distributed PIR with low storage overhead. Proceedings of the 2015 Proceedings of IEEE International Symposium on Information Theory (ISIT), Hong Kong, China.","DOI":"10.1109\/ISIT.2015.7282977"},{"key":"ref_4","unstructured":"Rao, S., and Vardy, A. (2016). Lower bound on the redundancy of PIR codes. arXiv."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"6136","DOI":"10.1109\/TIT.2019.2920975","article-title":"PIR array codes with optimal virtual server rate","volume":"65","author":"Blackburn","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1109\/TIT.2019.2942311","article-title":"PIR schemes with small download complexity and low storage requirements","volume":"66","author":"Blackburn","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5565","DOI":"10.1109\/TIT.2019.2920635","article-title":"On private information retrieval array codes","volume":"65","author":"Zhang","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Vajha, M., Ramkumar, V., and Kumar, P.V. (2017, January 25\u201330). Binary, shortened projective Reed Muller codes for coded private information retrieval. Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), Aachen, Germany.","DOI":"10.1109\/ISIT.2017.8007009"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1109\/TIT.2018.2852294","article-title":"Nearly optimal constructions of PIR and batch codes","volume":"65","author":"Asi","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Chan, T.H., Ho, S.W., and Yamamoto, H. (2015, January 14\u201319). Private information retrieval for coded storage. Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT), Hong Kong, China.","DOI":"10.1109\/ISIT.2015.7282975"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"4075","DOI":"10.1109\/TIT.2017.2689028","article-title":"The capacity of private information retrieval","volume":"63","author":"Sun","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"7081","DOI":"10.1109\/TIT.2018.2815607","article-title":"Private information retrieval from MDS coded data in distributed storage systems","volume":"64","author":"Tajeddine","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1945","DOI":"10.1109\/TIT.2018.2791994","article-title":"The capacity of private information retrieval from coded databases","volume":"64","author":"Banawan","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"7613","DOI":"10.1109\/TIT.2019.2918207","article-title":"Capacity-achieving private information retrieval codes with optimal message size and upload cost","volume":"65","author":"Tian","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4904","DOI":"10.1109\/TIT.2020.2977073","article-title":"Capacity-achieving private information retrieval codes from MDS-coded databases with minimum message size","volume":"66","author":"Zhou","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2361","DOI":"10.1109\/TIT.2017.2777490","article-title":"The capacity of robust private information retrieval with colluding databases","volume":"64","author":"Sun","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1109\/JSAC.2022.3142358","article-title":"Private retrieval, computing and learning: Recent progress and future challenges","volume":"40","author":"Ulukus","year":"2022","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"6617","DOI":"10.1109\/TIT.2020.3023016","article-title":"The capacity of private information retrieval from uncoded storage constrained databases","volume":"66","author":"Attia","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"5743","DOI":"10.1109\/TIT.2018.2789426","article-title":"Multiround private information retrieval: Capacity and storage overhead","volume":"64","author":"Sun","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Sun, H., and Tian, C. (2019). Breaking the MDS-PIR capacity barrier via joint storage coding. Information, 10.","DOI":"10.3390\/info10090265"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1109\/JSAIT.2021.3053217","article-title":"New results on the storage-retrieval tradeoff in private information retrieval systems","volume":"2","author":"Guo","year":"2021","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Tian, C., Sun, H., and Chen, J. (2018, January 17\u201320). A Shannon-theoretic approach to the storage-retrieval tradeoff in PIR systems. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437874"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1109\/TIT.1982.1056588","article-title":"Achievable rates for multiple descriptions","volume":"28","author":"Gamal","year":"1982","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"7539","DOI":"10.1109\/TIT.2020.3015818","article-title":"On the storage cost of private information retrieval","volume":"66","author":"Tian","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2106","DOI":"10.1109\/TIT.2003.815767","article-title":"Multiple description coding with many channels","volume":"49","author":"Venkataramani","year":"2003","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1976.1055508","article-title":"The rate-distortion function for source coding with side information at the decoder","volume":"22","author":"Wyner","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1109\/TIT.2003.821998","article-title":"n-channel symmetric multiple descriptions-part I: (n,k) source-channel erasure codes","volume":"50","author":"Pradhan","year":"2004","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"5344","DOI":"10.1109\/TIT.2010.2059651","article-title":"New coding schemes for the symmetric K-description problem","volume":"56","author":"Tian","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1109\/TIT.1977.1055690","article-title":"Source coding with side information at several decoders","volume":"23","author":"Sgarro","year":"1977","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/14\/1\/44\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:06:38Z","timestamp":1760119598000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/14\/1\/44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,11]]},"references-count":29,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["info14010044"],"URL":"https:\/\/doi.org\/10.3390\/info14010044","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,11]]}}}