Cryptographers Make Progress in Enabling Fully Private Internet Searches
Researchers have found a way to access information from large databases privately, bringing us closer to fully private browsing.
The Challenge of Private Information Retrieval
Cryptography faces the question of how to access information from a public database without revealing what has been accessed. This problem, known as private information retrieval, is crucial for privacy-preserving applications. Researchers have been working on solutions since the 1990s, but accessing large databases privately, like a private Google search, has remained a challenge.
Now, three researchers have made a breakthrough in private information retrieval by developing a more general privacy strategy. This work has overcome a major theoretical barrier and brings us one step closer to achieving fully private internet searches. The research received a Best Paper Award at the 2023 annual Symposium on Theory of Computing.
Overcoming the Full-Scan Barrier
Initially, researchers believed that the only way to access a database securely was to scan the entire database during each search. However, as databases grow larger, this method becomes inefficient. In the early 2000s, researchers began exploring the idea of preprocessing the database, transforming it into a special structure that allows the server to answer queries by reading only a small portion of that structure. It was thought that this preprocessing could enable a single server to handle all future search queries.
The authors of the new study took this idea further and found a way to efficiently preprocess a single-server database. This breakthrough allows anyone to retrieve information from the database privately, without the need for heavy computational lifting.
Moving Towards Private Internet Searches
With their secure lookup scheme in place, the researchers turned their attention to the goal of private internet searches. While the private lookup scheme can enable a version of private searching, it is currently labor-intensive. Users have to run Google's algorithm themselves and secretly pull data from the internet when needed. To achieve a true search experience, a broader approach known as homomorphic encryption is needed.
The authors used their private lookup method as a foundation and developed a new scheme that runs computations similar to everyday programs. This approach allows for covert information retrieval without scanning the entire internet, providing a more efficient solution for internet searches and other applications requiring quick data access.
