Paper 2021/823 Original: eprint.iacr.org/2021/823 ↗

GPU-accelerated PIR with Client-Independent Preprocessing for Large-Scale Applications

Abstract

Multi-Server Private Information Retrieval (PIR) is a cryptographic protocol that allows a client to securely query a database entry from $n \geq 2$ servers of which less than $t$ can collude, s.t. the servers 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 $(t-1)/n$ of the online computation to a local, client independent, preprocessing phase suitable for efficient batch precomputations. The online performance of CIP-PIR improves 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. 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 online performance simultaneously improves with the number of servers $n$. In addition, we accelerate for the first time the huge amount of XOR operations in multi-server PIR with GPUs. Our GPU-based CIP-PIR achieves an improvement up to factor $2.1\times$ over our CPU-based implementation for $n=2$ servers, and enables a client to query an entry in a 25 GB database within less than 1 second.