3 ms·

Pretty efficient! E.g. a recent paper describes a system to do fully private search over the common crawl (360 million web pages) with an end to end latency of

Pretty efficient! E.g. a recent paper describes a system to do fully private search over the common crawl (360 million web pages) with an end to end latency of 2.7 seconds: https://dl.acm.org/doi/10.1145/3600006.3613134 https://dl.acm.org/doi/10.1145/3600006.3613134

vlovich123 3y ago
Yeah, but that’s 1 request using 100% capacity of a 45 machine cluster. Relatively efficient but cost prohibitive.
- avmich 3y ago
  How does it compare to the search done without any encryption?
  - seeknotfind 3y ago
    Many many orders of magnitude. It really depends on the search algorithm. If you're looking up a single term, there are many standard ways to index this, but for instance using a trie or hash table, the lookup cost would be a number of operations proportional to the search term length (e.g. for "foo", it's a of length 3, times some small number of operations for each letter). Plus then if you want to combine the results and sort by frequency, to estimate the cost of this, add up the number of pages from each term, p_1 + p_2 + ... = P. Then the number of operations might be P*log(P). This dominates the cost. So if your search terms appear in 1,000,000 of these pages, you're talking about on the order of ~6,000,000 small operations. An implementation would be able to execute this many operations on a single CPU in 10s or 100s of milliseconds maybe, for an elementary unoptimized algorithm.
- deadfece 3y ago
  It used 145 core-seconds of compute, according to the paper. That's not 100% unless they were mostly 1 core servers. However, the search used almost 50MiB of traffic before the query was even sent by the client. I imagine that will add up fast.
  - vlovich123 3y ago
    You’re right, I did my math with 1 core assumption. Still, it’s 800ms of 100% utilization of all 4 vCPUs across the entire cluster. That’s 40% capacity if the 2s latency was purely CPU bound and the client was next to the server, but we know the initial phase involves some round trips to communicate that 50mib so the 40% is a floor. My point remains that this is several orders of magnitude off in terms of cost still (as you mention network bandwidth required is off by similar orders of magnitude as cpu).

vlovich123 3y ago

Yeah, but that’s 1 request using 100% capacity of a 45 machine cluster. Relatively efficient but cost prohibitive.

avmich 3y ago
How does it compare to the search done without any encryption?
- seeknotfind 3y ago
  Many many orders of magnitude. It really depends on the search algorithm. If you're looking up a single term, there are many standard ways to index this, but for instance using a trie or hash table, the lookup cost would be a number of operations proportional to the search term length (e.g. for "foo", it's a of length 3, times some small number of operations for each letter). Plus then if you want to combine the results and sort by frequency, to estimate the cost of this, add up the number of pages from each term, p_1 + p_2 + ... = P. Then the number of operations might be P*log(P). This dominates the cost. So if your search terms appear in 1,000,000 of these pages, you're talking about on the order of ~6,000,000 small operations. An implementation would be able to execute this many operations on a single CPU in 10s or 100s of milliseconds maybe, for an elementary unoptimized algorithm.
deadfece 3y ago
It used 145 core-seconds of compute, according to the paper. That's not 100% unless they were mostly 1 core servers. However, the search used almost 50MiB of traffic before the query was even sent by the client. I imagine that will add up fast.
- vlovich123 3y ago
  You’re right, I did my math with 1 core assumption. Still, it’s 800ms of 100% utilization of all 4 vCPUs across the entire cluster. That’s 40% capacity if the 2s latency was purely CPU bound and the client was next to the server, but we know the initial phase involves some round trips to communicate that 50mib so the 40% is a floor. My point remains that this is several orders of magnitude off in terms of cost still (as you mention network bandwidth required is off by similar orders of magnitude as cpu).