Paper 2022/981
FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. PoPETS 2023 (Issue 1)
- Keywords
- Private Information Retrieval
- Contact author(s)
-
alxdavids @ brave com
gpestana @ brave com
sceli @ brave com - History
- 2022-10-04: revised
- 2022-07-31: received
- See all versions
- Short URL
- https://ia.cr/2022/981
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/981,
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},
url = {https://eprint.iacr.org/2022/981}
}
