We all know to be careful about the details we share online, but the information we seek can also be revealing. Search for driving directions, and our location becomes far easier to guess. Check for a password in a trove of compromised data, and we risk leaking it ourselves.
These situations fuel a key question in cryptography: How can you pull information from a public database without revealing anything about what you’ve accessed? It’s the equivalent of checking out a book from the library without the librarian knowing which one.
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. Since the 1990s, researchers have chipped away at the question, improving strategies for privately accessing databases. 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.
Now, three researchers have crafted a long-sought version of private information retrieval and extended it to build a more general privacy strategy. The work, which received a Best Paper Award in June at the annual Symposium on Theory of Computing, topples a major theoretical barrier on the way to a truly private search.
To read more, click here.