Re:Fully Homomorphic Encryption and the Dawn of a Truly Priv...
by dcow on Friday July 18, 2025 @02:27PM
(#44608181)
You can process the data such that only a structured lookup table is shared with the client. That data structure is massive.
The use case isn't really “search Google without them knowing my query”, it’s search my own data without them knowing my data”. Which limits the practically applicable scope considerably.
Re:Fully Homomorphic Encryption and the Dawn of a Truly Priv...
by j2kun on Friday July 18, 2025 @03:16PM
(#44608697)
> the entirety of that data needs to be loaded into my program
What? No. I'm not saying the entire Google search index is feasible, but you can do a lot. Here are some concrete numbers from what is now considered an "old" paper (2022; it has been improved since then)
https://eprint.iacr.org/2022/949
To make queries to a 1 GB database [in a scheme called DoublePIR] the client must download a 16 MB "hint" about the database contents; thereafter, the client may make an unbounded number of queries, each requiring 345 KB of communication, and a throughput of 7.4 GB/s/core.
So that basically means that if a company has data that my program might want to use, the entirety of that data needs to be loaded into my program. Not quite feasible for something like the Google search index, which (afaik) doesn't even fit onto a single machine.
Also, while Google is fine with us doing searches, making the whole search index available to a homomorphic encrypted program is probably a quite different beast.