FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval
Authors: Alex Davidson (Brave Software), Gonçalo Pestana (Brave Software), Sofía Celi (Brave Software)
Volume: 2023
Issue: 1
Pages: 365–383
DOI: https://doi.org/10.56553/popets-2023-0022
Abstract: We design 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 1KB elements, FrodoPIR requires < 1 second for responding to a client query, has a server response size blow-up factor of < 3.6x, and financial costs are ~$1 for answering 100,000 client queries. Our experimental analysis is built upon a simple, non-optimized Rust implementation, illustrating that FrodoPIR is particularly suitable for deployments that involve large numbers of clients.
Keywords: private information retrieval, cryptography, lattices
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
