DMS-P$^{2}$2CQ: Privacy-Preserving Collaborative Query Protocol for Distributed Multi-Server Systems

A privacy-preserving collaborative query protocol for distributed multi-server systems (DMS-P$^{2}$CQ) enables a querying party to interact with multiple independent servers using an identifier$x_{u}$and receive a categorical decision (e.g.,Good/Moderate/Poor) determined by the total number of servers whose datasets contain$x_{u}$. This setting is motivated by financial applications such as credit assessment, where the querying party must not reveal$x_{u}$to data-owning institutions, and each institution must protect its proprietary user list. To meet both the functionality and privacy requirements of the querying party and the servers, we present two protocols that represent a privacy-efficiency trade-off. DMS-P$^{2}$CQ$_{1}$is a lightweight protocol inspired by OPRF-based PSI. It achieves identifier privacy and hides the identifier-to-server membership relation from the querying party via a two-stage OPRF with an aggregation/re-randomization server. However, it reveals the aggregate count to a randomly selected leader server and relies on a non-collusion assumption between two special servers. DMS-P$^{2}$CQ$_{2}$strengthens privacy by secret-sharing the count so that no single party learns the true aggregate count and removes the need for a trusted re-randomization server. We prove the security of two protocols under the semi-honest model. Experimental results on our local testbed show that with 20 servers and a dataset size of$2^{20}$, the runtimes for DMS-P$^{2}$CQ$_{1}$and DMS-P$^{2}$CQ$_{2}$are approximately 8.034s and 16.697s, respectively.