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


Daniel Günther and Maurice Heymann, Technical University of Darmstadt; Benny Pinkas, Bar-Ilan University; Thomas Schneider, Technical University of Darmstadt


Multi-Server Private Information Retrieval (PIR) is a cryptographic protocol that allows a client to securely query a database entry from n ≥ 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 GPUbased CIP-PIR achieves an improvement up to factor 2.1× 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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {281446,
author = {Daniel G{\"u}nther and Maurice Heymann and Benny Pinkas and Thomas Schneider},
title = {{GPU-accelerated} {PIR} with {Client-Independent} Preprocessing for {Large-Scale} Applications},
booktitle = {31st USENIX Security Symposium (USENIX Security 22)},
year = {2022},
isbn = {978-1-939133-31-1},
address = {Boston, MA},
pages = {1759--1776},
url = {},
publisher = {USENIX Association},
month = aug

Presentation Video