Brave Software developers have created a new privacy-centric database query system called FrodoPIR that retrieves data from servers without disclosing the content of user queries.
Brave plans to use FrodoPIR in an upcoming leaked credentials checker built into the Brave browser to check usernames and passwords against known data dumps without disclosing the checked pairs to the server.
The developers note that FrodoPIR was designed to be cost-effective and versatile in any use-case scenario, making it ideal for use in a broad range of data retrieval cases besides just checking credentials.
Also, compared to existing solutions, Brave’s private database access proposal is more cost-effective, less complicated to implement, and easier to scale.
As an example of its speed, for a database of 1 million 1KB elements, FrodoPIR requires less than a second to respond to client queries, has a server response size blow-up factor under 3.6x, and it costs just $1 to answer 100,000 client queries.
How FrodoPIR works
FrodoPIR’s functionality is broken down into two phases, an offline phase where preparatory work takes place and an online phase where the “hidden” query 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, and then applies compression and makes the results available as public parameters.
The client downloads those parameters and computes sets of pre-processed queries.
The client picks the proper 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 an answer that determines whether the query has a match in the database.
Finally, the client receives the response and decrypts it using the same pre-processed query parameters for generating the private query.
“Each client query is a noisy vector that appears uniformly random to the server,” explains Brave.
“The server never learns which value you are querying for, and yet it returns the correct answer (if it was included in the database or not).”
Apart from the password checker, which is in the plans 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 about how FrodoPIR works, you can also check this paper published by the Brave Software team.
