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, singleserver 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

Links

Ready to Brave the new internet?

Brave is built by a team of privacy focused, performance oriented pioneers of the web. Help us fix browsing together.

close
close

Almost there…

You’re just 60 seconds away from the best privacy online

If your download didn’t start automatically, .

  1. Download Brave

    Click “Save” in the window that pops up, and wait for the download to complete.

    Wait for the download to complete (you may need to click “Save” in a window that pops up).

  2. Run the installer

    Click the downloaded file at the bottom left of your screen, and follow the instructions to install Brave.

    Click the downloaded file at the top right of your screen, and follow the instructions to install Brave.

    Click the downloaded file, and follow the instructions to install Brave.

  3. Import settings

    During setup, import bookmarks, extensions, & passwords from your old browser.

Need help?

Get better privacy. Everywhere!

Download Brave mobile for privacy on the go.

Download QR code
Brave logo Click this file to install Brave
Click this file to install Brave Brave logo