Paper 2021/823

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

Daniel Günther, TU Darmstadt
Maurice Heymann, TU Darmstadt
Benny Pinkas, Bar-Ilan University
Thomas Schneider, TU Darmstadt

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2022
Private Information Retrieval GPU Acceleration
Contact author(s)
guenther @ encrypto cs tu-darmstadt de
sapp @ hotmail de
benny @ pinkas net
schneider @ encrypto cs tu-darmstadt de
2022-06-22: last of 3 revisions
2021-06-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Günther and Maurice Heymann and Benny Pinkas and Thomas Schneider},
      title = {{GPU}-accelerated {PIR} with Client-Independent Preprocessing for Large-Scale Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/823},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.