VMkCwPIR: A Single-Round Scalable Multi-Keyword PIR Protocol Supporting Non-Primary Key Queries

Read full text Summarise with VIRAT
Authors: Junyu Lu, Shengnan Zhao, Yali Huang, Zhongtian Jia, Lili Zhang, Chuan Zhao
Cited by: 0
References: 30

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

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–Girard identities to encode multi-keyword selection into a compact algebraic representation, representing a functional extension of CwPIR (Usenix Security ’22). While this functional expansion introduces additional computational overhead due to the processing of multiple keywords, we further introduce VMkCwPIR—an 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.

Fields of Study & Subjects

Cryptography and Data Security Cloud Data Security Solutions Internet Traffic Analysis and Secure E-voting

Publication details

Journal / source
Information
Volume
17
Issue
4
Pages
337–337
Publication date
1 April 2026
Language
EN