{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T15:45:21Z","timestamp":1780674321316,"version":"3.54.1"},"reference-count":29,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T00:00:00Z","timestamp":1566432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>The capacity of private information retrieval (PIR) from databases coded using maximum distance separable (MDS) codes was previously characterized by Banawan and Ulukus, where it was assumed that the messages are encoded and stored separably in the databases. This assumption was also usually made in other related works in the literature, and this capacity is usually referred to as the MDS-PIR capacity colloquially. In this work, we considered the question of if and when this capacity barrier can be broken through joint encoding and storing of the messages. Our main results are two classes of novel code constructions, which allow joint encoding, as well as the corresponding PIR protocols, which indeed outperformed the separate MDS-coded systems. Moreover, we show that a simple, but novel expansion technique allows us to generalize these two classes of codes, resulting in a wider range of the cases where this capacity barrier can be broken.<\/jats:p>","DOI":"10.3390\/info10090265","type":"journal-article","created":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T10:15:07Z","timestamp":1566555307000},"page":"265","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Breaking the MDS-PIR Capacity Barrier via Joint Storage Coding"],"prefix":"10.3390","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8777-7987","authenticated-orcid":false,"given":"Hua","family":"Sun","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, University of North Texas, Denton, TX 76203, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8752-6141","authenticated-orcid":false,"given":"Chao","family":"Tian","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Texas A&amp;M University, College Station, TX 77843, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/293347.293350","article-title":"Private Information Retrieval","volume":"45","author":"Chor","year":"1998","journal-title":"J. ACM (JACM)"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Sun, H., and Jafar, S.A. (2016, January 4\u20138). The capacity of private information retrieval. Proceedings of the 2016 IEEE Global Communications Conference (GLOBECOM), Washington, DC, USA.","DOI":"10.1109\/GLOCOM.2016.7842315"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Shah, N.B., 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_4","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1137\/16M1102562","article-title":"Private information retrieval from coded databases with colluding servers","volume":"1","author":"Gnilke","year":"2017","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"ref_5","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_6","doi-asserted-by":"crossref","unstructured":"Tajeddine, R., and Rouayheb, S.E. (2016). Private Information Retrieval from MDS Coded Data in Distributed Storage Systems. arXiv.","DOI":"10.1109\/ISIT.2016.7541531"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"100306:1","DOI":"10.1007\/s11432-018-9538-4","article-title":"On Sub-Packetization and Access Number of Capacity-Achieving PIR Schemes for MDS Coded Non-Colluding Databases","volume":"61","author":"Xu","year":"2018","journal-title":"Sci. China Inf. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"4243","DOI":"10.1109\/TIT.2019.2900313","article-title":"Achieving maximum distance separable private information retrieval capacity with linear codes","volume":"65","author":"Kumar","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Attia, M.A., Kumar, D., and Tandon, R. (2018). The capacity of private information retrieval from uncoded storage constrained databases. arXiv.","DOI":"10.1109\/ISIT.2018.8437729"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Woolsey, N., Chen, R.R., and Ji, M. (2019). An Optimal Iterative Placement Algorithm for PIR from Heterogeneous Storage-Constrained Databases. arXiv.","DOI":"10.1109\/GLOBECOM38437.2019.9013430"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Banawan, K., Arasli, B., Wei, Y.P., and Ulukus, S. (2019). The Capacity of Private Information Retrieval from Heterogeneous Uncoded Caching Databases. arXiv.","DOI":"10.1109\/ISIT.2019.8849652"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Raviv, N., and Tamot, I. (2018, January 17\u201322). Private Information Retrieval in Graph Based Replication Systems. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437311"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Lin, H.Y., Kumar, S., Rosnes, E., and i Amat, A.G. (2018). On the fundamental limit of private information retrieval for coded distributed storage. arXiv.","DOI":"10.1109\/ITW.2018.8613500"},{"key":"ref_14","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_15","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_16","doi-asserted-by":"crossref","unstructured":"Tian, C., Sun, H., and Chen, J. (2018, January 17\u201322). 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_17","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 IEEE International Symposium on Information Theory (ISIT), Hong Kong, China.","DOI":"10.1109\/ISIT.2015.7282977"},{"key":"ref_18","unstructured":"Rao, S., and Vardy, A. (2016). Lower Bound on the Redundancy of PIR Codes. arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Blackburn, S.R., and Etzion, T. (2019). PIR array codes with optimal virtual server rate. IEEE Trans. Inf. Theory.","DOI":"10.1109\/TIT.2019.2920975"},{"key":"ref_20","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_21","unstructured":"Skachek, V. (2018). Batch and PIR codes. Network Coding and Subspace Designs, Springer."},{"key":"ref_22","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_23","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_24","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.1109\/TIT.2017.2779454","article-title":"Private Information Retrieval from MDS Coded Data with Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.","volume":"64","author":"Sun","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Wang, Q., and Skoglund, M. (2017, January 21\u201325). Symmetric private information retrieval for MDS coded distributed storage. Proceedings of the 2017 IEEE International Conference on Communications (ICC), Paris, France.","DOI":"10.1109\/ICC.2017.7997029"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Zhou, R., Tian, C., Liu, T., and Sun, H. (2019, January 7\u201312). Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849542"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1112\/jlms\/s1-31.4.445","article-title":"The rank of circulant matrices","volume":"1","author":"Ingleton","year":"1956","journal-title":"J. Lond. Math. Soc."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Lidl, R., and Niederreiter, H. (1994). Introduction to Finite Fields and Their Applications, Cambridge University Press.","DOI":"10.1017\/CBO9781139172769"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01020648","article-title":"Exact results for deterministic cellular automata with additive rules","volume":"43","author":"Guan","year":"1986","journal-title":"J. Stat. Phys."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/9\/265\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:13:04Z","timestamp":1760188384000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/10\/9\/265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,22]]},"references-count":29,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9]]}},"alternative-id":["info10090265"],"URL":"https:\/\/doi.org\/10.3390\/info10090265","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,22]]}}}