[teo_zero]

Now I see it. Thank you.

What I still don't understand is how this can be used to have the remote host give me responses that I couldn't have calculated myself locally, because all the data is stored in the cloud, not locally (that's how Google search works).

[meindnoch]

Well, consider a function that is vastly more complex than IsOdd() from my previous example. IsOdd() was a function from Z[2]^n to Z[2]. Instead, imagine a function from Z[2]^n to Z[2]^m, aka a general N-to-M bit Boolean function. Any such Boolean function can be represented as a logic circuit, that is, AND/OR/NOT gates and connections between them. Now, if we can implement these logic gates (and the connections between them) homomorphically, then we can implement a homomorphic realization of arbitrary functions. One "small" caveat when transforming programs into logic circuits is that all data must be inlined, all loops must be unrolled, all branches must be executed.