Brave Software developers have created a new privacy-centric database query system called FrodoPIR that fetches data from servers without disclosing the contents of user queries.

Brave plans to use FrodoPIR in an upcoming in-browser Brave leaked credential checker to check usernames and passwords against known data dumps without leaking the checked pairs to the server.

The developers note that FrodoPIR was designed to be cost-effective and versatile in any usage scenario, making it ideal for use in a wide range of data recovery cases in addition to just verifying user information. ‘identification.

Additionally, compared to existing solutions, Brave’s private database access proposition is more cost-effective, less complicated to implement, and easier to scale.

As an example of its speed, for a database of 1 million 1 KB items, FrodoPIR takes less than a second to respond to client queries, has a response size blowout factor server performance less than 3.6x and it only costs $1 to cater to 100,000 customers. requests.

How FrodoPIR works

The functionality of FrodoPIR is divided into two phases, an offline phase where the preparatory work takes place and an online phase where the “hidden” request is made to the server.

In the offline phase, the server interprets the database as a linear matrix, which reduces its size by about 170 times, then applies compression and makes the results available as public parameters.

The client downloads these parameters and computes sets of preprocessed queries.

The client selects the appropriate query parameters in the online phase to produce an encrypted query vector.

Upon receiving the query, the server multiplies it with its database matrix and responds with a response that determines if the query has a match in the database.

Finally, the client receives the response and decrypts it using the same preprocessed query parameters to generate the private query.

“Each client request is a noisy vector that appears uniformly random to the server”, explains Brave.

“The server never learns what value you are querying, yet it returns the correct answer (whether it was included in the database or not).”

Besides the password verifier, which is planned for Brave Browser, the post mentions that the FrodoPIR scheme could also be used for certificate transparency and revocation checks, streaming, and safe browsing.

For more technical details on how FrodoPIR works, you can also look at this paper released by Brave Software team.