Paper 2024/482

$\textsf{ThorPIR}$: Single Server PIR via Homomorphic Thorp Shuffles

Abstract

Private Information Retrieval (PIR) is a two player protocol where the client, given some query $x \in [N]$, interacts with the server, which holds a $N$-bit string $\textsf{DB}$, in order to privately retrieve $\textsf{DB}[x]$. In this work, we focus on the single-server client-preprocessing model, initially proposed by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run a joint preprocessing algorithm, after which the client can retrieve elements from $\textsf{DB}$ privately in time sublinear in $N$. Most known constructions of single-server client-preprocessing PIR follow one of two paradigms: They feature either (1) a linear-bandwidth offline phase where the client downloads the whole database from the server, or (2) a sublinear-bandwidth offline phase where however the server has to compute a large-depth ($\Omega_\lambda (N)$) circuit under fully-homomorphic encryption (FHE) in order to execute the preprocessing phase. In this paper, we propose $\textsf{ThorPIR}$, a single-server client preprocessing PIR scheme which achieves both sublinear offline bandwidth (asymptotically and concretely) and a low-depth, highly parallelizable preprocessing circuit. Our main insight is to use and significantly optimize the concrete circuit-depth of a much more efficient shuffling technique needed during preprocessing, called Thorp shuffle. A Thorp shuffle satisfies a weaker security property (e.g., compared to an AES permutation) which is ``just enough'' for our construction. We estimate that with a powerful server (e.g., hundreds of thousands of GPUs), $\textsf{ThorPIR}$'s end-to-end preprocessing time is faster than any prior work. Additionally, compared to prior FHE-based works with sublinear bandwidth, our construction is at least around $10,000$ times faster.

Note: 12/09/24: Editorial changes. Include a discussion on FHE-friendly block-ciphers and other minor editorial changes. 06/04/24: Editorial changes. Include new benchmarks, detailed estimation, and conjectured security.