International Association
for Cryptologic Research

Multi-Server Private Information Retrieval (PIR) is a cryptographic primitive that allows a client to securely query a database entry from $n \geq 2$ non-colluding servers, which learn no information about the query. Highly efficient PIR could be used for large-scale applications like Compromised Credential Checking (C3) (USENIX Security'19), which allows users to check whether their credentials have been leaked in a data breach. However, state-of-the art PIR schemes are not efficient enough for fast online responses at this scale.

In this work, we introduce Client-Independent Preprocessing (CIP) PIR that moves $\frac{n-1}{n}$ of the online computation to a local preprocessing phase suitable for efficient batch precomputations. The security and online performance of CIP-PIR improve linearly with the number of servers $n$. We show that large-scale applications like C3 with PIR are practical by implementing our CIP-PIR scheme using a parallelized CPU implementation and further accelerating the huge amount of XOR operations with GPUs. To the best of our knowledge, this is the first multi-server PIR scheme whose preprocessing phase is completely independent of the client, and where security and online performance simultaneously increase with the number of servers $n$. In addition, CIP-PIR is the first multi-server PIR scheme that is accelerated by GPUs. It achieves an improvement up to factor $2.1\times$ over our CPU-based implementation. Moreover, a client can access a database entry of a 25 GByte database within less than 1 second.