{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:24:45Z","timestamp":1760235885673,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T00:00:00Z","timestamp":1632960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We consider the problem of Private Information Retrieval with Private Side Information (PIR-PSI), wherein the privacy of the demand and the side information are jointly preserved. Although the capacity of the PIR-PSI setting is known, we observe that the underlying capacity-achieving code construction uses Maximum Distance Separable (MDS) codes therefore contributing to high computational complexity when retrieving the demand. Pointing at this drawback of MDS-based PIR-PSI codes, we propose XOR-based PIR-PSI codes for a simple yet non-trivial setting of two non-colluding databases and two side information files at the user. Although our codes offer substantial reduction in complexity when compared to MDS-based codes, the code-rate marginally falls short of the capacity of the PIR-PSI setting. Nevertheless, we show that our code-rate is strictly higher than that of XOR-based codes for PIR with no side information. As a result, our codes can be useful when privately downloading a file especially after having downloaded a few other messages privately from the same database at an earlier time-instant.<\/jats:p>","DOI":"10.3390\/e23101287","type":"journal-article","created":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T10:22:42Z","timestamp":1632997362000},"page":"1287","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Existence of XOR-Based Codes for Private Information Retrieval with Private Side Information"],"prefix":"10.3390","volume":"23","author":[{"given":"Murali","family":"Krishnan K. H.","sequence":"first","affiliation":[{"name":"Bharti School of Telecom Technology and Management, Indian Institute of Technology Delhi, New Delhi 110016, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7333-4958","authenticated-orcid":false,"given":"Jagadeesh","family":"Harshan","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Indian Institute of Technology Delhi, New Delhi 110016, India"}]}],"member":"1968","published-online":{"date-parts":[[2021,9,30]]},"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","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_3","unstructured":"Lex, C.J., and Gnilke, O.W. (2021). Low-Complexity PIR Using Subfield Subcodes. arXiv."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Xu, J., and Zhang, Z. (2018, January 17\u201322). Building capacity-achieving PIR schemes with optimal sub-packetization over small fields. Proceedings of the IEEE International Symposium on Information Theory, Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437880"},{"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","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_7","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_8","doi-asserted-by":"crossref","unstructured":"Tandon, R. (2017, January 3\u20136). The capacity of cache aided private information retrieval. Proceedings of the 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2017.8262857"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Heidarzadeh, A., Kazemi, F., and Sprintson, A. (2018, January 25\u201329). Capacity of Single-Server Single-Message Private Information Retrieval with Coded Side Information. Proceedings of the 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613304"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Kazemi, F., Karimi, E., Heidarzadeh, A., and Sprintson, A. (2019, January 24\u201327). Private Information Retrieval with Private Coded Side Information: The Multi-Server Case. Proceedings of the 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2019.8919808"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Li, S., and Gastpar, M. (2020, January 18\u201320). Converse for Multi-Server Single-Message PIR with Side Information. Proceedings of the 2020 54th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, USA.","DOI":"10.1109\/CISS48834.2020.1570612786"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Wei, Y., and Ulukus, S. (2018, January 25\u201329). Private Information Retrieval with Private Side Information Under Storage Constraints. Proceedings of the 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613374"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Shariatpanahi, S.P., Siavoshani, M.J., and Maddah-Ali, M.A. (2018, January 25\u201329). Multi-Message Private Information Retrieval with Private Side Information. Proceedings of the 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613486"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kadhe, S., Garcia, B., Heidarzadeh, A., Rouayheb, S.E., and Sprintson, A. (2017, January 3\u20136). Private information retrieval with side information: The single server case. Proceedings of the 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2017.8262860"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"4761","DOI":"10.1109\/TIT.2020.2977919","article-title":"The Capacity of T-Private Information Retrieval With Private Side Information","volume":"65","author":"Chen","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1109\/TIT.2018.2848977","article-title":"The Capacity of Symmetric Private Information Retrieval","volume":"65","author":"Sun","year":"2018","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2920","DOI":"10.1109\/TIFS.2017.2725225","article-title":"Optimal Download Cost of Private Information Retrieval for Arbitrary Message Length","volume":"12","author":"Sun","year":"2017","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_18","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_19","doi-asserted-by":"crossref","unstructured":"Tan, X., Huang, C., and Ji, L. (2018, January 3\u20135). Access Control Scheme Based on Combination of Blockchain and XOR-Coding for ICN. Proceedings of the 5th IEEE International Conference on Cyber Security and Cloud Computing (CSCloud), New York, NY, USA.","DOI":"10.1109\/CSCloud\/EdgeCom.2018.00036"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Chou, R.A., and Kliewer, J. (2020, January 21\u201326). Secure Distributed Storage: Rate-Privacy Trade-Off and XOR-Based Coding Scheme. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174383"},{"key":"ref_21","first-page":"7287","article-title":"GUI-based software modularization through module clustering in edge computing based IoT environments","volume":"22","author":"Seo","year":"2019","journal-title":"J. Ambient. Intell. Humaniz. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1109\/TCC.2014.2344662","article-title":"Privacy-Preserving Data Storage in Cloud Using Array BP-XOR Codes","volume":"3","author":"Wang","year":"2005","journal-title":"IEEE Trans. Cloud Comput."},{"key":"ref_23","unstructured":"Harshan, J. (2021). XOR-Based Codes for Private Information Retrieval with Private Side Information. arXiv."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/10\/1287\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:07:48Z","timestamp":1760166468000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/10\/1287"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,30]]},"references-count":23,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2021,10]]}},"alternative-id":["e23101287"],"URL":"https:\/\/doi.org\/10.3390\/e23101287","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,9,30]]}}}