[mmastrac]

Oh hey, this is something I've actually done some real work on!

> Just try converting that into a circuit

Hmm. I think this article is a little behind the times. Loops are not a problem with Homomorphic encryption, as we can create circuits that work exactly like a transistor-based CPU.

In fact, I've got an implementation of one that I've been working on here: https://github.com/mmastrac/oblivious-cpu

The trick to making this work is that you may not know how long the computation is going to take, so you need to either add a set number of iterations to run (ie: clock cycles), or send back encrypted updates as you run to give your trusted computer a chance to determine when the calculation has finished.

[mti]

I'm not sure what specific scheme you have in mind, but while FHE for Turing machines does exist, it is really, really hard to instantiate. A construction with some restrictions and requiring a massive amount of preprocessing is given in Goldwasser et al.'s famous paper on reusable garbled circuits, and it already uses succinct functional encryption as a building block; and for the stronger notion of FHE for TM you basically need obfuscation. So thinking about implementing any of this seems somewhat premature to me.

[Ar-Curunir]

The very next line of Matt's blog post explains this:

> I mean, it’s not impossible to unroll loops (if you know the maximum number of iterations), but the resulting circuit is not likely to be practical. Moreover, this isn’t purely an issue with the use of circuits, but rather with the use of encrypted data. No matter what computational model you employ, you’re always going to have difficulty with things like control flow changes that depend on input data that the executing party can’t see.

If you want to add in interaction, then you have other far more efficient schemes for achieving such FHE, like garbled circuits