undefined | Better HN

0 pointsperlgeek9mo ago0 comments

> Private lookups of a plaintext database are possible and have been for a while now (5+ years?). The problem is it often requires some nontrivial preprocessing of the plaintext database, or in the worst case a linear scan of the entire database.

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.

0 comments

dcow9mo ago

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.

j2kun9mo ago

> 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.

j / k navigate · click thread line to collapse