Paper 2022/981

FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval

Alex Davidson, Brave Software
Gonçalo Pestana, Brave Software
Sofía Celi, Brave Software

We design $\mathsf{FrodoPIR}$ — a highly configurable, stateful, single-server Private Information Retrieval (PIR) scheme that involves an offline phase that is completely client-independent. Coupled with small online overheads, it leads to much smaller amortized financial costs on the server-side than previous approaches. In terms of performance for a database of $1$ million $1$KB elements, $\mathsf{FrodoPIR}$ requires $< 1$ second for responding to a client query, has a server response size blow-up factor of $< 3.6\times$, and financial costs are $\sim \$1$ for answering $100,000$ client queries. Our experimental analysis is built upon a simple, non-optimized Rust implementation, illustrating that $\mathsf{FrodoPIR}$ is particularly suitable for deployments that involve large numbers of clients.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. PoPETS 2023 (Issue 1)
Private Information Retrieval
Contact author(s)
alxdavids @ brave com
gpestana @ brave com
sceli @ brave com
2022-10-04: revised
2022-07-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Davidson and Gonçalo Pestana and Sofía Celi},
      title = {FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval},
      howpublished = {Cryptology ePrint Archive, Paper 2022/981},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.