Over the years, researchers have been developing methods to allow users to search and retrieve information from databases anonymously, but these processes are still too sluggish to be useful in real-world applications.
However, researchers at the Massachusetts Institute of Technology (MIT) have now created a method that is around 30 times quicker than previous approaches and allows users to discreetly search for information in a distant database without disclosing their search to the server and preserving privacy online.
Matthew Hong is a graduate student in computer science at MIT. Henry Corrigan-Gibbs, the Douglas Ross Career Development Professor of Software Technology in the MIT Department of Electrical Engineering and Computer Science (EECS), and Sarah Meiklejohn, a professor of cryptography and security at the University College London and a staff research scientist at Google, are the author behind the development.
A Faster Way to Preserve Privacy Online
By using this method, a user can search a database online without disclosing their search to the server. Furthermore, it is powered by a straightforward algorithm that would be simpler to implement than the more intricate methods from earlier studies.
Furthermore, by prohibiting a messaging app from seeing what users are saying or who they are talking to, their method might enable private conversation. Additionally, it might be used to retrieve pertinent internet ads without requiring advertising servers to discover a user’s preferences.
“This work is really about giving users back some control over their data. In the long run, we’d like browsing the web to be as private as browsing a library. This work doesn’t achieve that yet, but it starts building the tools to let us do this sort of thing quickly and efficiently in practice,” says Alexandra Henzinger, a computer science graduate student and lead author of a paper introducing the technique.
These methods make the server touch every single database item to protect privacy, making it impossible for the server to determine which record a user is looking for. The server would discover that the client is not interested in that item if one area was left unattended. The query procedure is slowed considerably by contacting every item, even if there may be millions of database items.
Accordingly, the MIT researchers created a protocol called Simple PIR to speed things up in which the server completes a large portion of the underlying cryptographic work in advance before a client even sends a query. Before sending a query, the client downloads a data structure that contains compressed information about the contents of the database as a result of this preprocessing step.
“Once the client has this hint, it can make an unbounded number of queries, and these queries are going to be much smaller in both the size of the messages you are sending and the work that you need the server to do. This is what makes Simple PIR so much faster,” Henzinger explains.
Additionally, their approach is much easier than many top-performing methods that need two distinct servers with identical databases because it only needs one server. Their approach performed better than these more intricate methods.
“I’ve been thinking about these schemes for some time, and I never thought this could be possible at this speed. The folklore was that any single-server scheme is going to be slow. This work turns that whole notion on its head,” Corrigan-Gibbs says.
Improving Practical Cost for Private Information Retrieval
Speaking on the new research, Yuval Ishai, a professor of computer science at Technion, the Israel Institute of Technology, who is part of the research work, said the work has significantly lowered the actual cost of retrieving private information. In his words:
“This work makes a major improvement to the practical cost of private information retrieval. While it was known that low-bandwidth PIR schemes imply public-key cryptography, which is typically orders of magnitude slower than private-key cryptography, this work develops an ingenious method to bridge the gap. This is done by making clever use of special properties of a public-key encryption scheme due to Regev pushing the vast majority of the computational work to a pre-computation step, in which the server computes a short ‘hint’ about the database.”
