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

Alex Davidson (Brave Software), Gonçalo Pestana (Brave Software), Sofía Celi (Brave Software) | Cryptography , Privacy

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.6×, 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 eminently suitable for large practical deployments.

View paper


Ready for a better Internet?

Brave’s easy-to-use browser blocks ads by default, making the Web cleaner, faster, and safer for people all over the world.


Get ready to Brave the Internet…

You’re just 60 seconds away from a browser that works for you.

If your download didn’t start, .

  1. Wait for the download to complete

  2. Run the installer

  3. Import settings from your old browser

Need help?

Get a better Internet. Everywhere.

Download Brave on your mobile devices.

Download QR code