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.
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.
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.
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
One limitation of Homomorphic encryption, as far as I can see, is that there is no way for the encrypted program to choose to communicate some data in the clear.
Which means it can't be used to allow an untrusted party to run your encrypted server, and have the server communicate with parties that it doesn't trust. Which is what most servers do. Unless I'm mistaken, or there has been an advance?
There is no encrypted program, there is encrypted data. You can operate on this data, and it will reflect on the plaintext after decryption. I think what you're thinking about is functional encryption?
The distinction between program and data is not a sharp one, since f(x) = apply(<f, x>) = eval_x(f) (where eval_x takes the description of some program f and runs it on the constant input x). You can use this equivalence to compute f(x) where f is in plaintext and x is encrypted (ordinary HE), f and x are both encrypted (but apply is plaintext), or f is encrypted but x is not (so we can derive eval_x). In every case, however, the output is encrypted.
In general, this is only of theoretical interest, since the interpreter apply and the specialized interpreter eval_x are large, complicated programs.
I'm not thinking of functional encryption. I thought I'd read somewhere a plan to use homomorphic encryption with an encrypted program by simply applying an interpreter to it.
If you want fully general functional FE, then no; constructions are based on something called "indistinguishability obfuscation", a crypto primitive that a) we're not sure exists b) has conjectured constructions that are ultra ultra ultra slow.
Can you tell us what do you mean by "encrypted program"?
Do you mean that if all operations of a universal Turing machine were homomorphic then you can encryt the code with a hard-coded input and get an encrypted output?
Can you also elaborate on your server example? I don't understand what you are trying to do. (Whats an "encrypted server"?
Pretty much. Like mmastrac's comment (currently top). I hadn't realised people had got so far.
What you'd like to be able to do, is something like encrypt the code of a tor node in such a way that it could be run by an untrusted hosting provider, without breaking the security of tor.
FHE does in principle allow you to do this, but it has the limitation that the outputs of the "Tor node" will themselves be encrypted. That's ok if you have the decryption key and are the one interacting with the Tor node. It's not ok if you want the Tor node to output useful data like network packet headers that anyone can parse.
There is another field called cryptographic program obfuscation that tries to avoid this problem, and actually create "encrypted" programs that can output useful unencrypted outputs that anyone can use. There are a lot of restrictions on that type of program. Here's another long (and very high level) blog post on that: https://blog.cryptographyengineering.com/2014/02/21/cryptogr...
This is a very interesting read, highly recommend! I'm currently reading the excellent book Cryptography Engineering [1] and this article definitely adds to my newborn interest in cryptography!
> 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.