Cryptographers Are Getting Closer to Enabling Fully Private Internet Searches

The original version of this story appeared in Quanta Magazine. Concocting a strategy that solves this problem—known as private information retrieval—is “a very useful building block in a number of privacy-preserving applications,” said David Wu, a cryptographer at the University of Texas, Austin. One major goal, still impossible with large databases, is the equivalent of a private Google search, where you can sift through a heap of data anonymously without doing any heavy computational lifting. The work, which received a Best Paper Award in June 2023 at the annual Symposium on Theory of Computing, topples a major theoretical barrier on the way to a truly private search. At first, researchers assumed that the only solution was to scan the entire database during every search, which would be like having a librarian scour every shelf before returning with your book.