{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,25]],"date-time":"2025-12-25T05:21:16Z","timestamp":1766640076936,"version":"3.48.0"},"reference-count":28,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T00:00:00Z","timestamp":1766448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education Academic Research","doi-asserted-by":"publisher","award":["24\/25"],"award-info":[{"award-number":["24\/25"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education Academic Research","doi-asserted-by":"publisher","award":["MOE-T2EP20223-0016"],"award-info":[{"award-number":["MOE-T2EP20223-0016"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation, Singapore","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We consider the problem of designing a Private Information Retrieval (PIR) scheme for n files replicated on k servers that can collude and return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We focus on minimizing download costs and propose PIR schemes with minimal download costs and the smallest file size (proportional to the number of involved servers). Motivated by the possible presence of stragglers, we extend our previous conference results and propose a scheme in which the number of participating servers may vary.<\/jats:p>","DOI":"10.3390\/e28010015","type":"journal-article","created":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T10:57:18Z","timestamp":1766487438000},"page":"15","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Optimal File Size of Capacity-Achieving Byzantine-Resistant Private Information Retrieval Schemes"],"prefix":"10.3390","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9557-5197","authenticated-orcid":false,"given":"Stanislav","family":"Kruglik","sequence":"first","affiliation":[{"name":"Department of Electrical and Photonics Engineering, Technical University of Denmark, 2800 Kongens Lyngby, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5611-0848","authenticated-orcid":false,"given":"Han Mao","family":"Kiah","sequence":"additional","affiliation":[{"name":"School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637121, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2276-017X","authenticated-orcid":false,"given":"Son Hoang","family":"Dau","sequence":"additional","affiliation":[{"name":"School of Computing Technologies, Royal Melbourne Institute of Technology, Melbourne 3001, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7669-8922","authenticated-orcid":false,"given":"Huaxiong","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637121, Singapore"}]}],"member":"1968","published-online":{"date-parts":[[2025,12,23]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., and Skeith, W.E. (2007). A Survey of Single-Database Private Information Retrieval: Techniques and Applications. Public Key Cryptography (PKC), Springer.","DOI":"10.1007\/978-3-540-71677-8_26"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Qin, K., Hadass, H., Gervais, A., and Reardon, J. (2019, January 24\u201326). Applying private information retrieval to lightweight bitcoin clients. Proceedings of the 2019 Crypto Valley Conference on Blockchain Technology (CVCBT), Rotkreuz, Switzerland.","DOI":"10.1109\/CVCBT.2019.00012"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Xie, Y., Zhang, C., Wei, L., Niu, Y., Wang, F., and Liu, J. (2019, January 11\u201313). A privacy-preserving Ethereum lightweight client using PIR. Proceedings of the 2019 IEEE\/CIC International Conference on Communications in China (ICCC), Changchun, China.","DOI":"10.1109\/ICCChina.2019.8855900"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1109\/JSTSP.2015.2432740","article-title":"Efficient Private Information Retrieval Over Unsynchronized Databases","volume":"9","author":"Fanti","year":"2015","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s00145-007-0424-2","article-title":"Robust information-theoretic private information retrieval","volume":"20","author":"Beimel","year":"2007","journal-title":"J. Cryptol."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1206","DOI":"10.1109\/TIT.2018.2869154","article-title":"The Capacity of Private Information Retrieval from Byzantine and Colluding Databases","volume":"65","author":"Banawan","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kurosawa, K. (2019, January 8\u201312). How to Correct Errors in Multi-server PIR. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan.","DOI":"10.1007\/978-3-030-34621-8_20"},{"key":"ref_9","unstructured":"Devet, K., Goldberg, I., and Heninger, N. (2012, January 8\u201310). Optimally Robust Private Information Retrieval. Proceedings of the 21st USENIX Security Symposium (USENIX Security), Berkeley, CA, USA."},{"key":"ref_10","unstructured":"Jajodia, S., Samarati, P., and Yung, M. (2019). Robust Private Information Retrieval. Encyclopedia of Cryptography, Security and Privacy, Springer."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wang, Q., Sun, H., and Skoglund, M. (2018, January 25\u201329). The \u03f5-error capacity of symmetric pir with byzantine adversaries. Proceedings of the 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613332"},{"key":"ref_12","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_13","doi-asserted-by":"crossref","unstructured":"Uezato, Y. (2021, January 14\u201319). Accelerating XOR-based erasure coding using program optimization techniques. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), St. Louis, MO, USA.","DOI":"10.1145\/3458817.3476204"},{"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":"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 servers","volume":"61","author":"Xu","year":"2018","journal-title":"Sci. China Inf. Sci."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1248","DOI":"10.1109\/TIFS.2019.2937634","article-title":"A New Capacity-Achieving Private Information Retrieval Scheme with (Almost) Optimal File Length for Coded Servers","volume":"15","author":"Zhu","year":"2020","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_17","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_18","doi-asserted-by":"crossref","first-page":"2723","DOI":"10.1109\/TIT.2018.2883283","article-title":"The Optimal Sub-Packetization of Linear Capacity-Achieving PIR Schemes With Colluding Servers","volume":"65","author":"Zhang","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Kruglik, S., Dau, S.H., Kiah, H.M., and Wang, H. (2023, January 25\u201330). k-server Byzantine-Resistant PIR Scheme with Optimal Download Rate and Optimal File Size. Proceedings of the 2023 IEEE International Symposium on Information Theory (ISIT), Taipei, Taiwan.","DOI":"10.1109\/ISIT54713.2023.10206768"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1109\/TIT.2021.3123692","article-title":"Communication Efficient Secret Sharing with Small Share Size","volume":"68","author":"Ding","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"7439","DOI":"10.1109\/TIT.2020.3017666","article-title":"Enabling Optimal Access and Error Correction for the Repair of Reed\u2013Solomon Codes","volume":"66","author":"Chen","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Lidl, R., and Niederreiter, H. (1996). Finite Fields, Cambridge University Press.","DOI":"10.1017\/CBO9780511525926"},{"key":"ref_23","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley-Interscience."},{"key":"ref_24","unstructured":"Blakley, G.R., and Meadows, C. (1984, January 9\u201311). Security of ramp schemes. Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques, Paris, France."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Roth, R.M. (2006). Introduction to Coding Theory, Cambridge University Press.","DOI":"10.1017\/CBO9780511808968"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1016\/j.ffa.2009.07.002","article-title":"The minimal polynomial over Fq of linear recurring sequence over Fqm","volume":"15","author":"Gao","year":"2009","journal-title":"Finite Fields Their Appl."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bitar, R., and Rouayheb, S.E. (2018, January 25\u201329). Staircase-PIR: Universally Robust Private Information Retrieval. Proceedings of the 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China.","DOI":"10.1109\/ITW.2018.8613532"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Bitar, R., and Jaggi, S. (2020, January 21\u201326). Communication Efficient Secret Sharing in the Presence of Malicious Adversary. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174266"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/1\/15\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,25]],"date-time":"2025-12-25T05:18:44Z","timestamp":1766639924000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/28\/1\/15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,23]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,1]]}},"alternative-id":["e28010015"],"URL":"https:\/\/doi.org\/10.3390\/e28010015","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2025,12,23]]}}}