DPF-PIR: a scheme of feasible two-server keyword PIR with logarithmic communication
摘要
Private information retrieval (PIR) allows a client to privately request a block of data from a database such that no information about the queried block is revealed to the database owner. With the rapid rise of cloud computing, data is often shared across multiple servers, making multi-server PIR a promising privacy-enhancing technology. As the demand for faster keyword PIR protocols increases, current single-server PIR schemes suffer from significant computational and communication costs, while two-server PIR schemes demonstrate superior performance in this regard. In this paper, we address the problem of the keyword PIR against some adversary who can corrupt at most one party in our protocols in the semi-honest setting. A feasible two-server scheme DPF-PIR is presented, inspired by the original employment of the distributed point function. Without the need of downloading some “hint” about the database, DPF-PIR can achieve similar throughput results with the state-of-the-art single-server scheme, SimplePIR, and 25.5× faster than previous schemes. Meanwhile, the communication cost of DPF-PIR, which exhibits logarithmic complexity, is significantly lower compared to other schemes; for example, it is less than 2% of the communication cost of SimplePIR. We also present a variant of our scheme, PDPF-PIR, rendering the non-collusion assumption more acceptable in practice. Despite the decreased throughput due to heavier computational costs, PDPF-PIR is still at least 2× faster than previous single-server schemes.