{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,7]],"date-time":"2025-12-07T06:44:08Z","timestamp":1765089848222,"version":"build-2065373602"},"reference-count":50,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2025,9,18]],"date-time":"2025-09-18T00:00:00Z","timestamp":1758153600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62201080"],"award-info":[{"award-number":["62201080"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>The problem of graph-based X-secure T-private linear computation (GXSTPLC) is to allow a user to retrieve a linear combination of K messages from a set of N distributed servers that store the messages in a graph-based fashion, i.e., each message is restricted to be distributed among a subset of servers. T-privacy requires that the coefficients of the linear combination are not revealed to any group of up to T colluding servers, and X-security guarantees that any set of up to X colluding servers learns nothing about the messages. In this paper, we propose an achievability scheme for GXSTPLC that enables a storage\u2013communication trade-off by exploiting non-replicated storage codes. Novel aspects of our achievability scheme include the usage of the idea of cross-subspace alignment null shaper that addresses various challenges posed by the graph-based storage structure. In addition, unlike previous works, our scheme allows a direct transformation into a quantum one to achieve a superdense coding gain by leveraging the idea of N-Sum Box abstraction of quantum \u201cover-the-air\u201d computing.<\/jats:p>","DOI":"10.3390\/e27090975","type":"journal-article","created":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:08:58Z","timestamp":1758276538000},"page":"975","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Storage\u2013Communication Trade-Off in Graph-Based X-Secure T-Private Linear Computation"],"prefix":"10.3390","volume":"27","author":[{"given":"Yueyang","family":"Liu","sequence":"first","affiliation":[{"name":"School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-8018-9011","authenticated-orcid":false,"given":"Haobo","family":"Jia","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuqing","family":"Jia","sequence":"additional","affiliation":[{"name":"School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing 100876, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,18]]},"reference":[{"key":"ref_1","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_2","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_3","doi-asserted-by":"crossref","first-page":"3880","DOI":"10.1109\/TIT.2018.2888494","article-title":"The Capacity of Private Computation","volume":"65","author":"Sun","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Tahmasebi, B., and Maddah-Ali, M.A. (2020, January 21\u201326). Private Function Computation. Proceedings of the 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA.","DOI":"10.1109\/ISIT44484.2020.9174370"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1109\/JSAIT.2021.3053481","article-title":"Double blind T-private information retrieval","volume":"2","author":"Lu","year":"2021","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1109\/TIFS.2019.2925723","article-title":"Private Polynomial Computation From Lagrange Encoding","volume":"15","author":"Raviv","year":"2020","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"4709","DOI":"10.1109\/TIT.2020.2977082","article-title":"The Asymptotic Capacity of Private Search","volume":"66","author":"Chen","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"6841","DOI":"10.1109\/TIT.2021.3100476","article-title":"The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns for Replicated Databases","volume":"67","author":"Yao","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","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_10","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_11","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_12","doi-asserted-by":"crossref","first-page":"3898","DOI":"10.1109\/TIT.2018.2890285","article-title":"Private Information Retrieval From Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers","volume":"65","author":"Tajeddine","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","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_14","doi-asserted-by":"crossref","first-page":"5160","DOI":"10.1109\/TIT.2019.2903206","article-title":"Symmetric Private Information Retrieval from MDS Coded Distributed Storage with Non-Colluding and Colluding Servers","volume":"65","author":"Wang","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1109\/JSAC.2022.3142362","article-title":"Private Linear Computation for Noncolluding Coded Databases","volume":"40","author":"Obead","year":"2022","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2001","DOI":"10.1109\/TIT.2021.3125006","article-title":"Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective","volume":"68","author":"Wang","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"2032","DOI":"10.1109\/TIT.2019.2948845","article-title":"Private Information Retrieval with Side Information","volume":"66","author":"Kadhe","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"3215","DOI":"10.1109\/TIT.2018.2883302","article-title":"Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching","volume":"65","author":"Wei","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"8222","DOI":"10.1109\/TIT.2019.2936023","article-title":"The Capacity of Private Information Retrieval with Partially Known Private Side Information","volume":"65","author":"Wei","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","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":"66","author":"Chen","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_21","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_22","doi-asserted-by":"crossref","first-page":"3198","DOI":"10.1109\/TIT.2018.2884891","article-title":"The Capacity of Private Information Retrieval with Eavesdroppers","volume":"65","author":"Wang","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2953","DOI":"10.1109\/TIFS.2018.2833050","article-title":"Private Information Retrieval for Secure Distributed Storage Systems","volume":"13","author":"Yang","year":"2018","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"5783","DOI":"10.1109\/TIT.2019.2916079","article-title":"Cross subspace alignment and the asymptotic capacity of X-secure T-private information retrieval","volume":"65","author":"Jia","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"7427","DOI":"10.1109\/TIT.2020.3013152","article-title":"X-secure T-private information retrieval from MDS coded storage with byzantine and unresponsive servers","volume":"66","author":"Jia","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"6280","DOI":"10.1109\/TIT.2020.3011053","article-title":"On the asymptotic capacity of X-secure T-private information retrieval with graph-Based replicated storage","volume":"66","author":"Jia","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"5418","DOI":"10.1109\/TIT.2022.3165400","article-title":"X-secure T-private federated submodel learning with elastic dropout resilience","volume":"68","author":"Jia","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_28","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":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2704","DOI":"10.1109\/TIT.2022.3140890","article-title":"Symmetric private polynomial computation from Lagrange encoding","volume":"68","author":"Zhu","year":"2022","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_30","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_31","doi-asserted-by":"crossref","first-page":"7628","DOI":"10.1109\/TIT.2019.2933011","article-title":"Asymmetry hurts: Private information retrieval under asymmetric traffic constraints","volume":"65","author":"Banawan","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_32","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_33","doi-asserted-by":"crossref","unstructured":"Jia, Z., Sun, H., and Jafar, S.A. (2017, January 4\u20138). The Capacity of Private Information Retrieval with Disjoint Colluding Sets. Proceedings of the GLOBECOM 2017\u20142017 IEEE Global Communications Conference, Singapore.","DOI":"10.1109\/GLOCOM.2017.8254170"},{"key":"ref_34","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_35","doi-asserted-by":"crossref","first-page":"3590","DOI":"10.1109\/TIT.2019.2955053","article-title":"Private Information Retrieval in Graph-Based Replication Systems","volume":"66","author":"Raviv","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1109\/TIFS.2022.3220034","article-title":"Bounds on the Capacity of Private Information Retrieval Over Graphs","volume":"18","author":"Sadeh","year":"2023","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Banawan, K., and Ulukus, S. (2019, January 7\u201312). Private Information Retrieval from Non-Replicated Databases. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France.","DOI":"10.1109\/ISIT.2019.8849399"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"5269","DOI":"10.1109\/TIT.2024.3388597","article-title":"The Asymptotic Capacity of X-Secure T-Private Linear Computation with Graph Based Replicated Storage","volume":"70","author":"Jia","year":"2024","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Nomeir, M., Vithana, S., and Ulukus, S. (2024, January 13\u201315). Asymmetric X-Secure T-Private Information Retrieval: More Databases is Not Always Better. Proceedings of the 2024 58th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, USA.","DOI":"10.1109\/CISS59072.2024.10480209"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Aytekin, A., Nomeir, M., Vithana, S., and Ulukus, S. (2023, January 4\u20138). Quantum Symmetric Private Information Retrieval with Secure Storage and Eavesdroppers. Proceedings of the 2023 IEEE Globecom Workshops (GC Wkshps), Kuala Lumpur, Malaysia.","DOI":"10.1109\/GCWkshps58843.2023.10464963"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1109\/TIT.2020.3022515","article-title":"Capacity of Quantum Private Information Retrieval with Multiple Servers","volume":"67","author":"Song","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"5491","DOI":"10.1109\/TIT.2021.3077269","article-title":"Capacity of Quantum Private Information Retrieval with Colluding Servers","volume":"67","author":"Song","year":"2021","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"885","DOI":"10.1109\/JSAC.2022.3142363","article-title":"On the Capacity of Quantum Private Information Retrieval From MDS-Coded and Colluding Servers","volume":"40","author":"Allaix","year":"2022","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Lu, Y., and Jafar, S.A. (November, January 29). Quantum Cross Subspace Alignment Codes via the N-sum Box Abstraction. Proceedings of the 2023 57th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA.","DOI":"10.1109\/IEEECONF59524.2023.10477050"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1109\/JSAIT.2025.3554625","article-title":"Quantum X-Secure T-Private Information Retrieval From MDS Coded Storage with Unresponsive and Byzantine Servers","volume":"6","author":"Lu","year":"2025","journal-title":"IEEE J. Sel. Areas Inf. Theory"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Karpuk, D. (2018, January 17\u201322). Private Computation of Systematically Encoded Data with Colluding Servers. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437349"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"1800","DOI":"10.1109\/TIFS.2022.3166667","article-title":"Private Polynomial Function Computation for Noncolluding Coded Databases","volume":"17","author":"Obead","year":"2022","journal-title":"IEEE Trans. Inf. Forensics Secur."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"3183","DOI":"10.1109\/TIT.2018.2878034","article-title":"On PIR and Symmetric PIR From Colluding Databases with Adversaries and Eavesdroppers","volume":"65","author":"Wang","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_49","unstructured":"Yu, Q., Li, S., Raviv, N., Kalan, S.M.M., Soltanolkotabi, M., and Avestimehr, S.A. (2019, January 16\u201318). Lagrange coded computing: Optimal design for resiliency, security, and privacy. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, PMLR, Naha, Japan."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1109\/TIT.2024.3514921","article-title":"N-Sum Box: An Abstraction for Linear Computation Over Many-to-One Quantum Networks","volume":"71","author":"Allaix","year":"2025","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/9\/975\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:48:22Z","timestamp":1760035702000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/9\/975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,18]]},"references-count":50,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["e27090975"],"URL":"https:\/\/doi.org\/10.3390\/e27090975","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2025,9,18]]}}}