BstPIR: Keyword Private Information Retrieval Based on Binary Search Trees
Kexin Xu, Li Su, Shen He, Shan Chen, Huizheng Geng · IEEE Internet of Things Journal · 2025
In Internet of Things (IoT) systems, the storage and retrieval of data are often provided by remote servers (e.g., the cloud) due to the constrained resources of devices. Private information retrieval (PIR) is an important cryptographic tool that enables a client to access data from a server without disclosing the client’s intention, which guarantees the query privacy of the device. In this article, we design BstPIR, a novel keyword PIR protocol tailored for resource-constrained devices. To this end, based on fully homomorphic encryption (FHE) over rings, we first construct a 3-way homomorphic comparison and multiplexer, which could be of independent interest. The algorithm is then utilized to conduct blind path selections on the database with a binary search tree (BST) structure, and homomorphically extract retrieval results. Compared to state-of-the-art works, BstPIR achieves optimal computational and communicational overheads for the client as well as competitive performance for the server. A proof-of-concept implementation demonstrates this. Furthermore, our proposal supports dynamic data insertion and database privacy preservation without almost introducing additional costs.