The unique model of this story appeared in Quanta Magazine.

We all know to watch out in regards to the particulars we share on-line, however the info we search will also be revealing. Search for driving instructions, and our location turns into far simpler to guess. Check for a password in a trove of compromised information, and we threat leaking it ourselves.

These conditions gas a key query in cryptography: How are you able to pull info from a public database with out revealing something about what you’ve accessed? It’s the equal of testing a e-book from the library with out the librarian figuring out which one.

Concocting a technique that solves this downside—generally known as personal info retrieval—is “a very useful building block in a number of privacy-preserving applications,” mentioned David Wu, a cryptographer on the University of Texas, Austin. Since the Nineteen Nineties, researchers have chipped away on the query, enhancing methods for privately accessing databases. One main purpose, nonetheless unattainable with giant databases, is the equal of a non-public Google search, the place you possibly can sift by a heap of knowledge anonymously with out doing any heavy computational lifting.

Now, three researchers have crafted a long-sought model of personal info retrieval and prolonged it to construct a extra basic privateness technique. The work, which acquired a Best Paper Award in June 2023 on the annual Symposium on Theory of Computing, topples a serious theoretical barrier on the best way to a very personal search.

“[This is] something in cryptography that I guess we all wanted but didn’t quite believe that it exists,” mentioned Vinod Vaikuntanathan, a cryptographer on the Massachusetts Institute of Technology who was not concerned within the paper. “It is a landmark result.”

The downside of personal database entry took form within the Nineteen Nineties. At first, researchers assumed that the one resolution was to scan your complete database throughout each search, which might be like having a librarian scour each shelf earlier than returning along with your e-book. After all, if the search skipped any part, the librarian would know that your e-book shouldn’t be in that a part of the library.

That strategy works properly sufficient at smaller scales, however because the database grows, the time required to scan it grows at the least proportionally. As you learn from larger databases—and the web is a fairly large one—the method turns into prohibitively inefficient.

In the early 2000s, researchers began to suspect they may dodge the full-scan barrier by “preprocessing” the database. Roughly, this may imply encoding the entire database as a particular construction, so the server may reply a question by studying only a small portion of that construction. Careful sufficient preprocessing may, in principle, imply {that a} single server internet hosting info solely goes by the method as soon as, by itself, permitting all future customers to seize info privately with none extra effort.

For Daniel Wichs, a cryptographer at Northeastern University and a coauthor of the brand new paper, that appeared too good to be true. Around 2011, he began attempting to show that this type of scheme was unattainable. “I was convinced that there’s no way that this could be done,” he mentioned.