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

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.