{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T17:08:10Z","timestamp":1785431290288,"version":"3.56.0"},"reference-count":34,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"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":["62472252"],"award-info":[{"award-number":["62472252"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"award":["62472252"],"award-info":[{"award-number":["62472252"]}],"id":[{"id":"https:\/\/ror.org\/01h0zpd94","id-type":"ROR","asserted-by":"publisher"}]},{"name":"TaiShan Scholars Program","award":["tsqn202211280"],"award-info":[{"award-number":["tsqn202211280"]}]},{"name":"TaiShan Scholars Program","award":["tstp20240828"],"award-info":[{"award-number":["tstp20240828"]}]},{"DOI":"10.13039\/501100007129","name":"Shandong Provincial Natural Science Foundation","doi-asserted-by":"crossref","award":["ZR2024QF131"],"award-info":[{"award-number":["ZR2024QF131"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100007129","name":"Shandong Provincial Natural Science Foundation","doi-asserted-by":"crossref","award":["ZR2023LZH014"],"award-info":[{"award-number":["ZR2023LZH014"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"crossref"}]},{"award":["ZR2024QF131"],"award-info":[{"award-number":["ZR2024QF131"]}],"id":[{"id":"https:\/\/ror.org\/04aqat463","id-type":"ROR","asserted-by":"publisher"}]},{"award":["ZR2023LZH014"],"award-info":[{"award-number":["ZR2023LZH014"]}],"id":[{"id":"https:\/\/ror.org\/04aqat463","id-type":"ROR","asserted-by":"publisher"}]},{"name":"Department of Science & Technology of Shandong  Province","award":["SYS202201"],"award-info":[{"award-number":["SYS202201"]}]},{"award":["SYS202201"],"award-info":[{"award-number":["SYS202201"]}],"id":[{"id":"https:\/\/ror.org\/01b9fvd84","id-type":"ROR","asserted-by":"publisher"}]},{"name":"Research Project of Quan Cheng Laboratory, China","award":["QCL20250204"],"award-info":[{"award-number":["QCL20250204"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Keyword Private Information Retrieval (Keyword PIR) enables private querying over keyword-based databases, which are typically sparse, as opposed to the dense arrays used in standard Index PIR. However, existing Keyword PIR schemes are limited to single-keyword queries and generally assume that keywords serve as unique identifiers, making them inadequate for practical scenarios where keywords are non-unique attributes and clients need to retrieve records matching multiple keywords simultaneously. To bridge this gap, we propose MkCwPIR, the first single-round, exact-match multi-keyword PIR protocol that supports conjunctive keyword queries while preserving strict keyword privacy against the server. Our construction employs Constant-weight codes and Newton\u2013Girard identities to encode multi-keyword selection into a compact algebraic representation, representing a functional extension of CwPIR (Usenix Security \u201922). While this functional expansion introduces additional computational overhead due to the processing of multiple keywords, we further introduce VMkCwPIR\u2014an optimized variant leveraging BFV vectorized homomorphic encryption. Experimental results demonstrate that although the base MkCwPIR incurs higher latency due to its enhanced logical capabilities, the vectorized optimizations in VMkCwPIR effectively close this performance gap. Consequently, VMkCwPIR achieves a performance level comparable to the single-keyword CwPIR. Experimental results demonstrate that when processing a query with eight keywords, VMkCwPIR achieves a server-side execution time comparable to executing only four independent single-keyword queries in CwPIR, while maintaining constant communication overhead for up to 16 keywords.<\/jats:p>","DOI":"10.3390\/info17040337","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:09:21Z","timestamp":1775038161000},"page":"337","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["VMkCwPIR: A Single-Round Scalable Multi-Keyword PIR Protocol Supporting Non-Primary Key Queries"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-7474-9021","authenticated-orcid":false,"given":"Junyu","family":"Lu","sequence":"first","affiliation":[{"name":"Shandong Key Laboratory of Ubiquitous Intelligent Computing, University of Jinan, Jinan 250022, China"},{"name":"Quan Cheng Laboratory, Jinan 250103, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6883-9724","authenticated-orcid":false,"given":"Shengnan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Quan Cheng Laboratory, Jinan 250103, China"},{"name":"Shandong Key Laboratory of Ubiquitous Intelligent Computing, University of Jinan, Jinan 250022, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9660-3444","authenticated-orcid":false,"given":"Yuchen","family":"Huang","sequence":"additional","affiliation":[{"name":"Quan Cheng Laboratory, Jinan 250103, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9629-5159","authenticated-orcid":false,"given":"Zhongtian","family":"Jia","sequence":"additional","affiliation":[{"name":"Shandong Key Laboratory of Ubiquitous Intelligent Computing, University of Jinan, Jinan 250022, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lili","family":"Zhang","sequence":"additional","affiliation":[{"name":"Inspur Group Co., Ltd., Jinan 250000, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9106-6010","authenticated-orcid":false,"given":"Chuan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Shandong Key Laboratory of Ubiquitous Intelligent Computing, University of Jinan, Jinan 250022, China"},{"name":"Quan Cheng Laboratory, Jinan 250103, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2026,4,1]]},"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","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_3","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., and Orlov, I. (2012). Share conversion and private information retrieval. Proceedings of the 2012 IEEE 27th Conference on Computational Complexity, Porto, Portugal, 26\u201329 June 2012, IEEE.","DOI":"10.1109\/CCC.2012.23"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2968443","article-title":"2-server PIR with subpolynomial communication","volume":"63","author":"Dvir","year":"2016","journal-title":"J. ACM (JACM)"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kales, D., Omolola, O., and Ramacher, S. (2019). Revisiting user privacy for certificate transparency. Proceedings of the 2019 IEEE European Symposium on Security and Privacy (EuroS&P), Stockholm, Sweden, 17\u201319 June 2019, IEEE.","DOI":"10.1109\/EuroSP.2019.00039"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Mozaffari, H., and Houmansadr, A. (2020). Heterogeneous private information retrieval, Network and Distributed Systems Security (NDSS) Symposium 2020.","DOI":"10.14722\/ndss.2020.24363"},{"key":"ref_7","unstructured":"Eriguchi, R., Kurosawa, K., and Nuida, K. Multi-Server PIR with Full Error Detection and Limited Error Correction. Proceedings of the 3rd Conference on Information-Theoretic Cryptography, ITC 2022."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gong, T., Henry, R., Psomas, A., and Kate, A. (2024). More is merrier: Relax the non-collusion assumption in multi-server pir. Proceedings of the 2024 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 19\u201323 May 2024, IEEE.","DOI":"10.1109\/SP54263.2024.00095"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs, H., Henzinger, A., and Kogan, D. (2022). Single-server private information retrieval with sublinear amortized time. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-031-07085-3_1"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Zhou, M., Lin, W.K., Tselekounis, Y., and Shi, E. (2023). Optimal single-server private information retrieval. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-031-30545-0_14"},{"key":"ref_11","unstructured":"Menon, S.J., and Wu, D.J. (2024). YPIR: High-Throughput Single-Server PIR with Silent Preprocessing. 33rd USENIX Security Symposium (USENIX Security 24), USENIX Association."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Mughees, M.H., and Ren, L. (2023). Vectorized batch private information retrieval. Proceedings of the 2023 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 21\u201325 May 2023, IEEE.","DOI":"10.1109\/SP46215.2023.10179329"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Lazzaretti, A., and Papamanthou, C. (2023). TreePIR: Sublinear-time and polylog-bandwidth private information retrieval from DDH. Annual International Cryptology Conference, Springer.","DOI":"10.1007\/978-3-031-38545-2_10"},{"key":"ref_14","first-page":"393","article-title":"Committed Private Information Retrieval","volume":"Volume 14344","author":"Cao","year":"2024","journal-title":"ESORICS 2023: 28th European Symposium on Research in Computer Security"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Angel, S., Chen, H., Laine, K., and Setty, S. (2018). PIR with compressed queries and amortized query processing. Proceedings of the 2018 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 20\u201324 May 2018, IEEE.","DOI":"10.1109\/SP.2018.00062"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Mughees, M.H., Chen, H., and Ren, L. OnionPIR: Response efficient single-server PIR. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, 15\u201319 November 2021.","DOI":"10.1145\/3460120.3485381"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"365","DOI":"10.56553\/popets-2023-0022","article-title":"Frodopir: Simple, scalable, single-server private information retrieval","volume":"2023","author":"Davidson","year":"2023","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_18","unstructured":"Henzinger, A., Hong, M.M., Corrigan-Gibbs, H., Meiklejohn, S., and Vaikuntanathan, V. (2023). One server for the price of two: Simple and fast Single-Server private information retrieval. 32nd USENIX Security Symposium (USENIX Security 23), USENIX Association."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Zhou, M., Park, A., Zheng, W., and Shi, E. (2024). Piano: Extremely simple, single-server PIR with sublinear server computation. Proceedings of the 2024 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 19\u201323 May 2024, IEEE.","DOI":"10.1109\/SP54263.2024.00055"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Liu, J., Li, J., Wu, D., and Ren, K. (2024). PIRANA: Faster multi-query PIR via constant-weight codes. Proceedings of the 2024 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 19\u201323 May 2024, IEEE.","DOI":"10.1109\/SP54263.2024.00039"},{"key":"ref_21","unstructured":"Ali, A., Lepoint, T., Patel, S., Raykova, M., Schoppmann, P., Seth, K., and Yeo, K. (2021). Communication\u2013Computation trade-offs in PIR. 30th USENIX Security Symposium (USENIX Security 21), USENIX Association."},{"key":"ref_22","unstructured":"Mahdavi, R.A., and Kerschbaum, F. (2022). Constant-weight PIR: Single-round keyword PIR via constant-weight equality operators. 31st USENIX Security Symposium (USENIX Security 22), USENIX Association."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Celi, S., and Davidson, A. (2024). Call me by my name: Simple, practical private information retrieval for keyword queries. 2024 on ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery.","DOI":"10.1145\/3658644.3670271"},{"key":"ref_24","unstructured":"Hao, M., Liu, W., Peng, L., Zhang, C., Wu, P., Zhang, L., Li, H., and Deng, R.H. (2025). Practical Keyword Private Information Retrieval from Key-to-Index Mappings. 34th USENIX Security Symposium (USENIX Security 25), USENIX Association."},{"key":"ref_25","unstructured":"Gentry, C. (June, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Van Dijk, M., Gentry, C., Halevi, S., and Vaikuntanathan, V. (2010). Fully homomorphic encryption over the integers. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-642-13190-5_2"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Gentry, C., and Halevi, S. (2011). Implementing gentry\u2019s fully-homomorphic encryption scheme. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-642-20465-4_9"},{"key":"ref_28","unstructured":"Fan, J., and Vercauteren, F. (2012). Somewhat practical fully homomorphic encryption. Cryptol. ePrint Arch."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2633600","article-title":"(Leveled) fully homomorphic encryption without bootstrapping","volume":"6","author":"Brakerski","year":"2014","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017). Homomorphic encryption for arithmetic of approximate numbers. International Conference on the Theory and Application of Cryptology and Information Security, Springer.","DOI":"10.1007\/978-3-319-70694-8_15"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10623-012-9720-4","article-title":"Fully homomorphic SIMD operations","volume":"71","author":"Smart","year":"2014","journal-title":"Des. Codes Cryptogr."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Castryck, W., Iliashenko, I., and Vercauteren, F. (2018). Homomorphic SIMD Operations: Single Instruction Much More Data. Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer.","DOI":"10.1007\/978-3-319-78381-9_13"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Menon, S.J., and Wu, D.J. (2022). Spiral: Fast, high-rate single-server PIR via FHE composition. Proceedings of the 2022 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 22\u201326 May 2022, IEEE.","DOI":"10.1109\/SP46214.2022.9833700"},{"key":"ref_34","unstructured":"Microsoft (2026, March 18). Microsoft SEAL: Release 4.1. Available online: https:\/\/github.com\/microsoft\/SEAL."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/17\/4\/337\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T04:14:35Z","timestamp":1775189675000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/17\/4\/337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":34,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2026,4]]}},"alternative-id":["info17040337"],"URL":"https:\/\/doi.org\/10.3390\/info17040337","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]}}}