FrodoPIR

This morning I'm currently staring down a stack of research papers on my desk. But I just saw a headline from Hacker News that Brave, a privacy-preserving browser I'm a fan of, published a paper and code for an improved private information retrieval system.

It requires a relatively simple offline setup ritual and allegedly the FrodoPIR scheme outperforms other private information retrieval schemes by an order of magnitude! The paper is on IACR. And an implementation (written in Rust!) is on their Github at Brave Experiments.

While I won't post any of the mathematical abstractions here because I don't have time to write the LaTeX, the high level overview from their paper appears straightforward enough. Very nice.

1. In the offline phase, the server interprets the database as a matrix, applies a compression function to said matrix and makes the results available as global public parameters. This compression function shrinks the size of the database by a factor of approximately m/λ, where λ is the security parameter and m is the number of database elements. Thus, the size of the parameters is no longer linear in the size of the database.
2. The client downloads the public parameters, and can compute c sets of preprocessed query parameters.
3. In the online phase, the client uses a single set of preprocessed query parameters to produce an “encrypted” query vector, which is sent to the server.
4. The server responds to the query by multiplying the vector with their database matrix.
5. The client returns the result by “decrypting” the response using their preprocessed query parameters.

The paper mentions that previous private information retrieval schemes suffer from computational costs (and thus financial costs) during the initial offline setup phase, with information scaling linearly with the number of clients that will be making requests. Instead, this research is based on learning with errors and provides a low-cost, single-server private information retrieval scheme that outperforms its predecessors.

The main benefit of FrodoPIR is that the offline phase of the protocol is performed by the server alone, completely independent of the number of clients or queries that will be made. This results in low amortized computation overheads, and an offline client download size that is a tiny fraction of the entire server database.