Paper 2021/823
GPU-accelerated PIR with Client-Independent Preprocessing for Large-Scale Applications
Daniel Günther and Maurice Heymann and Benny Pinkas and Thomas Schneider
Abstract
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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- Private Information RetrievalGPU Acceleration
- Contact author(s)
- guenther @ encrypto cs tu-darmstadt de,sapp @ hotmail de,benny @ pinkas net,schneider @ encrypto cs tu-darmstadt de
- History
- 2022-06-22: last of 3 revisions
- 2021-06-16: received
- See all versions
- Short URL
- https://ia.cr/2021/823
- License
-
CC BY