[swordswinger12]

All FHE schemes can run a full-blown virtual machine, but you might not live long enough to see Ubuntu finish booting up.

[whatidonteven]

Aren't there MASSIVE (read: showstopper) complications when you want to use FHE for "looping" computations?

I always thought FHE was only good if you can fully unroll your "fixed-length" computation, and even then you can only use each "program" once without compromising security.

[swordswinger12]

The short answer is yes. There are some (slow) ways to fix this: https://people.csail.mit.edu/nickolai/papers/goldwasser-we.p...

[whatidonteven]

Their construction relies on two unproven conjectures.

In particular the "Extractable Witness Encryption" conjecture is impossible under a reasonable falsifiable assumption: https://pdfs.semanticscholar.org/8587/dba4ff31e8118e9bd5914a...

Under that assumption, general purpose differing-inputs obfuscation cannot exist.

The way I understand it, FHE being applicable to anything other than "unwrapping a path through a circuit" seems implausible. Any claims of arbitrary encrypted computation should be viewed with the highest dose of skepticism.

[middleorigin]

Hmm so it doesn't work well with variable length data?

[whatidonteven]

You could say that.

Every time you want to run a computation on your FHE-enabled VPS you would need to upload data proportional to the maximum number of operations in the computation. Otherwise, re-running the same computation with a different input gives away information about both of your inputs and about the computation.

[throwaway613834]

What are the time complexities like?

Do they actually do better than "factor the RSA key, then compute the output, then re-encrypt"?

[warkdarrior]

The paper at http://www.shoup.net/papers/helib.pdf should give you an idea of what goes in a HE scheme. They also report performance of multiplying two 1024x1024 matrices: 473 seconds.