So even with his hope renewed, Wichs assumed that any version of these programs that was secure was still a long way off. Instead, he and his co-authors — Wei-Kai Lin, now at the University of Virginia, and Ethan Mook, also at Northeastern — worked on problems they thought would be easier, which involved cases where multiple servers host the database.
In the methods they studied, the information in the database can be transformed into a mathematical expression, which the servers can evaluate to extract the information. The authors figured it might be possible to make that evaluation process more efficient. They toyed with an idea from 2011, when other researchers had found a way to quickly evaluate such an expression by preprocessing it, creating special, compact tables of values that allow you to skip the normal evaluation steps.
That method didn’t produce any improvements, and the group came close to giving up — until they wondered whether this tool might actually work in the coveted single-server case. Choose a polynomial carefully enough, they saw, and a single server could preprocess it based on the 2011 result — yielding the secure, efficient lookup scheme Wichs had pondered for years. Suddenly, they’d solved the harder problem after all.
At first, the authors didn’t believe it. “Let’s figure out what’s wrong with this,” Wichs remembered thinking. “We kept trying to figure out where it breaks down.”
But the solution held: They had really discovered a secure way to preprocess a single-server database so anyone could pull information in secret. “It’s really beyond everything we had hoped for,” said Yuval Ishai, a cryptographer at the Technion in Israel who was not involved in this work. It’s a result “we were not even brave enough to ask for,” he said.
After building their secret lookup scheme, the authors turned to the real-world goal of a private internet search, which is more complicated than pulling bits of information from a database, Wichs said. The private lookup scheme on its own does allow for a version of private Google-like searching, but it’s extremely labor-intensive: You run Google’s algorithm yourself and secretly pull data from the internet when necessary. Wichs said a true search, where you send a request and sit back while the server collects the results, is really a target for a broader approach known as homomorphic encryption, which disguises data so that someone else can manipulate it without ever knowing anything about it.
Typical homomorphic encryption strategies would hit the same snag as private information retrieval, plodding through all the internet’s contents for every search. But using their private lookup method as scaffolding, the authors constructed a new scheme which runs computations that are more like the programs we use every day, pulling information covertly without sweeping the whole internet. That would provide an efficiency boost for internet searches and any programs that need quick access to data.
While homomorphic encryption is a useful extension of the private lookup scheme, Ishai said, he sees private information retrieval as the more fundamental problem. The authors’ solution is the “magical building block,” and their homomorphic encryption strategy is a natural follow-up.
For now, neither scheme is practically useful: Preprocessing currently helps at the extremes, when the database size balloons toward infinity. But actually deploying it means those savings can’t materialize, and the process would eat up too much time and storage space.
Luckily, Vaikuntanathan said, cryptographers have a long history of optimizing results that were initially impractical. If future work can streamline the approach, he believes private lookups from giant databases may be within reach. “We all thought we were kind of stuck there,” he said. “What Daniel’s result gives is hope.”
Quanta is conducting a series of surveys to better serve our audience. Take our computer science reader survey and you will be entered to win free Quanta merchandise.
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/cryptographers-devise-an-approach-for-total-search-privacy-20231106/
