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

How does it compare to the search done without any encryption?

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.

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.

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