FrodoPIR: New Privacy-Focused Database Querying System

Dec 23, 2022Ravie LakshmananEncryption / Privacy / Browser

The developers behind the Brave open-source web browser have
revealed a new privacy-preserving data querying and retrieval
system called FrodoPIR.

The idea, the company said^[1], is to use the
technology to build out a wide range of use cases such as safe
browsing, checking passwords against breached databases,
certificate revocation checks, and streaming, among others.

The scheme is called FrodoPIR^[2]
because “the client can perform hidden queries to the server, just
as Frodo remained hidden from Sauron,” a reference to the
characters from oJ. R. R. Tolkien’s The Lord of the Rings^[3].

PIR, short for private information retrieval^[4], is a cryptographic
protocol that enables users (aka clients) to retrieve a piece of
information from a database server without revealing to its owner
which element was selected.

In other words, the goal is to be able to query a platform for
information (say, cooking videos) without letting the service
provider infer from a user’s search history to offer personalized
recommendations or targeted ads based on the search criteria.

One way this is achieved is by using an approach called homomorphic encryption^[5], which allows
computation to be performed directly on enciphered data without
requiring access to a private key.

But a common problem afflicting such methods is that they are
“expensive in terms of either bandwidth, or in the amount of time
taken to process each client query,” making them prohibitive for
real-world deployments.

That’s where FrodoPIR steps in. It involves two phases, an
offline preparatory step and an online step wherein the client
transmits encrypted queries to the server.

The server subsequently opts to return a positive or negative
value depending on whether or not the query is found in the
database without learning what the user is actually querying
for.

“In terms of performance for a database of 1 million KB
elements, FrodoPIR requires <1 second for responding to a client
query, has a server response size blow-up factor of > 3.6x, and
financial costs are ~$1 for answering client queries,” Brave
said^[6]
in a GitHub description of the project.

Google Open Sources Two Privacy-Enhancing Technologies
(PETs)

The development comes as Google said^[7]
it’s open-sourcing two privacy-enhancing technologies (PETs) as
part of its ongoing efforts to democratize access to techniques
beyond Federated Learning^[8]
and Differential Privacy^[9].

This consists of a new machine learning tool called Magritte^[10] that’s designed to blur
objects like license plates present in videos, as well as
efficiency improvements to its Fully Homomorphic Encryption
(FHE^[11]) Transpiler.

The transpiler^[12], aka source-to-source
compiler or translator, is designed to run computation-based
queries on encrypted information sans any access to personally
identifiable data.

The PETs “will provide the broader developer community
(researchers, governments, nonprofits, businesses and more) new
ways to deploy and enhance privacy features in their own work,”
Google noted.