How expensive would running a practical application on full homomorphic encryption be?

Question

This is a multidisciplinary question, hopefully I can stay on topic.

It has been published that we can now use (try?) fully homomorphic encryption computation on cipher text inputs. But I'd like to ask how practical it is to use this technology.

So here's a specific question.

If Alice has a one megabyte text file (like some novel). And Bob wants to provide the service of scanning the text and producing a list of the unique words in the file (useful for search indexing). And Bob wants to provide this service without any access to the underlying file. And the parties want to use something like PALISADE or the Microsoft Homomorphic Encryption libraries. Then what rough order of magnitude would this cost in terms of computer memory and retail cost of executing this on some commodity cloud provider?

Are we talking pennies, US dollars, or something exceeding the world GDP?

Answer 1

This will likely be rather expensive. This is because the problem you describe seems like it would be hard to express as a shallow arithmetic circuit, which is a rough estimate of how difficult the computation is with FHE.

In particular, a naive algorithm for solving your problem is:

1. Instantiate some hashmap
2. Iterate through your textfile, when you see the character " ", chunk off the previous block of text and add it to the hashmap. Throughout this, record the last bit of text you chunked off for future use in computing what to chunk
3. Return the hashmap

This has $O(n)$ complexity, and in practice should be only slightly less efficient than reading the entire array of text. Essentially no part of it translates well into FHE though. FHE evaluates programs on encrypted data where the programs are expressed as circuits (essentially standard programs where the computational path may not depend on the data).

The above program seems difficult to implement as a circuit efficiently. Both of the non-trivial parts of the program (instantiating/using a hashmap, and the iterative "chunking" operation) seem pretty bad for this. This can be worse if you use a variable-length text encoding such as UTF-8, but even for a fixed-length encoding (such as ASCII) it seems pretty bad.

If you want to get an explicit estimate of the complexity, you would first need to generate some fixed circuit implementing your desired function. There are some transpilers for "standard" programming languages to arithmetic circuits (this paper describes a transpiler (implemented here) from some subset of C to arithmetic circuits. I haven't checked if it suffices for this program) that you can leverage to do this, but I won't bother for this answer.

Even some of the more basic parts of the computation (checking if a character is equal to " ") is rather difficult in FHE --- equality testing is difficult to express as a low-degree polynomial, and therefore difficult to express as a low-(multiplicative) depth circuit.

Anyway, I would guess it would cost $\gg\\\$1$. I don't have order-of-magnitude estimates, but whatever the final number if I doubt you could convince customers to pay it rather than buying their own (trusted) server that they outsource plaintext computations to (this is both more generally useful, is a one-time cost vs a per computation cost, etc).

The big draw of FHE are for computations where:

1. Buying a trusted server is not an option (say computing functions of data from several mutually non-trusting sources)

2. "Simple" computations (where simple means something like "is expressible as a low-depth arithmetic circuit", or equivalently "is expressible as a low-degree polynomial").

An example application is that of computing statistical tests on medical data, which is (from my perspective) still the most compelling application of FHE, rather than "renting cloud-compute in a `trusted' way". Note that there is currently a big push for hardware implementation of FHE, which may change this picture in the near-term.