Brother
Professional
- Messages
- 2,590
- Reaction score
- 539
- Points
- 113
A discovery that promises a new era of privacy in the use of search engines.
The attention to detail we share online is always relevant. But the information we're looking for can also tell you a lot about us. For example, searching for routes leads to guessing our location, and checking the password for data leaks can lead to its self-disclosure.
These situations raise an important question in the field of cryptography: how can I extract information from public databases without revealing what exactly you were looking for? It's like taking a book from a library without the librarian's knowledge.
David Wu, a cryptographer at the University of Texas at Austin, notes that solving this problem (known as "finding private information") is key for many data privacy applications. Since the 1990s, researchers have been working to improve strategies for confidential database access. One of the main goals is to create something like a private Google search, which allows you to browse huge amounts of data anonymously without significant computational effort.
Recently, three researchers proposed a long-awaited version of private information retrieval and expanded it to a more general privacy strategy. Their work, which won the Best Paper award in June 2023 at the annual Symposium on Computational Theory , overcame an important theoretical barrier to creating a truly confidential search experience.
"It's something that everyone in cryptography dreamed of, but didn't believe it existed," says Vinod Vaikuntanathan, a cryptographer at the Massachusetts Institute of Technology who wasn't involved in the study. "This is a breakthrough result."
The problem of confidential access to databases began to form in the 1990s. At first, it was thought that the only solution was to scan the entire database with each search. It's like a librarian checking each shelf before bringing in your book. After all, if the search skips any section, the librarian will understand that the book you are looking for is not in this part of the library.
This approach is acceptable on a small scale, but as the database grows, the time required to scan it increases proportionally. When working with large amounts of data, the process becomes inefficient.
In the early 2000s, researchers began to suspect that they could avoid a full scan by pre-processing the database. Roughly, this would mean encoding the entire database as a special structure, so that the server could respond to the request by reading only a small part of it. Sufficiently thorough preprocessing could theoretically mean that a single server storing information goes through this process once, allowing all subsequent users to retrieve data confidentially without additional effort.
Daniel Wiechs, a cryptographer at Northeastern University and one of the authors of the groundbreaking publication, was initially skeptical of the idea, considering it too utopian to be a reality. In 2011, he made attempts to prove its impossibility, confident in its unrealizability.
However, in 2017, two groups of researchers published results that made Wichs change his mind. They created the first programs capable of performing such a private search for information, but could not prove their security.
In the methods they learn, the information in the database can be converted into a mathematical expression that servers can evaluate to extract the data. The authors suggested that the evaluation process could be made more efficient. They experimented with the idea from 2011, when other researchers found a way to quickly evaluate such an expression by preprocessing it and creating compact tables of values. This allowed you to skip the usual evaluation steps.
This method did not bring any improvements, and the group was close to abandoning the idea. But they wondered: what if this tool can still work in the case of a single server? By selecting a suitable polynomial, they saw that a single server could pre-process it based on the 2011 result — creating a secure and efficient search scheme that Wichs had been thinking about for years. Suddenly, they solved a more complex problem.
At first, the authors didn't believe it. "Let's find out what the catch is," Wiechs recalls."We kept trying to figure out where it breaks down."
But the solution turned out to be correct: they actually found a safe way to pre-process a single-server database, so that anyone could secretly extract information.
"This really exceeds all our expectations," said Yuval Yishai, a cryptographer at the Technion in Israel who was not involved in the work. This is a result "that we did not even dare to hope for," he said.
After creating their secret search scheme, the authors turned to the real purpose of private internet search, which is more complex than extracting bits of information from a database, Wichs said.
The private search scheme itself does allow for a Google-like search, but it's extremely time-consuming: you run Google's algorithm yourself and secretly pull data from the web as needed.
Wichs said that true search, where you send a request and wait for the server to collect the results, is really the goal for a broader approach known as homomorphic encryption. It masks the data so that someone else can manipulate it without ever knowing about it.
Typical homomorphic encryption strategies would face the same problem as searching for private information by scanning the entire internet for each request. But using their private search scheme as a basis, the authors developed a new homomorphic encryption scheme. It performs calculations more similar to everyday programs, secretly extracting data without browsing the entire Internet. This would provide increased efficiency for internet search and any applications that need fast access to information.
Although homomorphic encryption is a useful extension of the private search scheme, Yishai believes that finding private information is a more fundamental problem. The authors 'solution is a " magic building block", and their homomorphic encryption strategy is a natural extension.
At the moment, none of the schemas are practically useful: preprocessing currently helps at extreme limits, when the database size tends to infinity. But the actual implementation means that these savings cannot be realized, and the process will require too much time and storage space.
Fortunately, Vaikuntanathan said, cryptographers have a long history of optimizing results that were initially impractical. If future work makes this approach easier, he believes that private search in giant databases can become achievable. "We all thought we were stuck there, "he said." Daniel's result gives us hope."
The attention to detail we share online is always relevant. But the information we're looking for can also tell you a lot about us. For example, searching for routes leads to guessing our location, and checking the password for data leaks can lead to its self-disclosure.
These situations raise an important question in the field of cryptography: how can I extract information from public databases without revealing what exactly you were looking for? It's like taking a book from a library without the librarian's knowledge.
David Wu, a cryptographer at the University of Texas at Austin, notes that solving this problem (known as "finding private information") is key for many data privacy applications. Since the 1990s, researchers have been working to improve strategies for confidential database access. One of the main goals is to create something like a private Google search, which allows you to browse huge amounts of data anonymously without significant computational effort.
Recently, three researchers proposed a long-awaited version of private information retrieval and expanded it to a more general privacy strategy. Their work, which won the Best Paper award in June 2023 at the annual Symposium on Computational Theory , overcame an important theoretical barrier to creating a truly confidential search experience.
"It's something that everyone in cryptography dreamed of, but didn't believe it existed," says Vinod Vaikuntanathan, a cryptographer at the Massachusetts Institute of Technology who wasn't involved in the study. "This is a breakthrough result."
The problem of confidential access to databases began to form in the 1990s. At first, it was thought that the only solution was to scan the entire database with each search. It's like a librarian checking each shelf before bringing in your book. After all, if the search skips any section, the librarian will understand that the book you are looking for is not in this part of the library.
This approach is acceptable on a small scale, but as the database grows, the time required to scan it increases proportionally. When working with large amounts of data, the process becomes inefficient.
In the early 2000s, researchers began to suspect that they could avoid a full scan by pre-processing the database. Roughly, this would mean encoding the entire database as a special structure, so that the server could respond to the request by reading only a small part of it. Sufficiently thorough preprocessing could theoretically mean that a single server storing information goes through this process once, allowing all subsequent users to retrieve data confidentially without additional effort.
Daniel Wiechs, a cryptographer at Northeastern University and one of the authors of the groundbreaking publication, was initially skeptical of the idea, considering it too utopian to be a reality. In 2011, he made attempts to prove its impossibility, confident in its unrealizability.
However, in 2017, two groups of researchers published results that made Wichs change his mind. They created the first programs capable of performing such a private search for information, but could not prove their security.
In the methods they learn, the information in the database can be converted into a mathematical expression that servers can evaluate to extract the data. The authors suggested that the evaluation process could be made more efficient. They experimented with the idea from 2011, when other researchers found a way to quickly evaluate such an expression by preprocessing it and creating compact tables of values. This allowed you to skip the usual evaluation steps.
This method did not bring any improvements, and the group was close to abandoning the idea. But they wondered: what if this tool can still work in the case of a single server? By selecting a suitable polynomial, they saw that a single server could pre-process it based on the 2011 result — creating a secure and efficient search scheme that Wichs had been thinking about for years. Suddenly, they solved a more complex problem.
At first, the authors didn't believe it. "Let's find out what the catch is," Wiechs recalls."We kept trying to figure out where it breaks down."
But the solution turned out to be correct: they actually found a safe way to pre-process a single-server database, so that anyone could secretly extract information.
"This really exceeds all our expectations," said Yuval Yishai, a cryptographer at the Technion in Israel who was not involved in the work. This is a result "that we did not even dare to hope for," he said.
After creating their secret search scheme, the authors turned to the real purpose of private internet search, which is more complex than extracting bits of information from a database, Wichs said.
The private search scheme itself does allow for a Google-like search, but it's extremely time-consuming: you run Google's algorithm yourself and secretly pull data from the web as needed.
Wichs said that true search, where you send a request and wait for the server to collect the results, is really the goal for a broader approach known as homomorphic encryption. It masks the data so that someone else can manipulate it without ever knowing about it.
Typical homomorphic encryption strategies would face the same problem as searching for private information by scanning the entire internet for each request. But using their private search scheme as a basis, the authors developed a new homomorphic encryption scheme. It performs calculations more similar to everyday programs, secretly extracting data without browsing the entire Internet. This would provide increased efficiency for internet search and any applications that need fast access to information.
Although homomorphic encryption is a useful extension of the private search scheme, Yishai believes that finding private information is a more fundamental problem. The authors 'solution is a " magic building block", and their homomorphic encryption strategy is a natural extension.
At the moment, none of the schemas are practically useful: preprocessing currently helps at extreme limits, when the database size tends to infinity. But the actual implementation means that these savings cannot be realized, and the process will require too much time and storage space.
Fortunately, Vaikuntanathan said, cryptographers have a long history of optimizing results that were initially impractical. If future work makes this approach easier, he believes that private search in giant databases can become achievable. "We all thought we were stuck there, "he said." Daniel's result gives us hope."
